七种排序算法的比较及每种排序的上机统计时间.docx

《七种排序算法的比较及每种排序的上机统计时间.docx》由会员分享，可在线阅读，更多相关《七种排序算法的比较及每种排序的上机统计时间.docx（34页珍藏版）》请在三一办公上搜索。

1、数据结构课程设计报告课题：排序算法的比较学院:信息学院班级：2011级电子信息工程1班小组成员:韦志东（组长）20111601310027夏琪20111601310028完成时间:2014-01-08教师:周铁目录1.3、设计任务书27271、课程分析11、选题要求利用随机函数产生30000个随机整数，利用直接插入排序、希尔排序，冒泡 排序、直接选择排序、快速排序、堆排序、归并排序的排序方法进行排序，并统 计每一种排序上机所花费的时间。1.2、选题的意义及背景排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任 意序列，重新排列成一个按关键词有序的序列。此实验通过对各种内部排序算

2、法进行比较，能使我们更好的掌握各种排序的 基本思想，掌握各种排序方法的算法实现，掌握各种排序方法的优劣分析及花费 的时间的计算，掌握各种排序方法所适应的不同场合。通过该题目的设计，可以 加深理解各种数据结构的逻辑结构、存储结构及相应上运算的实现，进一步理解 和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问 题，培养我们的动手能力。1.3、设计任务书（1）定义结构体，头文件，定义数组范围，大小。（2）依次描写七种排序的算法。（3）描写产生随机函数的算法。（4）描写菜单函数。（5）描写主函数，调用七种排序的算法。2、设计分析2.1原始资料用户输入记录的个数30000个，数据由

3、随机函数生成。2.2输出数据产生的随机数分别用冒泡排序、直插排序、希尔排序、选择排序、快速排序、 堆排序、归并排序这些排序方法进行排序，并统计每一种排序上机所花费的时间。3 .程序源代码及其注释#include stdio.h” #include stdlib.h” #include math.h” #include #include#defineMAX 60000 /*记录数组的个数*/#defineNUM 30000 /*实际输入数组的个数*/typedefint datatype;typedefstruct /*定义记录为结构体类型*/ int key;/*记录的关键词域*/dataty

4、pe other; /*记录的其它域*/ rectype;rectype *s1,sMAX;/*sMAX存放原始随机数，*s1取出原始数据后进行排序*/*直接插入排序算法如下*/void insert_sort(rectype *r) /*对数组r按递增顺序进行插入排序算法*/ int i,j,n=NUM;/*NUM为实际输入的记录数，是一个常量*/for(i=1;i=n;i+)/* iNUM条件很重要，NUM为实际记录数*/ r0=ri;/*r0为监视哨*/j=i-1;/*依次插入记录r1,，rNUM*/while(r0.key0) jump=jump/2; /*取步长 d(i+1) = d

5、(i)/2*/do change=0; /*设置交换标志，change=0表示未交换*/for(i=1;irm.key) /*记录交换*/ temp=rm.key;rm.key=ri.key;ri.key=temp;change=1; /*change=1 表示有交换 */*if*/*for*/ /*本趟排序完成*/while(change=1); /* 当 change=0 时终止本趟排序*/*while*/* 当增量 jump=1 且 change=0 时终止算法 */*SHELLSORT*/*冒泡排序算法如下*/void bubble_sort(rectype *r) /*从下往上扫描的

6、冒泡排序*/ int i,j,noswap=0,n=NUM;/*noswap为交换标志,NUM为实际输入记录数*/rectype temp;for(i=1;i=i;j-)/* 从下往上扫描*/if(rj.key=temp.key)&(ij)j-;/*从右往左扫描，查找第一个关键词小于temp的记录*/if(ij) ri+=rj; /*交换 ri和 rj*/while(ri.key=temp.key)&(ij)i+;/*从左往右扫描，查找第一个关键词大于temp的记录*/if(ij) rj-=ri; /*交换 ri和 rj*/while(i!=j);/*i=j,z则一次划分结束，基准记录达到其最

7、终位置*/ri=temp; /*最后将基准记录tem p定位*/return(i);/*PARTITION*/void quick_sort(rectype *r,int hs,int ht)/*对 rhs到 rht 进行快速排序 */ int i;if(hsht) /*只有一个记录或无记录时无需排序*/ i=partition(r,hs,ht); /*对 rhs到 rht 进行一次划分 */quick_sort(r,hs,i-1); /*递归处理左区间*/quick_sort(r,i+1,ht); /*递归处理右区间*/ /*QUICK_SORT*/*直接选择排序算法如下*/void sel

8、ect_sort(rectype *r) rectype temp;int i,j,k,n=NUM; /*NUM为实际输入记录数*/for(i=1;i=n;i+)/*做n-1 趟选择排序 */ k=i;for(j=i+1;j=n;j+)/*在当前无序区中选择关键词最小的记录rk*/ if(rj.keyrk.key) k=j;if(k!=i) temp=ri;/* 交换记录 ri和 rk*/ri=rk;rk=temp;/*for*/*SELECT_SORT*/*堆排序算法如下*/void shift(rectype *r,int i,int m)/*堆的筛选算法，在数组中ri到rm中，调整堆 r

9、i*/ int j; rectype temp;temp=ri; j=2*i;while (j=m)/*j=m,r2*i是ri的左孩子*/ if(jm)&(rj.keyrj+1.key)j+; /*j指向ri的左右孩子中关键词较大者*/if(temp.key0;i-)/*建 立初始堆*/shift(r,i,n);for(i=n;i1;i-)/*进行n-1趟筛选，交换，调整，完成堆排序*/ temp=r1;/*将堆顶元素r1与最后一个元素交换位置*/r1=ri;ri=temp;shift(r,1,i-1);/*将数组元素r1到ri-1重新调整成为一个新堆*/ /*FOR*/*HEAP_SORT*

10、/*二路归并排序算法如下*/void merge(rectype *a,rectype *r,int low,int mid,int high) int i,j,k;i=low;j=mid+1;k=low;while(i=mid)&(j=high)/*将两个相邻有序子表进行合并*/ if(ai.key=aj.key)/*取 两表中小者复制*/rk+=ai+;else rk+=aj+;while(i=mid) rk+=ai+;/*复制第一个有序子表的剩余记录*/ while(j=high) rk+=aj+;/*复制第二个有序子表的剩余记录*/ /*MERGE*/void merge_pass(r

11、ectype *r,rectype *r1,int length) int i=1,j,n=NUM;while (i+2*length-1)=n)/*归并若干长度为2*length的两个相邻有序子表*/ merge(r,r1,i,i+length-1,i+2*length-1);i=i+2*length;/*i指向下一对有序子表的起点*/if(i+length-1n)merge(r,r1,i,i+length-1,n);/*处理表长不足 2*length 的部分 */else for(j=i;j=n;j+)r1j=rj;/*将最后一个子表复制到口中*/*MERGEPASS*/void merg

12、e_sort(rectype *r) int length;rectype r1MAX;length=1;/*归并长度从1开始*/while(lengthNUM) merge_pass(r,r1,length);/*一趟归并，结果存放在口中*/length=2*length;/*归并后有序表的长度加倍*/merge_pass(r1,r,length);/*再次归并，结果存放在匕中*/length=2*length;/*再次将归并后有序表的长度加倍*/*MERGE_SORT*/void creat_randnum(int *a )/*产生给定个数和范围的随机整数函数*/ int i;int ra

13、nge=30000;srand(time(NULL);for(i=1;i=NUM;i+)ai=rand(); /*调用rand生成随机整数*/printf(nnttt排序前的原始随机整数为:nnt);for(i=1;i=NUM;i+) printf(%6d”,ai); /*输出随机整数 */if(i%10=0) printf(nt);printf(n)；/*CREAT_RANDNUM*/void create() /*产生NUM个随机整数并保存到记录数组、中*/ int bMAX;int range=30000,i;creat_randnum(b); /*调用随机整数生成函数，结果存放在数组b

14、中*/for(i=1;i=NUM;i+)si.key=bi;/*将随机整数存放到数组、中*/s1=s;/*s1指向s,以便保存原始数据*/*CREAT*/void print_record(rectype *r)/*记录数组的输出函数 */ int i;printf(nttt排序后的有序随机整数:nnt);for(i=1;i=NUM;i+)printf(%6d”,ri.key);if(i%10=0) printf(nnt);getchar();getchar();/*PRINTRECORD*/int menu_select()/*主 菜单选择模块 */ char c; int kk;syste

15、m(cls);/*清 屏函数 */printf(内排序算法的比较主控模块:nn);printf(ttt1.直接插入排序n);printf(ttt2.printf(ttt3.printf(ttt4.printf(ttt5.printf(ttt6.printf(ttt7.printf(ttt0.希尔排序n）；冒泡排序n）；快速排序n）；直接选择排序n）；堆排序n）；二路归并排序n）；退出n）；do printf（nttt请按数位07键选择功能:）；c=getchar()； kk=c-48；while (kk7);return(kk);/*MENU_SELECT*/main() /*算法比较一主程序

16、模块*/double time1, time2, time3, time4, time5, time6, time7;clock_t start, finish;int kk;do kk=menu_select(); /*进入主菜单选择模块*/if(kk!=0) create();/*建立记录数组 */switch(kk) case 1: start=clock();insert_sort(s1)；finish=clock()；Jbreak;time1 = (double)(finish - start)/ CLOCKS_PER_SECprintf(直接插入排序耗时%三secondsn”, t

17、ime1);case 2: start=clock();shell_sort(s1)；finish=clock();time2 =(double)(finish - start)/ CLOCKS_PER_SECprintf(希尔排序耗时%三 secondsn”, time2); break;case 3: start=clock();bubble_sort(s1);finish=clock();time3 = (double)(finish - start)/ CLOCKS_PER_SEC ;printf(冒泡排序耗时%三 secondsn”, time3); break;case 4: st

18、art=clock();quick_sort(s1,1,NUM);finish=clock();time4 = (double)(finish - start)/ CLOCKS_PER_SEC ;printf(快速排序耗时%三 secondsn”, time4); break;case 5: start=clock();select_sort(s1);finish=clock();time5 = (double)(finish - start)/ CLOCKS_PER_SEC ;printf(直接选择排序耗时%三 secondsn”, time5); break;case 6: start=c

19、lock();heap_sort(s1);finish=clock();time6 = (double)(finish - start)/ CLOCKS_PER_SEC ;printf(堆排序耗时 %f secondsn”, time6); break;case 7: start=clock();merge_sort(s1);finish=clock();time7 = (double)(finish - start)/ CLOCKS_PER_SEC ;printf(二路归并排序耗时 %f secondsn”, time7); break;case 0:exit(0);print_record

20、(s1);while (kk!=0);/*MAIN*/4 .测试结果主控模块:1=1 回内排序算法的比较入序序序择并 插排排排选序归 接尔泡速接排路出 直希冒快直垠二退 12345670请按数字。一了键选择功能:选择直接插入排序:内排序算法的比较请按数字。一了键选择功能:1排序前的原始随机整数为: , DACbDebuggg 旧 xb入序序序择并 插排排排选序归 接尔泡速接排路出 直希冒快直堆二退 123456701889 24052 25174 117728039 5557 2943 5623 14804 18132 25443 19380 249110169 9518 22121 2485

21、9 25231 19628 12G55 1345 15722 24250 27032 18707 31649 4014 4916 3300 20151 1557G 20801 909 7622 27763 2110 13650 1H000 9686 20133 16880 26740 2301 10058 32194 28270 7129 309175588 221 GG 5025 10736 23879 224 21150 G10 6884 3159G 29733 12815 9450 14473 27758 22431 19474 25642 7695 51046060 10782 308

22、91 11348 22784 11092 30747 6089 10010 19941 8078 5319 5245 4639 425 22033 32016 29907 30257 8616 7195 182G0 32489 29847 3114 3111 24534 20577 22047 16451 1652。 14744 21045 523424441 30435 26054 1471 166412093 7611 140304517 27659 18547 16029 15618 12879 8891 17152 25399311364094 19357 20188 29803 26

23、7009205 2828H 8110 1856 19467 113914357 10729 11763 3052 20631 15253 21830 3000 3735 28019 31835 13316 29648 9402 9295 7056 9716 5865 206明3095 15983 29215 10347 27928 20999 13981 10857 27227 25743 9513 10254 13959 1289 1207 7523 6157 141348579 11396排序前本有30000个随机数显示，但数据太多，只截一部分图来表示。排序后也一样，应有30000个排好顺

24、序的整数显示，但由于数据过多，也只截一部分图来表示。(2)选择希尔排序：排序前本有30000个随机数显示，但数据太多，只截一部分图来表示。排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一 部分图来表示。由图可知，希尔排序耗时0026000秒* D:CbDebuggg.exe内排序算法的比较一一主控模块:序kF君入序序序择并插排排排选序归序 序- - - -希冒快直堆二退2 3 4 5 G 7 0请按数字。一了键选择功能： 请按数字。一了键选择功能:2 排序前的原始随机整数为:3561 13860 4440 8160 9456 4662 321 65 2H80 2096

25、2 15311 22293 2明26 1385 11861 26066 32212339194129039 9918 17417902 120472112 31198 23399436。25034 12054 26797 17724 1003431947 32254 5762 3265 23927 3392 15829 30324 23311 2564165场 27717 8325 22095 14379 14637 1038 8686 19986 16596 16423 505 171 26 1932 30080 11829 17747 7504 30788 12380 8781 11699

26、1147426733742 12413 4537 11G134149 17755 204314682 30903 8938 180693722 30GG5 84308777 27231 1848 17224 26384 29431177 27676 22769 4557 26190 26973 3555 28527 26014 9287 12384 31456 24286 5438 9237 23945 7221 32000 30350 30894 17014 27627 18536 228174975 217136931 625 764 12615 9307 29GO0 24624 2509

27、 12057 6592 19113 3966 12793 15066 7550 241611504488861825216G329241225G53081230757235512549831163236142709116326269203118265 13935 5160 15533 32385 321G7 195G7 13649 29096 13391 31855 25600 24263 291458426 30196(3)选择冒泡排序：排序前本有30000个随机数显示，但数据太多，只截一部分图来表示。排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一 部分图来表示。

28、 D:CbDebuggg.exe1内排序算法的比较-主控模块:序kF君入序序序择并插排排排选序归序 序- - - -希冒快直堆二退2 3 4 5 G 7 0请按数字。一了键选择功能： 请按数字。一了键选择功能：3排序前的原始随机整数为:4234 16159 29506 3763 24542580G 12434 21827 73122953643851214321 8明31358 1877 297929338 1886 19617 5944 1G4G7 5804 18945 21291 161685086 26793 20978 13916 23887 209GG 2522G9182 5343

29、18624 222417129 8049 22330 12H3S 26773 29094 29882 227598294 19825 7676 25944194599357 232016315 24577 1395 5672 11610 19618 25586 13177 24826 1930310934 12109 275186356 19507 30066 27562 19852 46 26855 26801 943 19919 15767 30875 646。 25497 28汹 257231252 27166 18965 6540 23636 1G553 14352 022 26710

30、 25319 16032 19995 25759 311824437 1774030957 18170 22935 2938 22898 2145 1816 1471 17064 1146。 17933 13477 162557104 583 4348265明 27901 19651 1289G 5795 1072 2775G 16331 27086 28721 5659 22355 9404 21164 29407 1204G8559 25566 28759 146G8 283243219 27996 25827 9532 1985784792582 19615 14422 19195950

31、819715 10353 101797326 28758 250GG7994 17618 9925 241701 74012134 252381530 10353 5870FD选择快速排序：排序前本有30000个随机数显示，但数据太多，只截一部分图来表示。排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一 部分图来表示。请按数字。一了键选择功能： 请按数字。一了键选择功能:4内排序算法的比较主控模块:序 序序 入序序序择并 插排排排选序归 接尔泡速接排路出 直希冒快直垠二退 1234567049072805419186 285341238 209581676213310

32、207531165184582755911199 100293572 271Q148852240994786771218043019431487 2641623623 33142158457702292515199321331969845Q 288Q29942 2862343813177767331886282213119423099 327322398 2088937912283274072513214182370712706 228421248 36751311353111664117965254712584429831 2698716794 28526291793Q88725179291

33、891917477032732Q 212893078 1313637093015220898215862643Q11383Q234 915714224 306523778934628281235221Q9921954132548 65762388 13313247931808214216218119245164582Q456 86Q6630 58741885224973185622947386016922178Q1 938120043 1301732095797614318114369454157798263 781727620 15194139736014375326213180862Q97

34、817556 948714504 106924158272611721366831045524208973 1543626583 15627289601849632120122812359676504482 1Q56929483 2619419751327003147314311排序前的原始随机整数为:选择直接选择排序：排序前本有30000个随机数显示，但数据太多，只截一部分图来表示。排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一 部分图来表示。由图可知，直接选择排序耗时1528000秒* D:CbDebuggg.exe,内排序算法的比较-一主控模块:1.直接插入排

35、序2.希尔排序3.冒泡排序4.快速排序5. 直接选择排序6. 堆排序7.二路归并排序0.退出请按数字。一了键选择功能： 请按数字。一了键选择功能:5排序前的原始随机整数为:572661601387763451525235271155532228177162809614102584730265162Q32452Q81718761268521Q23713223351216517318881760718953265562884512399802320Q4231706316443173229QQ13744238762491165201Q126391116667214601472111172137412

36、26321821Q271126566213492244720717171071752510495124802568126701170883094723541247052022816Q532839434852354820941474820337273941198322229810828893283775501502111073303981472919Q932856627738772185932226644331358522312752967723QQ759Q2215068145921447512595291351611116Q36370525992128999388574511701380828

37、78Q3787133329913154181346823865145361 7877811211916368225744287055521137061Q9313127213420111091385425652224362799297432744931015509923782167152983877122695114955206431965018688152651692856796988826719386296601205524848Q302Q11Q36831968894033143722762293831868822933128053234531719290081786828001选择堆排序:

38、排序前本有30000个随机数显示，但数据太多，只截一部分图来表示。排序后也一样，应有30000个排好顺序的整数显示，但由于数据过多，也只截一部分图来表示。由图可知，堆排序耗时0.008000秒 D:CbDebuggg.exe排序算法的比较-主控模块:1. 直接插入排序2. 希尔排序3. 冒泡排序4. 快速排序5. 直接选择排序6. 堆排序7. 二路归并排序0.退出请按数字。一了键选择功能： 请按数字。一了键选择功能：6排序前的原始随机整数为:6125674630618257181471911068308262780514316952882511221114642142423713614413756137374209324171994846482868921420310443223970482358414748166524606216542738221004412626138135684460117102386513793228643245022363189931368715165