20112915谢宸果排序算法比较

课程设计报告设计题目：比较快速排序、堆排序、希尔排序、冒泡排序、归并排序的时间性能学生姓名：谢宸果专业：信息安全班级：2011级1班学号：20112915指导教师：张玉红完成日期：2012年7月5日合肥工业大学计算机与信息学院（一）题目要求（1）时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。（2）实验数据应具有说服力，包括：规模范围要大（如从100到10000）数据的初始特性类型要多，因而需要具有随机性；实验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来实验。实验结果要能以清晰的形式给出，如图、表等。（3）算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。（4）实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。（5）要给出实验的方案及其分析。（二）设计数据储存：根据题目要求，比较这些算法需要用到共同的数据，那么需要用一个线性表来储存这些数据，所以，需要在程序的前面建立一个线性表并初始化。然后是以上几种排序算法的介绍：快速排序：它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。希尔排序：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成（n除以d1）个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2d1重复上述的分组和排序，直至所取的增量dt=1(dtdt-l…d2d1)，即所有记录放在同一组中进行直接插入排序为止。冒泡排序：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。归并排序：归并排序时一种基于归并方法的排序。所谓归并是指将两个或者两个以上的有序表合并成一个新的有序表。可以这样实现：首先将整个表看成n个有序子表，每个子表的长度为1，然后两两归并，得到n/2个长度为2的有序子表。然后再两两归并，得到n/4个长度为4的有序子表，依次类推，直至得到一个长度为n的有序表为止。堆排序：利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。其基本思想为(大顶堆)：1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无须区；2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]=R[n];3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。属性和方法定义类名成员类别类型成员名描述属性intm记录元素的比较次数intn记录元素的移动次数IntLen顺序表的长度Intdata[MAXSIZE]顺序表数据SeqListL顺序表方法VoidBubbleSort(SeqListL)冒泡排序算法Voidshellsort(SeqListL)希尔排序算法VoidPartition(SeqList&L,intlow,inthigh)快速排序算法Voidmegre(SeqList&L,SeqList&R,intl,intr,intmiddle)归并排序算法voidbj(SeqListL)比较两个排序算法的时间性能（三）用户手册①程序运行时，首先提示用户录入数据。②用户根据需要选择合适的排序方式对数据进行排序。③用户也可以选择方式6对两个排序方式进行比较（四）调试及测试由于几种算法本身的特点，我们选择用线性表储存数据，这样比较简便和简单。运行实例：初始化成功!1数据录入2冒泡排序3希尔排序4快速排序5归并排序6两种排序的比较请选择需要的操作：1请输入待排序的元素的个数：3请输入待排序的数据：-2176-19283698182379871数据录入2冒泡排序3希尔排序4快速排序5归并排序6两种排序的比较请选择需要的操作：2冒泡排序前的信息：-2176-1928369818237987排序后的信息：-19283698-217618237987冒泡排序的元素的比较次数为：5元素的移动次数为：11数据录入2冒泡排序3希尔排序4快速排序5归并排序6两种排序的比较请选择需要的操作：6输入第一种排序的方式3希尔排序前的信息：-2176-1928369818237987排序后的信息：-19283698-217618237987希尔排序的元素的比较次数为：1元素的移动次数为：1输入第二种排序方式：4快速排序的结果为：-19283698-217618237987快速排序的元素的比较次数为：9元素的移动次数为：71数据录入2冒泡排序3希尔排序4快速排序5归并排序6两种排序的比较请选择需要的操作：进一步改进:①目前程序的操作界面看起来太繁琐，选项提示不断出现，使操作界面看起来很乱，可以考虑修改部分函数来加以优化。②较结果并没有直接显示出来，因为在设计程序的时候比较次数和移动次数都是用相同的字母来表示的，需要比较的话则需要添加新的变量。除此之外，对于比较结果，有些比较次数多但是移动次数少，有些移动次数多但是比较次数少，因此我也不是很清楚这个时间性能哪个应该算更好一些。附录源程序/*给出一组实验来比较下列排序算法的时间性能：快速排序、堆排序、希尔排序、冒泡排序、归并排序*/#includeiostream#includestring.h#includefstream#defineMAXSIZE100usingnamespacestd;typedefintDataType;intm=0,n=0;typedefstruct{DataTypedata[MAXSIZE+10];intlen;//顺序表的长度}SeqList;voidInit_SeqList(SeqList&L)//初始化{cout初始化成功!endl;L.len=0;}voidset_SeqList(SeqList&L)//输入线性表的信息{cout请输入待排序的元素的个数：endl;cinL.len;cout请输入待排序的数据:endl;for(inti=1;i=L.len;i++){cinL.data[i];}}voidoutput_SeqList(SeqList&L)//输出线性表的信息{cout请输出线性表的元素:endl;for(inti=1;i=L.len;i++){coutL.data[i];}}voidBubbleSort(SeqListL)//冒泡排序{inti,j,flag=1;m=0,n=0;DataTypex;cout冒泡排序前的信息：endl;for(i=1;i=L.len;i++){coutL.data[i];}coutendl;for(i=1;((i=L.len)&&(flag==1));i++){m++;flag=0;for(j=1;jL.len-i+1;j++){m++;if(L.data[j]L.data[j+1]){n++;x=L.data[j];L.data[j]=L.data[j+1];L.data[j+1]=x;flag=1;}}}cout排序后的信息：endl;for(i=1;i=L.len;i++){coutL.data[i];}coutendl;cout冒泡排序的元素的比较次数为：m元素的移动次数为：nendl;}voidshellsort(SeqListL)//希尔排序{inti,j,gap,t;m=0,n=0;cout希尔排序前的信息：endl;for(i=1;i=L.len;i++){coutL.data[i];}coutendl;gap=(L.len)/2;//置增量初值while(gap0){m++;for(i=gap+1;i=L.len;i++){j=i-gap;while(j0)if(L.data[j]L.data[j+gap]){n++;t=L.data[j];L.data[j]=L.data[j+gap];L.data[j+gap]=t;j=j-gap;}elsej=0;}gap=gap/2;//减少增量}cout希尔排序的结果为endl;for(i=1;i=L.len;i++){coutL.data[i];}coutendl;cout希尔排序的元素的比较次数为：m元素的移动次数为：nendl;}intPartition(SeqList&L,intlow,inthigh)//快速算法{L.data[0]=L.data[low];intkey=L.data[low];while(lowhigh){m++;while(lowhigh&&L.data[high]=key){high--;m++;}L.data[low]=L.data[high];n++;while(lowhigh&&L.data[low]=key){low++;m++;}L.data[high]=L.data[low];}L.data[low]=L.data[0];n++;//记录returnlow;//返回空缺位置}voidQSort(SeqList&L,intlow,inthigh){intpivotloc;if(lowhigh){pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);//对低子表递归排序QSort(L,pivotloc+1,high);//对高子表递归排序}}voidmegre(SeqList&L,SeqList&R,intl,intr,intmiddle)//归并排序算法左l右r{//intm=0,n=0;for(intj=l;j=r;j++){m++;R.data[j]=L.data[j];}inttop1=l;//左inttop2=middle+1;//右inti=l;//从左面开始while((top1=middle)&&(top2=r)){m++;if(R.data[top1]R.data[top2]){n++;L.data[i++]=R.data[top1++];m++;}else{m++;L.data[i++]=R.data[top2++];}}while(top1=middle){m++;L.data[i++]=R.data[top1++];}while(top2=r){m++;L.data[i++]=R.data[top2++];}}voidmergesort(SeqList&L,SeqList&R,intl,intr){if(lr){intmiddle=(l+r)/2;mergesort(L,R,l,middle);mergesort(L,R,middle+1,r);megre(L,R,l,r,middle);}}voidgb(S