2.cpp

谢尔排序法 和 归并排序法 恰当的输出中间结果

#include <iostream>
using namespace std;
template <class T>
class Doer
{
	public:
		Doer(T k);
		~Doer() {delete [] a;};
		void Insert(T n,const T& x,T c); 
		void Arran(T k);
	private:
		T *a;
};
template <class T>
void Doer <T> :: Insert(T n,const T& x,T c)
{
	T i;
	for (i=n-c;i>=0 && x<a[i]; i=i-c)
		a[i+c] = a[i];
	a[i+c] = x;
}
template <class T>
void Doer <T> :: Arran(T k)
{
	T t=k/2;
	while (t!=0)
	{
		for (T i=t ; i<k ; i++)
		{
			T q=a[i];
			Insert (i,q,t);
		}
		t=t/2;
		for ( i=0 ; i<k ; i++)
		{
			cout << a[i] << " " ;
		}
			cout << endl;
	}
}
template <class T>
Doer<T> :: Doer(T k)
{
	a=new T[k];
	for (T i=0;i<k;i++)
	{
		cin >> a[i];
	}
}

template <class T>
class Backin
{
	public:
		Backin(T k);
		~Backin() {delete [] a;};
		T Insert(const T x,T i,T m);
		void Bace (T i,T m,T n);
		void Break (T i,T n,T m) ;
		void Show( int  n);
	private:
		T *a;
};
template <class T>
T Backin<T>::Insert (const T x,T i,T m)
{
	T k; 
	for (k=m-1;k>=i && x<a[k];k--)
		a[k+1] = a[k];
	a[k+1] = x;
	return k+2;
}

template <class T>
void Backin <T> :: Bace (T i,T m,T n)
{
	T t=0,h=i;
	for (T y=m;y<=n;y++)
	{
		t=Insert(a[y],h,y);
		h=t;
	}
}
template <class T>
void Backin <T> :: Break(T i,T n,T m)
{
	if (n==i)	return;	
	Break(i,(n+i)/2,m);
	Break((n+i)/2+1,n,m);
	Bace(i,(n+i)/2+1,n);
	Show(m);
}
template <class T>
void Backin<T>::Show( int n)
{
	for (int l = 0 ; l < n ; l ++)
			cout << a[l] << "  " ;
		cout << endl ;
}

template <class T>
Backin<T> :: Backin(T k)
{
	a=new T[k];
	for (T i=0;i<k;i++)
	{
		cin >> a[i];
	}
}

int main ()
{
	int k;
	int j;
	cout << "Please put in the length of the array you want!! “谢尔”" << endl;
	cin >> k;
	if (k==1 || k==0)
	{
		cout << "Are you kidding !!=@-@=" << endl;
		return 0;
	}
	cout << "Please put in the number !!" << endl;
	Doer <int> an(k);
	an.Arran(k);
	cout << "Please put in the length of the array you want!! “归并”" << endl;
	cin >> j;
	cout << "Please put in the number !! " << endl;
	Backin<int> bn(j);
	bn.Break(0,j-1,j);
	return 0;
}