shell_mergesorting.h

同时对Shell排序和归并排序进行了实现,并且打印了每趟的结果

#include<iostream>
using namespace std;
template<class T>
#define MAX 10
class mylist{
	public:
		mylist(int maxlistsize=15);
	    ~mylist();
		bool isempty()const{return length==0;}
		int getlength()const{return length;}
		bool find(int k,T& x)const;
		int search(int k,T& x)const;
		mylist<T>& mydelete(int k,T& x);
		mylist<T>& insert(int k,const T& x);
		void output(ostream& out)const;
		void ShellSort(int n);
		void MergeSort(int left,int right);
		void Copy(T f[],int left,int right);
		void Merge(T d[],int l,int m,int n);
		T **table;
	
	private:
		
		int length,maxsize;
	
	
};
template<class T>
mylist<T>::mylist(int maxlistsize)
{
	maxsize=maxlistsize;
	table=new T*[maxsize];
	length=0;
}
template<class T>
mylist<T>::~mylist()
{
	for(int i=0;i<length;i++)
	{
		delete table[i];
	}
		delete [] table;
}
template<class T>
mylist<T>& mylist<T>::mydelete(int k,T& x)
{
	if(find(k,x))
	{
		for(int i=k;i<length;i++)
			table[i-1]=table[i];
		length--;
		return *this;
	}
	//else throw OutOfBounds();
}
template<class T>
bool mylist<T>::find(int k,T& x)const
{
	if(k<1||k>length)
		return false;
	x=*table[k-1];
	return true;
}
template<class T>
mylist<T>& mylist<T>::insert(int k,const T& x)
{
	//if(k<0||k>length)
		//throw OutOfBounds();
	//if(length==maxsize)
		//throw NoMem();
	for(int i=length-1;i>=k;i--)
	{
		table[i+1]=table[i];
	}
		table[k]=new T;
		*table[k]=x;
		length++;
		return *this;
	
}
template<class T>
void mylist<T>::output(ostream& out)const
{
	for(int i=0;i<length;i++)
	{
		out<<*table[i]<<" ";
	}
	out<<endl;
}
template<class T>
ostream& operator<<(ostream& out,const mylist<T>& x)
{
	x.output(out);
	return out;
}

template<class T>
void mylist<T>::ShellSort(int n)
{
	int i,j,k,gap;
	gap=n/2;
	while(gap>0)
	{
		for(k=0;k<gap;k++)
		{
			for(i=k+gap;i<n;i=i+gap)
			{
				for(j=i-gap;j>=k;j=j-gap)
				{
					if(*table[j]>*table[j+gap])
					{
						int temp;
						temp=*table[j];
						*table[j]=*table[j+gap];
						*table[j+gap]=temp;
					}
					else
						break;
				}
			}
		}
		cout<<"gap="<<gap<<endl;
		for(int i=0;i<length;i++)
		{
			cout<<*table[i]<<" ";
		}
		cout<<endl;
		gap=gap/2;
	}

}
template<class T>
void mylist<T>::MergeSort(int left,int right)
{
	if(left<right)
	{
		int i=(left+right)/2;
		int b[MAX];
		MergeSort(left,i);
		MergeSort(i+1,right);
		Merge(b,left,i,right);
		Copy(b,left,right);
		for(int ii=0;ii<length;ii++)
		{
			cout<<*table[ii]<<" ";
		}
		cout<<endl;
	}
}
template<class T>
void mylist<T>::Merge(T d[],int l,int m,int r)
{
	int i=l,j=m+1,k=l;
	while((i<=m)&&(j<=r))
	{
		if(*table[i]<=*table[j])
			d[k++]=*table[i++];
		else
			d[k++]=*table[j++];
	}
	if(i>m)
	{
		for(int q=j;q<=r;q++)
			d[k++]=*table[q];
	}
	else
	{
		for(int q=i;q<=m;q++)
			d[k++]=*table[q];
	}
}

template<class T>
void mylist<T>::Copy(T f[],int left,int right)
{
	for(int q=left;q<=right;q++)
	{
		*table[q]=f[q];
	}
}