课程设计题目(排序)

排序算法的比较系统总体说明：编程实现选择、冒泡、直接插入、折半插入、希尔、快速和归并等排序算法，并计算每种算法的比较、移动次数。

完成功能的详细说明：1．要求由键盘输入待排序数据的个数和待排序数据。

2．实现选择、冒泡、直接插入、折半插入、希尔、快速和归并等排序算法。

3．比较每种排序算法在排序码个数相同的情况下，排序过程中排序码的比较次数和元素的移动次数。

4．待排序数据量分别取n=10，30，50，100时，比较同一个算法在排序过程中排序码的比较次数和元素的移动次数。

5．输出结果中，给出各算法按两种方式进行比较后的结果。

#include<iostream>#include<string>#include<time.h>#define random(x)(rand()%x)using namespace std;struct Data{int dt[100];int length;int compare;int remove;};class list{public:static int compare;static int remove;Data insertsort(Data,int);//直接插入排序插入排序分直接插入排序和折半插入排序void binsertsort(Data);//折半插入排序折半插入排序减少了比较次数而未改变移动次数void shellsort(Data);//希尔排序希尔排序是对直接插入排序的一种改进算法void selectsort(Data);//直接选择排序void bubblesort(Data);//冒泡排序交换排序分冒泡排序和快速排序void quicksort(Data&,int,int);//快速排序快速排序是对冒泡排序的一种改进void quicksortx(Data);void towmerge(Data&,Data&,int,int,int);//二路归并排序算法void mergepass(Data&,Data&,int);//一趟2路归并算法void mergesort(Data,Data);//2-路归并算法list(){}void display(Data);void show(int);Data getdata1(int);Data getdata2();void play1(int);void play2();void play3();};int list::remove=0;int list::compare=0;Data list::getdata1(int length){Data data;data.length=length;srand((int)time(0));for(int i=0;i<length;i++){data.dt[i]=random(1000);}pare=0;data.remove=0;return data;}Data list::getdata2(){Data data;int n=0;int m;cout<<"请输入待输入数据的个数：\n";cin>>n;data.length=n;for(int i=0;i<n;i++){cout<<"请输入第"<<i+1<<"个数据：";cin>>m;data.dt[i]=m;}pare=0;data.remove=0;return data;}void list::display(Data data){for(int i=0;i<data.length;i++){cout<<data.dt[i]<<" ";if((i+1)%10==0)cout<<endl;}}Data list::insertsort(Data data,int h)//直接插入排序{int n=0;for(int i=1;i<data.length;i++){n=data.dt[i];int j=i-1;while(j>=0&&data.dt[j]>n){data.dt[j+1]=data.dt[j];data.remove++;j--;}data.dt[j+1]=n;}pare+=data.remove+data.length-1;if(h==1){cout<<"比较结果为：\n";display(data);cout<<"\n其中\n";cout<<"直接插入排序--";cout<<"比较次数："<<pare<<" 移动次数："<<data.remove<<endl;}return data;}void list::binsertsort(Data data)//折半插入排序{int n=0;int j=0;int low=0;int high=0;int middle=0;for(int i=1;i<data.length;i++){n=data.dt[i];low=0;high=i-1;while(low<=high){pare++;middle=(low+high)/2;if(data.dt[middle]>n)high=middle-1;elselow=middle+1;}for(j=i-1;j>high;j--){data.dt[j+1]=data.dt[j];data.remove++;}data.dt[high+1]=n;}//cout<<"======================================\n";cout<<"折半插入排序--";cout<<"比较次数："<<pare<<" 移动次数："<<data.remove<<endl;//display(data);}void list::selectsort(Data data)//直接选择排序{for(int i=0;i<data.length;i++){int j=i;for(int k=j+1;k<data.length;k++){pare++;if(data.dt[j]>data.dt[k])j=k;}if(j!=i){int s=data.dt[i];data.dt[i]=data.dt[j];data.dt[j]=s;data.remove++;}}cout<<"直接选择排序--";cout<<"比较次数："<<pare<<" 移动次数："<<data.remove<<endl;// display(data);}void list::bubblesort(Data data)//冒泡排序{int n=0;for(int i=data.length-1;i>0;i--)for(int j=0;j<i;j++){pare++;if(data.dt[j]>data.dt[j+1]){n=data.dt[j];data.dt[j]=data.dt[j+1];data.dt[j+1]=n;data.remove++;}}cout<<"冒泡排序--";cout<<"比较次数："<<pare<<" 移动次数："<<data.remove<<endl;//display(data);}void list::quicksort(Data &data,int s,int t)//快速排序{int n;int i=s;int j=t;if(j>i){n=data.dt[i];do{while(j>i&&data.dt[j]>=n){j--;pare++;}if(j>i){data.dt[i]=data.dt[j];i++;data.remove++;}while(j>i&&data.dt[i]<=n){i++;pare++;}if(j>i){data.dt[j]=data.dt[i];j--;data.remove++;}}while(j>i);data.dt[i]=n;quicksort(data,s,i-1);quicksort(data,j+1,t);}}void list::quicksortx(Data data){quicksort(data,0,data.length-1);cout<<"快速排序--";cout<<"比较次数："<<pare<<" 移动次数："<<data.remove<<endl;//display(data);}void list::shellsort(Data data)//希尔排序{int i=0,j=0,gap=0;gap=data.length/2;while(gap>0){for(i=gap;i<data.length;i++){j=i-gap;while(j>=0){pare++;if(data.dt[j]>data.dt[j+gap]){n=data.dt[j+gap];data.dt[j+gap]=data.dt[j];data.dt[j]=n;j=j-gap;data.remove++;}elsej=-1;}}gap=gap/2;}cout<<"希尔排序--";cout<<"比较次数："<<pare<<" 移动次数："<<data.remove<<endl;//display(data);}void list::towmerge(Data&data1,Data&data2,int s,int m,int t){int i,j,k;i=s;j=m+1;k=s;while(i<=m&&j<=t){compare++;if(data1.dt[i]<=data1.dt[j]){data2.dt[k]=data1.dt[i];k++;i++;}elsedata2.dt[k]=data1.dt[j];remove++;k++;j++;}}while(i<=m){data2.dt[k]=data1.dt[i];k++;i++;}while(j<=t){data2.dt[k]=data1.dt[j];k++;j++;}}void list::mergepass(Data &data,Data &r,int len) {int p=0;while(p+2*len-1<data.length){towmerge(data,r,p,p+len-1,p+2*len-1);p=p+2*len;}if(p+len-1<data.length-1)towmerge(data,r,p,p+len-1,data.length-1);elsefor(int i=p;i<data.length;i++){r.dt[i]=data.dt[i];}}void list::mergesort(Data data,Data r)//2-路归并算法{int len;len=1;while(len<data.length){mergepass(data,r,len);len=len*2;mergepass(r,data,len);len=len*2;}cout<<"二路归并排序--";cout<<"比较次数："<<compare<<" 移动次数："<<remove<<endl;//display(data);}void list::play1(int q){Data data;Data r;r.length=0;r.remove=0;list::compare=0;list::remove=0;data=getdata1(q);r.length=q;cout<<"原始数据为：\n";display(data);/*cout<<"比较结果为：\n";display(data);cout<<"其中\n";*/insertsort(data,1);binsertsort(data);selectsort(data);bubblesort(data);shellsort(data);quicksortx(data);mergesort(data,r);}void list::play2(){Data data;Data r;list::compare=0;list::remove=0;data=getdata2();r.length=data.length;cout<<"原始数据为：\n";display(data);cout<<endl;insertsort(data,1);binsertsort(data);selectsort(data);bubblesort(data);shellsort(data);quicksortx(data);mergesort(data,r);}void list::play3(){Data data[3];Data d[3];Data r[3];for(int i=0;i<3;i++){r[i].length=0;r[i].remove=0;}data[0]=getdata1(10);cout<<"原始数据为：\n";cout<<"第一组，随机产生十个数：\n";display(data[0]);cout<<"==================\n";data[1]=getdata1(50);cout<<"第二组，随机产生五十个数：\n";display(data[1]);cout<<"==================\n";data[2]=getdata1(100);cout<<"第三组，随机产生一百个数：\n";display(data[2]);d[0]=insertsort(data[0],0);d[1]=insertsort(data[1],0);d[2]=insertsort(data[2],0);cout<<"比较结果为：\n";cout<<"第一组\n";display(d[0]);cout<<"第二组\n";display(d[1]);cout<<"第三组\n";display(d[2]);cout<<"其中\n";cout<<"==================\n";cout<<"直接插入排序--";cout<<"比较次数："<<d[0].compare<<" 移动次数："<<d[0].remove<<endl;cout<<"直接插入排序--";cout<<"比较次数："<<d[1].compare<<" 移动次数："<<d[1].remove<<endl;cout<<"直接插入排序--";cout<<"比较次数："<<d[2].compare<<" 移动次数："<<d[2].remove<<endl;cout<<"=======================\n";binsertsort(data[0]);binsertsort(data[1]);binsertsort(data[2]);cout<<"=======================\n";selectsort(data[0]);selectsort(data[1]);selectsort(data[2]);cout<<"=======================\n";bubblesort(data[0]);bubblesort(data[1]);bubblesort(data[2]);cout<<"=======================\n";shellsort(data[0]);shellsort(data[1]);shellsort(data[2]);cout<<"=======================\n";quicksortx(data[0]);quicksortx(data[1]);quicksortx(data[2]);cout<<"=======================\n";list::compare=0;list::remove=0;r[0].length=10;mergesort(data[0],r[0]);list::compare=0;list::remove=0;r[1].length=50;mergesort(data[1],r[1]);list::compare=0;list::remove=0;r[2].length=100;mergesort(data[2],r[2]);cout<<"插入排序\n直接插入排序是一种稳定的排序\n折半插入排序减少了记录关键字之间的比较次数，而未改变记录的移动次数\n";cout<<"希尔排序是对直接插入排序的一种改进算法，它是一种不稳定的排序方法\n";cout<<"交换排序：\n冒泡排序是一种简单的交换排序，是一种稳定的排序方法\n快速排序是对冒泡排序的一种改进是一种不稳定的排序方法\n";cout<<"归并排序是一种不稳定的排序\n";}void main(){list s;int n;while(1){cout<< " \n ***主菜单*** "<<endl;cout<<" +++++++++++++++++++++++++++++++++++++"<<endl;cout<<" || ||"<<endl;cout<<" || 1.随机生成十个数||"<<endl;cout<<" || 2.随机生成三十个数||"<<endl;cout<<" || 3.随机生成五十个数||"<<endl;cout<<" || 4.随机生成一百个数||"<<endl;cout<<" || 5.对比||"<<endl;cout<<" || 6.键盘输入任意个数||"<<endl;cout<<" || 0=>退出||"<<endl;cout<<" || ||"<<endl;cout<<" ++++++++++++++++++++++++++++++++++++"<<endl;cout<<"请选择：\n";cin>>n;switch(n){case 1:s.play1(10);break;case 2:s.play1(30);break;case 3:s.play1(50);break;case 4:s.play1(100);break;case 5:s.play3();break;case 6:s.play2();break;case 0:exit(0);default:cout<<"输入错误!请重新输入";break;}}}。