sort.h

数据结构中数据的排序示例,包括堆排序、快速排序等

#include<iostream.h>
#define MAXSIZE  20

 struct sqlist{
	int r[MAXSIZE+1];
	int length;
};

class sort{
	sqlist l;
	sqlist q;

	void renew()
	{for(int i=0;i<=l.length;i++)
	l.r[i]=q.r[i];
	}

	void shellinsert(int dk)
	{for(int i=dk+1;i<=l.length;++i)
	if(l.r[i]<l.r[i-dk])
	{l.r[0]=l.r[i];
	for(int j=i-dk;j>0&&l.r[0]<l.r[j];j-=dk)
		l.r[j+dk]=l.r[j];
	l.r[j+dk]=l.r[0];}
	}
	
	int partition(int low,int high)
	{int p=l.r[low];
	while(low<high)
	{while(low<high&&l.r[high]>=p)--high;
	 {l.r[0]=l.r[low];l.r[low]=l.r[high];l.r[high]=l.r[0];}
	while(low<high&&l.r[low]<=p)++low;
	{l.r[0]=l.r[low];l.r[low]=l.r[high];l.r[high]=l.r[0];}}
	show();
	return low;
	}

	void heapadjust(int s,int m)
	{l.r[0]=l.r[s];
	for(int j=2*s;j<=m;j*=2){
	{if(j<m&&l.r[j]<l.r[j+1])++j;
	if(!(l.r[0]<l.r[j]))break;
	l.r[s]=l.r[j];s=j;}}
	l.r[s]=l.r[0]; 
	
	}

	void merge(sqlist sr,sqlist &tr,int i,int m,int n)
	{for(int j=m+1,k=i;i<=m&&j<=n;++k)
	if(sr.r[i]<sr.r[j])tr.r[k]=sr.r[i++];
	else tr.r[k]=sr.r[j++];
	if(i<=m)
		for(int q=i;q<=m;q++)
		tr.r[k++]=sr.r[q];
	if(j<=n)
		for(int q=j;q<=n;q++)
		tr.r[k++]=sr.r[q];
	
	}
	
	void mergepass(sqlist  x,sqlist &y,int s,int n)
	{int i=1;
	while(i<=n-2*s+1)
	{merge(x,y,i,i+s-1 ,i+2*s-1 );
	i=i+2*s ;}
	if(i+s<1+n)merge(x,y,i ,i+s-1 ,n);
	else for(int j=i ;j<=n;j++)
		y.r[j]=x.r[j];

	}

public:
	sort(int length)
	{q.length=l.length=length;q.r[0]=l.r[0]=0;
	cout<<"请输入"<<length<<"个数据"<<endl;
	for(int i=1;i<=length;i++)
	{cin>>l.r[i];
	q.r[i]=l.r[i];}
	}

	void insertsort()
	{cout<<"\n插入排序法:"<<endl;
	for(int i=2;i<=l.length;i++)
	{if(l.r[i]<l.r[i-1])
	{l.r[0]=l.r[i];
	l.r[i]=l.r[i-1];
	for(int j=i-2;l.r[0]<l.r[j];--j)
	l.r[j+1]=l.r[j];
	l.r[j+1]=l.r[0];}
	cout<<"第"<<i-1<<"趟排序:  " ;
	show();}
	renew();
	}

	void shellsort(int dlta[],int t)
	{cout<<"\n希尔排序法:"<<endl;
		for(int i=0;i<t;i++)
		{shellinsert(dlta[i]);
		cout<<"第"<<i+1<<"趟排序:  " ;
		show();}
		renew();}

	void bsort()
	{cout<<"\n起泡排序法:"<<endl;
	for(int i=1;i<l.length;i++)
	{for(int j=1;j<l.length-i+1;j++)
			if(l.r[j+1]<l.r[j])
			{l.r[0]=l.r[j+1];l.r[j+1]=l.r[j];l.r[j]=l.r[0];}
			cout<<"第"<<i<<"趟排序:  " ;	
			show();}
			renew();
	}

	void heapsort()
	{cout<<"\n选择排序法:"<<endl;
		for(int i=l.length/2;i>0;--i)
	heapadjust(i,l.length);
		cout<<"构成堆:    ";
		show();
	for(i=l.length;i>1;--i)
	{l.r[0]=l.r[i];l.r[i]=l.r[1];l.r[1]=l.r[0];
	heapadjust(1,i-1);
	cout<<"第"<<l.length-i+1<<"趟排序:  " ;
	show();}
	renew();
	}
	
    void qsort(int low,int high)
	{  static int k=0;
		if(low<high){cout<<"第"<<++k<<"趟排序:  " ;
	int pivot=partition(low,high); 
	qsort(low,pivot-1);
	qsort(pivot+1,high);}
	}

	void mergesort(int n)
	{   renew();
	     cout<<"\n归并排序法:"<<endl;
		sqlist b;
		b=*(new sqlist);
	int s=1,k=0;
	while(s<n)
	{mergepass(l,b,s,n);
	cout<<"第"<<++k<<"次归并:  " ;
	show();
	s+=s;
	mergepass(b,l,s,n);
	cout<<"第"<<++k<<"次归并:  " ;
	show();
	s+=s;}
 
	}


	void show()
	{for(int i=1;i<=l.length;i++)
	cout<<l.r[i]<<"  ";
	cout<<"\n";}

};