sort.cpp

这是关于数据结构书中经常介绍的排序算法的具体实现

//#include<stdafx.h>
#include<iostream>
#include<time.h>
#include<stdlib.h>
//#include<mmsystem.h>
//#include<Windows.h>
//#include<Winmm.dll>

using namespace std;

#define MAXSIZE 5000  //7000
#define MAXINT 32767

//***********************插入排序定义***************************
typedef struct RedType{
  int key;
  int otherinfo;
}RedType;
typedef struct SqList{
  RedType r[MAXSIZE+1];
  int length;
}SqList;

//***********************表插入排序定义***************************
typedef struct SLNode{
  RedType rc;
  int next;
}SLNode;
typedef struct SLinkListType{
  SLNode r[MAXSIZE+1];
  int length;
}SLinkListType;

class Sorting_Compare{
public:
	//**********************初始化　输出***************************
	void Init_SqList(SqList *L,SqList *temp);
	void Output_SqList(SqList *L);
	void Init_SLinkList(SqList *L,SLinkListType *SL);
	void Output_SLinkList(SLinkListType *SL);
    void createtestarray(SqList *L);

	//***********************插入排序******************************
	void InsertSort(SqList *L);

	//***********************折半插入排序******************************
	void BInsertSort(SqList *L);
	
	//***********************表插入排序******************************
	void TInsertSort(SLinkListType *SL);
	void Arrange(SLinkListType *SL);

	//***********************希尔排序******************************
	void ShellInsert(SqList *L,int dk);
	void ShellSort(SqList *L,int t);

	//***********************快速排序******************************
	void QSort(SqList *L,int low,int high);
	void QuickSort(SqList *L);
	int Partition(SqList *L,int low,int high);

	//***********************冒泡排序和改进******************************
	void BubbleSort(SqList *L);
	void advanced_BubbleSort(SqList *L);

	//**********************堆排序******************************
	void HeapAdjust(SqList *H,int s,int m);
	void HeapSort(SqList *H);

	//**********************归并排序******************************
	void Merge(RedType SR[],RedType TR[],int i,int m,int n);
	void Msort(RedType SR[],RedType TR1[],int s,int t); 
	void MergeSort(SqList *L);
};

//***************************插入排序********************************************
void Sorting_Compare::InsertSort(SqList *L){	
	int i,j;
	//cout<<timeGetTime()<<endl;
	for(i=2;i<=L->length;i++)
		if(L->r[i].key<L->r[i-1].key){
			L->r[0]=L->r[i];
			L->r[i]=L->r[i-1];
			for(j=i-2;L->r[0].key<L->r[j].key;j--)
				L->r[j+1]=L->r[j];
			L->r[j+1]=L->r[0];
		}
	return;
}

void Sorting_Compare::Init_SqList(SqList *L,SqList *temp){
	for(int i=1;i<=MAXSIZE;i++)
		temp->r[i].key=L->r[i].key;
    temp->length=MAXSIZE;
}

void Sorting_Compare::Output_SqList(SqList *L){
	int i;
	cout<<endl;
	for(i=1;i<=L->length;i++){
		cout<<L->r[i].key<<"  ";
        if(i%5==0)  cout<<endl;
	}
	cout<<endl<<endl;
	return;
}

//***********************折半插入排序*******************************************
void Sorting_Compare::BInsertSort(SqList *L){
	int i,j,m,low,high;		
	for(i=2;i<=L->length;i++){
		L->r[0]=L->r[i];
		low=1;
		high=i-1;
		while(low<=high){
			m=(low+high)/2;
			if(L->r[0].key<L->r[m].key)
				high=m-1;
			else
				low=m+1;
		}
		for(j=i-1;j>=high+1;j--)
			L->r[j+1]=L->r[j];
		L->r[high+1]=L->r[0];
	}
	return;
}

//**********************************希尔排序********************************************
void Sorting_Compare::ShellInsert(SqList *L, int dk){
   int i,j;
   for(i=dk+1;i<=L->length;++i)
      if ( L->r[i].key< L->r[i-dk].key){
        L->r[0] = L->r[i];           
        for(j=i-dk;  j>0&&(L->r[0].key<L->r[j].key);j-=dk)
           L->r[j+dk] = L->r[j]; 
        L->r[j+dk] = L->r[0];       
      } 
} 

void Sorting_Compare::ShellSort (SqList *L,int t){  
	int dlta,sum=1,k,m;		
	for(k=0;k<t;++k){
		 for(m=1;m<=t-k+1;m++) sum=sum*2;
		 dlta=sum-1;
		 if(k==t-1) dlta=1;
         ShellInsert(L,dlta);
	}
} 

//*****************************快速排序*************************************
void Sorting_Compare::QSort(SqList *L,int low,int high){  
	if (low<high){          
    int pivotloc=Partition(L,low,high);
	QSort(L,low,pivotloc-1);
	QSort(L,pivotloc+1,high);
   }
}

void Sorting_Compare::QuickSort(SqList *L){
     QSort(L,1,L->length);
} 

int Sorting_Compare::Partition(SqList *L, int low, int high){
	L->r[0] = L->r[low]; 
	int pivotkey = L->r[low].key;    
	while(low<high){
		while(low<high&& L->r[high].key>=pivotkey)
           -- high;      
		L->r[low] = L->r[high];
		while(low<high && L->r[low].key<=pivotkey) 
           ++ low;     
		L->r[high] = L->r[low];
	}
	L->r[low] = L->r[0];     
	return low;
}

//**********************************冒泡排序和改进**********************************************
void Sorting_Compare::BubbleSort(SqList *L){		
	int temp,i,j;
    for(i=L->length;i>1;--i)
       for(j=1;j<i;++j)
          if(L->r[j+1].key<L->r[j].key){
               temp=L->r[j+1].key;
			   L->r[j+1].key=L->r[j].key;
			   L->r[j].key=temp;	
           }
}

void Sorting_Compare::advanced_BubbleSort(SqList *L){	  
	int temp,i,j,k,lastExchangeIndex=1;
	i=L->length;
    while(i>2){
       for(j=1,k=0;j<i;++j)
          if(L->r[j+1].key<=L->r[j].key){
              temp=L->r[j+1].key;
			  L->r[j+1].key=L->r[j].key;
			  L->r[j].key=temp;
              lastExchangeIndex=j+1;
          k++; 
		  }
	   if(k!=0)
	      i=lastExchangeIndex;
	   else i=1;
	}
return;
}

//*****************************表插入排序**************************************************
void Sorting_Compare::Init_SLinkList(SqList *L,SLinkListType *SL){
	SL->r[0].rc.key = MAXINT ;
	SL->r[0].next = 1;  
	SL->r[1].next = 0;
	for(int i=1;i<=MAXSIZE;i++)
		SL->r[i].rc.key=L->r[i].key;
	SL->length=MAXSIZE;	
	return;
}

void Sorting_Compare::TInsertSort(SLinkListType *SL){  
	int i,k,q; 
	for(i=2;i<=SL->length;i++){
	   for(q=0,k=SL->r[0].next;SL->r[k].rc.key<=SL->r[i].rc.key;q=k,k=SL->r[k].next);
		  SL->r[i].next = k; 
		  SL->r[q].next = i;  
	}	
	return;
}

void Sorting_Compare::Arrange(SLinkListType *SL){
	int p,q,i;   SLNode temp;
	p=SL->r[0].next;
	for(i=1;i<SL->length;i++){
	   while(p<i)
		 p=SL->r[p].next;
	   q=SL->r[p].next;
	   if(p!=i){
		 temp=SL->r[p];
		 SL->r[p]=SL->r[i];
		 SL->r[i]=temp;
		 SL->r[i].next=p;
	   }
	   p=q;
	}
	return;
}

void Sorting_Compare::Output_SLinkList(SLinkListType *SL){
	int i;
	for(i=1;i<=SL->length;i++){
		cout<<SL->r[i].rc.key<<"   ";
        if(i%5==0)  cout<<endl;	
	}
	cout<<endl<<endl;
	return;
}

//***************************************堆排序******************************************
void Sorting_Compare::HeapAdjust(SqList *H,int s,int m){ 
	int j;    RedType rc=H->r[s];
    for(j=2*s;j<=m;j*=2){
       if(j<m&&(H->r[j].key<H->r[j+1].key)) 
		   ++j;
       if (rc.key>=H->r[j].key) 
		   break;
       H->r[s]=H->r[j];  s=j;
    }
    H->r[s]=rc;
}

void Sorting_Compare::HeapSort(SqList *H){
  int i;  RedType temp;
  for(i=H->length/2;i>0;--i)
       HeapAdjust ( H, i, H->length ); 
  for(i=H->length;i>1;--i){  
	   temp=H->r[i];
	   H->r[i]=H->r[1];
	   H->r[1]=temp;
       HeapAdjust(H, 1, i-1); 
  }
} 

//***********************************归并排序***********************************************
void Sorting_Compare::Merge(RedType SR[],RedType TR[],int i,int m,int n){
  int j,k;
  for (j=m+1,k=i;i<=m && j<=n;++k){                   
      if (SR[i].key<=SR[j].key)  TR[k] = SR[i++];
      else TR[k] = SR[j++];
   }
   if (i<=m)  for(;k<=n&&i<=m;k++,i++) TR[k]=SR[i];
   if (j<=n)  for(;k<=n&&j<=n;k++,j++) TR[k]=SR[j];
}

void Sorting_Compare::Msort(RedType SR[],RedType TR1[],int s,int t){
	RedType *TR2=new RedType[t];
    if(s==t) TR1[s]=SR[s];
    else{
	    int m = (s+t)/2;
		Msort (SR, TR2, s, m);
		Msort (SR, TR2, m+1, t);
		Merge (TR2, TR1, s, m, t);
    }
}

void Sorting_Compare::MergeSort(SqList *L){
   Msort(L->r,L->r,1,L->length);
}

void Sorting_Compare::createtestarray(SqList *L){
   L->length=MAXSIZE;
   srand(time(NULL));
   for(int i=1;i<=MAXSIZE;i++)
       L->r[i].key=rand()%40000;
}

//*********************************main****************************************
void main(){
	Sorting_Compare soco;
	SqList L,temp;
	SLinkListType SL;

	double time1,time2;

	cout<<"测试数据有"<<MAXSIZE<<"个"<<endl<<endl;
	   
	soco.createtestarray(&L);
    //cout<<"随机生成数据："<<endl;
	//soco.Output_SqList(&L);
 
	/*while(1){	
	  cout<<"1-----插入排序"<<endl
		  <<"2-----折半插入排序"<<endl
		  <<"3-----表插入排序"<<endl
		  <<"4-----希尔插入排序"<<endl
		  <<"5-----快速排序"<<endl
		  <<"6-----冒泡排序"<<endl
		  <<"7-----冒泡排序改进"<<endl
		  <<"8-----堆排序"<<endl
		  <<"9-----归并排序"<<endl
		  <<"0-----退出"<<endl<<endl;
	
	  cout<<"输入选项:"<<endl;
	  cin>>choice;
	  cout<<endl;*/
	
	  //if(choice==0)  break;	  
	  //if(choice==1){
		
		soco.Init_SqList(&L,&temp);	
		time1=clock();
		soco.InsertSort(&temp);
		time2=clock();
		cout<<endl<<"经过插入排序后,时间为:"<<(time2-time1)/CLK_TCK<<"秒"<<endl;

		soco.Init_SqList(&L,&temp);			
		time1=clock();
		soco.BInsertSort(&temp);
        time2=clock();
	    cout<<endl<<"经过折半插入排序后,时间为:"<<(time2-time1)/CLK_TCK<<"秒"<<endl;

		soco.Init_SLinkList(&L,&SL);
        time1=clock();
		soco.TInsertSort(&SL);
		soco.Arrange(&SL);
        time2=clock();
		cout<<endl<<"经过表插入排序后,时间为:"<<(time2-time1)/CLK_TCK<<"秒"<<endl;

		soco.Init_SqList(&L,&temp);
		time1=clock();
		soco.ShellSort(&temp,8);
        time2=clock();
	    cout<<endl<<"经过希尔排序后,时间为:"<<(time2-time1)/CLK_TCK<<"秒"<<endl;

		soco.Init_SqList(&L,&temp);
        time1=clock();
		soco.QuickSort(&temp);   
        time2=clock();
	    cout<<endl<<"经过快速排序后,时间为:"<<(time2-time1)/CLK_TCK<<"秒"<<endl;

		soco.Init_SqList(&L,&temp);
        time1=clock();
		soco.BubbleSort(&temp);
        time2=clock();
	    cout<<endl<<"经过冒泡排序后,时间为:"<<(time2-time1)/CLK_TCK<<"秒"<<endl;

		/*soco.Init_SqList(&L,&temp);
        time1=clock();
		soco.advanced_BubbleSort(&temp);
        time2=clock();
	    cout<<endl<<"经过改进冒泡排序后,时间为:"<<(time2-time1)/CLK_TCK<<"秒"<<endl;*/

		soco.Init_SqList(&L,&temp);
        time1=clock();
		soco.HeapSort (&temp);
        time2=clock();
		cout<<endl<<"经过堆排序后,时间为:"<<(time2-time1)/CLK_TCK<<"秒"<<endl;

		soco.Init_SqList(&L,&temp);	
		time1=clock();	
		soco.MergeSort(&temp);
        time2=clock();
	    cout<<endl<<"经过归并排序后,时间为:"<<(time2-time1)/CLK_TCK<<"秒"<<endl; 
}