数据结构课程设计--排序算法比较.doc

数据结构与算法设计课程设计报告 题目： 排序算法比较 学生姓名： 汪洪 学 号： 201120181805 班 级： 1121822 指导教师： 周华清 2013年1月10日目录需求分析3总体设计4详细设计5类的设计5现实部分8随机数赋值8结果输出8直接插入排序9冒泡排序10选择排序11快速排序13堆排序15二路归并排序18程序测试21总结251 需求分析本程序主要为了实现对各排序算法的性能比较。主要包括对直接插入排序，冒泡排序，选择排序，快速排序，堆排序二路归并排序六种排序算法在时间复杂度上的性能比较。基于此目的需要设定一个顺序表来产生一组数据，本程序用了一个长度为30000的long int型数组并用了以时间为随机种子产生了一组数组。用六个模块来实现各种排序功能并在各模块中完成计算排序所用的时间。并用一个数组保存各种排序所用的时间。为了比较各种排序的在时间上的优劣性将各个排序所用的时间进行比较并输出结果！2 总体设计Switch结构设定long数组开始 进行快速排序进行冒泡排序进行冒泡排序进行选择排序 二路归并排序堆排序冒泡排序直接插入排序快速排序选择排序 保存所需时间进行二路归并排序进行堆排序进行选择排序进行直接插入排序 结束对所有排序的时间进行从小到大的排序并输出结果获得所有排序所花费的时间（包括未switch结构中未被选中的排序）保存所需时间保存所需时间保存所需时间保存所需时间保存所需时间 3 详细设计1. 类的设计本程序功能只是为了比较各种排序算法在时间上的优劣。所以可以用一个类来完成的有的操作，固本程序只需定义一个类。为实现本程序功能定义一个类其中包括了一个长度300000的数组。并且为了实现各种排序功能应当设计功能函数分别实现各种类型的排序和排序后的结果。以下对这个类进行详细说明。类名：sortrather数据成员：long int aN 其中N为一个全局常量其值为30000，该成员用来保存一个用于保存一组数据用于排序。Long int time6该数组用于保存各种排序所用的时间，以便对种种排序所用时间进行比较。成员函数：1. void pubction（）实现功能：本函数的的作用是给数据成员 aN进行随机赋值。实现算法：用系统时间作为随机种子。再将随机函数对90000的取余赋给。aN.2. print()实现功能：将aN的前30个元素输出。实现算法：将数组元素一个一个的输出。3.void insertsort()实现功能：以直接插入排序算法完成对数组a的直接插入排序。实现算法：以当前元素以基准元素，将后面的元素与其进行比较。如果比当前元素大则直接插到当前元素后面。否则把当前元素后移并置当前元素为前一个元素。重复此步骤。4void bubblesort()实现功能：以冒泡的方式对数组aN进行排序。实现算法：从第N-1个数开始与前一个数比较使之小的在的前大的在后，直到第1个数，这样便找到了最小的用同样的方法找到第二小的数。3. void selectsort(long int a,long int n)实现功能：以选择排序的方法完成对aN的排序。实现算法：依次取数组aN中的第一个、第二个到第aN个，与数组中它所在位置后的其它元素进行比较并使a1,a2,.aN取余下元素的最小值。4. void quick(long int a,long int left,long int right)实现功能：用快递排序的方法来实现对aN从小到大的排序实现算法：先取a1作为基准点从a-1开始依次与基准点比较若a1大于其中的某个数则交换a1与这个数的值。并以该数为基准点从a2开始从复以上步骤真以基准点为界两边的数大小被分开。再对分好区间执行此步骤。5.void heapsort(long int a);实现功能：用堆排序对数组aN进行排序。实现算法：从N/2开始双数组进行移位使得对于数组中满足aia2*i,aia2*i+1.6. void mergesort(long int a);实现功能：用二路归并排序对数组aN进行排序。实现算法：先以N/2为间隔对数组aN进行直接插入排序。依次使N=N/2缩小间隔。最终作一次直接插入排序。实现部分对数组随机赋值void pubction()srand(time(NULL);for(long int i=0;iN;i+) ai=rand()%90000;输出数组前30个元素void print(long int a)int i;for(i=0;iW;i+)coutait;coutendl;直接插入排序void insertsort(long int a)long int i,j,temp;pubction(a);/cout初始数组是：n; /print(a);for(i=1;i=0;j-)if(tempaj)ppp0+;aj+1=aj;elsebreak;aj+1=temp;/cout直接排序后的数组是：n;/print(a);cout直接插入排序耗时： ppp0/100000毫秒endl;冒泡排序void bubblesort(long int a)long int i,j,temp;pubction(a);/cout初始数组是：n;/print(a);for(i=0;ii;j-)if(ajaj-1)ppp1+;temp=aj;aj=aj-1;aj-1=temp;/cout冒泡排序后的数组是：n;/print(a);cout冒泡排序耗时为： ppp1/100000毫秒6)pubction(a);for(i=0;in-1;i+)temp=ai;for(j=i+1;jaj)ppp2+;k=aj;aj=temp;temp=k;ai=temp;cout选择排序耗时为： ppp2/100000毫秒endl;elsefor(i=0;in-1;i+)temp=ai;strcpy(trtemp,sti);for(j=i+1;j=aj)strcpy(trt,stj);strcpy(stj,trtemp);strcpy(trtemp,trt);k=aj;aj=temp;temp=k;strcpy(sti,trtemp);ai=temp;ai/=100000;ai/=100000;快速排序void quick(long int a,long int left,long int right)long int i=left,j=right,temp;temp=ai;if(ji)while(ji)while(ajtemp)&(ij)j-;if(ij)ppp3+;ai=aj;i+;while(aitemp)&(ij)i+;if(ij)ppp3+;aj=ai;j-;ai=temp;quick(a,left,i-1);quick(a,i+1,right);void Quick(long int a)long int i=0,j=N-1;pubction(a);/cout初始数组是：n;/print(a);quick(a,i,j);/cout快速排序后数组是：n;/print(a);cout快速排序耗时为： ppp3/100000毫秒endl;堆排序void creatheap(long int a,long int i,long int n)long int j,temp;temp=ai;j=2*i+1;while(j=n)if(j=n)if(j+1=n)if(ajaj+1)j+;if(tempaj)ppp4+;ai=aj;i=j;j=2*i+1;else j=n+1;ai=temp;void heapsort(long int a)int temp,j;int n=N-1;pubction(a);/cout=0;i-)creatheap(a,i,n);for(j=n;j=1;j-)temp=a0;a0=aj;aj=temp;creatheap(a,0,j-1);/cout堆排序后的数组是:n;/print(a);cout堆排序耗时为： ppp4/100000毫秒aj)ck=aj;j+;elseck=ai;i+;k+;while(im)&(jn)while(aiaj)&(im)&(j=aj)&(im)&(j=m)while(j=n)while(im)ppp5+;ck=ai;k+;i+;for(long int p=l;pn;p+)ap=cp;void mergesort(long int a)long int cN,d=1,i=0;/cout初始数组为：n;pubction(a);/print(a);for(d;dN-1;d*=2)i=0;while(i=N-1)merge(a,c,i,N,N);else if(i+2*d=N-1)merge(a,c,i,i+d,N);else if(i+2*d=N-1)merge(a,c,i,i+d,i+2*d);i+=2*d;/cout经二路归并排序后的数组为：n;/print(c);cout二路规并排序耗时为:ppp5/100000毫秒endl;5. 程序测试菜单界面直接插入排序冒泡排序选择排序快速排序堆排序二路归并排序各种排序的比较由运行的结果可以看出在六个排序中快速排序的耗时最短，冒泡排序的耗时最长。其次可以看出快速排序，堆排序，二路归并排序，所花的时间均很少，而选择排序，冒泡排序，直接插入排序这些排序算法的时间花费都很大它们间相差三个数量级。可以看出一些算法在时间运作方面的出色。在本程序中还有一个值得注意的土方是在对所有排序算法耗时进行排序的时候又用了一个对时间排序的函数，这样做其际上没有做到代码重用的原则。可以用类中原本就存在的函数来实现这一功能。还有就是程序的所显示的时间并不是真正意义上的时间而是把每个排序算法的执行循环次数去除100000而得到了结果，所以不是非常精确。所以这个程序还不是非常完美！也由此得出学习是无止境的！6. 总结通过本次实验我不但复习了平时所学的知识，而且更加直观的认识到了一个道理，一个好的算法不仅仅要简单明了，而且还要考虑时间和空间的开肖，在本程序中，快速排序对30000个数排序仅用了1毫秒而冒泡排