南邮数据结构上机实验四内排序算法的实现以及性能比较

实验报告（2015/2016学年第二学期）课程名称数据结构A实验名称内排序算法的实现以及性能比较实验时间2016年5月26日指导单位计算机科学与技术系指导教师骆健学生姓名耿宙班级学号B14111615学院(系)管理学院专业信息管理与信息系统实习题名:内排序算法的实现及性能比较班级B141116姓名耿宙学号B14111615日期2016.05.26一、问题描述验证教材的各种内排序算法，分析各种排序算法的时间复杂度；改进教材中的快速排序算法，使得当子集合小于10个元素师改用直接插入排序；使用随即数发生器产生大数据集合，运行上述各排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。系统时钟包含在头文件“time.h”中。二、概要设计文件Sort.cpp中包括了简单选择排序SelectSort()，直接插入排序InsertSort()，冒泡排序BubbleSort()，两路合并排序Merge()，快速排序QuickSort()以及改进的快速排序GQuickSort()六个内排序算法函数。主主函数main的代码如下图所示：三、详细设计1.类和类的层次设计在此次程序的设计中没有进行类的定义。程序的主要设计是使用各种内排序算法对随机生成的数列进行排列，并进行性能的比较，除此之外还对快速排序进行了改进。下图为主函数main的流程图：main()2.核心算法1)简单选择排序：简单选择排序的基本思想是：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。2)直接插入排序：插入排序的思想是将一组无序的元素分别插入一个已经有序的的数组里，并保证插入后的数组也是有序的。当所有无序组的元素都插入完毕时，一个有序数组构造完成。数组n[1…r]为初始的一个无序数组（为了直观起见，我们这里设定数组从1开始，而不是0），则n[1]默认为只有一个元素的有序数组，n[2]插入只有n[1]构成的有序数组中，则此时有序数组的元素数量变为2。以此类推，到第i个元素时，前i-1个元素已经是有序的，此时只需将第i个元素插入到有序数组中并使之保持有序。如此直至最后一个元素插入完毕，整个插入排序完成。3)冒泡排序：冒泡排序每遍历一次数组，便将最大的元素放到数组最后边。下次遍历将次大的元素放到数组倒数第二位，依次类推，直至将最小的元素放到最前边，此时冒泡排序完成。4)快速排序：快速排序是采用了分而治之的思想，但与合并排序有所不同的是快速排序先“工作”（这里是分割或partition），再递归。快速排序的主要思想是保证数组前半部分小于后半部分的元素，然后分别对前半部分和后半部分再分别进行排序，直至所有元素有序。5)两路合并排序两路合并排序算法的基本思想是：将待排序元素平分成大小大致相同的两个子序列，然后对每个子序列分别使用递归的方法进行两路合并排序，直到子序列长度变为1，最后利用合并算法将得到的已排序好的两个子序列合并成一个有序的序列。两路合并排序算法的核心部分是将子问题的解组合成原问题解得合并操作。常用的操作是新建一个序列，序列的大小等于要合并的两个子序列的长度之和。比较两个子序列中的最小值，输出其中较小者到新建的序列中，重复此过程直到其中一个子序列为空。如果另一个子序列中还有元素未输出，则将剩余元素依次输出到新建序列中即可。最终得到一个有序序列。此外还对快速排序进行了改进，改进算法流程图如下所示：GQuickSort()四、程序代码templateclassTvoidGQuickSort(TA[],intn)//改进的快速排序{GQSort(A,0,n-1);}templateclassTvoidGQSort(TA[],intleft,intright){inti,j;if(right=9){if(leftright){i=left;j=right+1;do{doi++;while(A[i]A[left]);doj--;while(A[j]A[left]);if(ij)Swap(A[i],A[j]);}while(ij);Swap(A[left],A[j]);QSort(A,left,j-1);QSort(A,j+1,right);}}else{InsertSort(A,right-left+1);return;}}五、测试和调试1.测试用例和结果测试结果如下图1)生成随机数据2)简单选择排序及其所需时间3)直接插入排序及其所需时间4)冒泡排序及其所需时间5)快速排序及其所需时间6)改进快速排序及其所需时间7)两路合并排序及其所需时间2.结果分析简单选择排序的最好、最坏的平均情况的时间复杂度都为O(n2),是不稳定的排序方法；直接插入排序的最好情况的时间复杂度为O(n)，最坏情况的时间复杂度为O(n2)；冒泡排序最好情况的时间复杂度为O(n)，最坏情况的时间复杂度为O(n2)，是稳定的排序方法；快速排序最好情况的时间复杂度为O(n2)，最坏情况的时间复杂度为O(nlog2n)，是不稳定的排序方法；两路合并排序的时间复杂度为O(nlog2n)，是稳定的排序方法。六、实习小结在这次实验中,我们对内部排序算法进行了比较以及性能分析,通过这次实验,我们加深了对内部排序算法的理解,对内部排序算法的基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。通过这次实验，我明白了，没有总是最好的排序方法。对于一般列表，快速排序、希的性能较好。通过本次实验，我深刻体会到问题解决方案的重要性，算法效率分析的必要性。法时。附录：#includeiostream.h#includestdlib.h#includetime.htemplateclassTvoidSwap(T&a,T&b){Ttemp=a;a=b;b=temp;}templateclassTvoidSelectSort(TA[],intn)//简单选择排序{intsmall;for(inti=0;in-1;i++){small=i;for(intj=i+1;jn;j++)if(A[j]A[small])small=j;Swap(A[i],A[small]);}}templateclassTvoidInsertSort(TA[],intn)//直接插入排序{for(inti=1;in;i++){intj=i;Ttemp=A[j];while(j0&&tempA[j-1]){A[j]=A[j-1];j--;}A[j]=temp;}}templateclassTvoidBubbleSort(TA[],intn)//冒泡排序{inti,j,last;i=n-1;while(i0){last=0;for(j=0;ji;j++)if(A[j+1]A[j]){Swap(A[j],A[j+1]);last=j;}i=last;}}templateclassTvoidQuickSort(TA[],intn)//快速排序{QSort(A,0,n-1);}templateclassTvoidQSort(TA[],intleft,intright){inti,j;if(leftright){i=left;j=right+1;do{doi++;while(A[i]A[left]);doj--;while(A[j]A[left]);if(ij)Swap(A[i],A[j]);}while(ij);Swap(A[left],A[j]);QSort(A,left,j-1);QSort(A,j+1,right);}}templateclassTvoidGQuickSort(TA[],intn)//改进的快速排序{GQSort(A,0,n-1);}templateclassTvoidGQSort(TA[],intleft,intright){inti,j;if(right=9){if(leftright){i=left;j=right+1;do{doi++;while(A[i]A[left]);doj--;while(A[j]A[left]);if(ij)Swap(A[i],A[j]);}while(ij);Swap(A[left],A[j]);QSort(A,left,j-1);QSort(A,j+1,right);}}else{InsertSort(A,right-left+1);return;}}templateclassTvoidMerge(TA[],inti1,intj1,inti2,intj2)//两路合并排序{T*Temp=newT[j2-i1+1];inti=i1,j=i2,k=0;while(i=j1&&j=j2){if(A[i]=A[j])Temp[k++]=A[i++];elseTemp[k++]=A[j++];}while(i=j1)Temp[k++]=A[i++];while(j=j2)Temp[k++]=A[j++];for(i=0;ik;i++)A[i1++]=Temp[i];delete[]Temp;}templateclassTvoidMergeSort(TA[],intn){inti1,j1,i2,j2;intsize=1;while(sizen){i1=0;while(i1+sizen){i2=i1+size;j1=i2-1;if(i2+size-1n-1)j2=n-1;elsej2=i2+size-1;Merge(A,i1,j1,i2,j2);i1=j2+1;}size*=2;}}intmain(){clock_tstart,finish;srand(time(NULL));intn=1000;int*a=newint[n];int*b=newint[n];int*c=newint[n];int*d=newint[n];int*e=newint[n];int*f=newint[n];cout待排序序列为:endl;for(inti=0;in;i++){a[i]=rand()%91;couta[i];b[i]=a[i];c[i]=a[i];d[i]=a[i];e[i]=a[i];f[i]=a[i];}coutendl;start=clock();SelectSort(a,n);cout经过简单选择排序后的序列为:endl;for(i=0;in;i++)couta[i];coutendl;finish=clock();cout开始时间为:start结束时间为:finish持续时间为:(double)(finish-start)/CLOCKS_PER_SECendl;start=clock();InsertSort(b,n);cout经过直接插入排序后的序列为:endl;for(i=0;in;i++)coutb[i];coutendl;finish=clock();cout开始时间为:start结束时间为:finish持续时间为:(double)(finish-start)/CLOCKS_PER_SECendl;start=clock();BubbleSort(c,n);cout经过冒泡排序后的序列为:endl;for(i=0;in;i++)coutc[i];coutendl;finish=clock();cout开始时间为:start结束时间为:finish持续时间为:(double)(finish-start