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

1、数据结构课程设计报告课题：排序算法的比较学院:信息学院 班级:2011级电子信息工程1班 小组成员：韦志东（组长） 20111601310027夏琪20111601310028完成时间:2014-01-08 教师:周铁11 1、课程分析1.11.1、选题.2.2.1.21.2、选题的意义及背景 .2.1.31.3、设计任务书. 2 22 2、设计分析5 5、总结& &参考文献. 27277 7、小组人员分工.27271、课程分析1.11.1 选题要求利用随机函数产生 3000030000 个随机整数，利用直接插入排序、希尔排序，冒泡 排序、直接选择排序、快速排序、堆排序、归并排

2、序的排序方法进行排序，并统 计每一种排序上机所花费的时间。1.21.2、 选题的意义及背景排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任 意序列，重新排列成一个按关键词有序的序列。此实验通过对各种内部排序算法进行比较，能使我们更好的掌握各种排序的 基本思想，掌握各种排序方法的算法实现，掌握各种排序方法的优劣分析及花费 的时间的计算，掌握各种排序方法所适应的不同场合。 通过该题目的设计，可以 加深理解各种数据结构的逻辑结构、 存储结构及相应上运算的实现，进一步理解 和熟练掌握课本中所学的各种数据结构，学会如何把学到的目录2.12.1、原始数据.错误！未定义书签2.22.2、输

3、出数据.错误！未定义书签2.32.3、程序流程图.3.3.3 3、程序源代码及注释.3 34 4、测试结果.错误！未定义书签26262知识用于解决实际问 题，培养我们的动手能力。1.31.3、 设计任务书（1 1）定义结构体，头文件，定义数组范围，大小。（2 2）依次描写七种排序的算法。（3 3）描写产生随机函数的算法。（4 4）描写菜单函数。（5 5）描写主函数，调用七种排序的算法。2、设计分析2.12.1 原始资料用户输入记录的个数 3000030000 个，数据由随机函数生成。2.22.2 输出数据产生的随机数分别用冒泡排序、直插排序、希尔排序、选择排序、快速排序、 堆排序、归并排序这些

4、排序方法进行排序，并统计每一种排序上机所花费的时间。2.32.3 程序流程图主程序产生 1 1 组随机数3输出排序上机所花费的时间3 3 程序源代码及其注释#i nclude stdio.h#in elude stdlib.h#in elude math.h#in clude#in clude#define MAX 60000 /*记录数组的个数 */ #defi ne NUM 30000 /* 实际输入数组的个数 */直接冒泡排序ShellShell排序插入排序二路归并堆排排序序快速排序排序直接选择将随机数保存在数组中4typedef int datatype;typedef struct

5、/*定义记录为结构体类型*/ int key; /*记录的关键词域*/datatype other; /*记录的其它域*/ rectype;rectype *s1,sMAX;/*sMAX存放原始随机数，*s1 取出原始数据后进行排序*/对数组 r 按递增顺序进行插入排序算法*/为实际输入的记录数，是一个常量*/条件很重要，NUM 为实际记录数*/为监视哨*/依次插入记录 r1,rNUM*/查找 ri合适的位置*/将记录关键词大于 ri.key 的记录后移*/将记录 ri插入到有序表的合适的位置上*/*希尔排序算法如下*/取增量为 d(i+1)=d(i)/2的希尔排序的算法*/ int i,n,

6、jump,change,temp,m; /*change为交换标志， jump 为增量步长 */jump=NUM; n=NUM; /*NUM为顺序表的实际长度 */while(jump0) jump=jump/2; /* 取步长 d(i+1)=d(i)/2*/do change=0; /*设置交换标志， change=0 表示未交换*/for(i=1;irm.key) /*记录交换*/*直接插入排序算法如下*/void in sert_sort(rectype *r) /* int i,j, n=NUM; /*NUMfor(i=1;i=n;i+)/* iNUM rO=ri;/*r0j=i-1;

7、/*while(rO.keyrj.key) /*rj+1=rj-;/*rj+1=r0;/*/*INSERTSORT*/void shell_sort(rectype *r) /* temp=rm.key;5rm.key=ri.key;ri.key=temp;change=1; /*change=1表示有交换 */怖/*for*/ /*本趟排序完成*/while(change=1); /*当 change=0 时终止本趟排序 */*while*/* 当增量 jump=1 且 change=0 时终止算法 */*SHELLSORT*/*冒泡排序算法如下*/void bubble_sort(rect

8、ype *r) /*从下往上扫描的冒泡排序*/ int i,j,no swap=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*/ri=temp; /*最后将基准记录 temp 定位*/return(i);/*PARTITION*/void quick_sort(rectype *r,i nt hs,i nt ht)/*

9、 int i;/*QUICK_SORT*/*直接选择排序算法如下*/void select_sort(rectype *r) rectype temp;int i,j,k, n=NUM; /*NUM为实际输入记录数 */for(i=1;i=n;i+)/*做 n-1 趟选择排序 */ k=i;if(rj.keyrk.key) k=j;if(k!=i) temp=ri;/*ri=rk;i+;/*从左往右扫描，查找第一个关键词大于temp 的记录*/if(ij) rj-=ri; /*交换 ri和 rj*/while(ri.key=temp.key) &(ij)则一次划分结束，基准记录达到其最

10、终位置*/for(j=i+1;j=n ;j+)/*在当前无序区中选择关键词最小的记录rk*/while(i!=j);/*i=j,z对 rhs到 rht进行快速排序*/*/进行一次划分*/*/*/ i=partiti on( r,hs,ht); /*对 rhs到 rhtquick_sort(r,hs,i-1); /*递归处理左区间quick_sort(r,i+1,ht); /*递归处理右区间交换记录 ri和 rk*/if(hsht) /*只有一个记录或无记录时无需排序7/*for*/rk=temp;/*SELECT_SORT*/*堆排序算法如下*/void shift(rectype *r,i

11、nt i,i nt m)/*堆的筛选算法，在数组中 ri到 rm中，调整堆ri*/ 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与最后一个元素交换位置*/8r1=ri；ri=temp;shift(r,1,i-

12、1);/*将数组元素 r1到 ri-1重新调整成为一个新堆 */*FOR*/*HEAP_SORT*/*二路归并排序算法如下*/ void merge(rectype *a,rectype *r,i nt low,i nt mid,i nt high) inti,j,k;i=low;j=mid+1;k=low;rk+=ai+;else rk+=aj+;/*MERGE*/ void merge_pass(rectype *r,rectype *r1,i nt le ngth) int i=1,j, n=NUM;归并若干长度为 2*length 的两个相邻有序子表*/ merge(r,r1,i,i+

13、le ngth-1,i+2*le ngth-1);if(i+le ngth-1 n)merge(r,r1,i,i+length-1,n);/*处理表长不足 2*length 的部分 */else for(j=i;j=n ;j+)r1j=rj;/*将最后一个子表复制到 r1 中*/*MERGEPASS*/while(i=mid)&(j=high)/*将两个相邻有序子表进行合并*/ if(ai.key=aj.key)/*取两表中小者复制*/while(i=mid) rk+=ai+;/*复制第一个有序子表的剩余记录*/while(j=high) rk+=aj+;/*复制第二个有序子表的剩余记

14、录*/while (i+2*le ngth-1)=n)/*i=i+2*length;/*i指向下一对有序子表的起点*/9void merge_sort(rectype *r) int len gth;rectype r1MAX;len gth=1;/*归并长度从 1 开始*/while(le ngthNUM) merge_pass(r,r1,le ngth);/*趟归并，结果存放在 r1 中 */len gth=2*le ngth;/*归并后有序表的长度加倍*/merge_pass(r1,r,le ngth);/*再次归并，结果存放在 r 中*/len gth=2*le ngth;/*再次将归

15、并后有序表的长度加倍*/*MERGE_SORT*/void creat_ra ndn um(i nt *a )/*产生给定个数和范围的随机整数函数*/ int i;in t ran ge=30000;sran d(time(NULL);for(i=1;i=NUM;i+)ai=rand(); /*调用 rand 生成随机整数*/prin tf(nnttt排序前的原始随机整数为：nnt);for(i=1;i=NUM;i+) printf(%6d,ai); /*输出随机整数 */if(i%10=0) pri ntf(nt);pri ntf(n);/*CREAT_RANDNUM*/void creat

16、e() /*产生 NUM 个随机整数并保存到记录数组 s 中*/ int bMAX;in t ran ge=30000,i;creat_ra ndn um(b); /*调用随机整数生成函数，结果存放在数组b 中*/for(i=1;i=NUM;i+)si.key=bi;/*将随机整数存放到数组 s 中*/S 仁 s;/*s1指向 s,以便保存原始数据*/10/*CREAT*/void prin t_record(rectype *r)/*记录数组的输出函数 */ int i;prin tf(nttt排序后的有序随机整数：nnt);for(i=1;i=NUM;i+)pri ntf(%6d,ri.k

17、ey);if(i%10=0) pri ntf(nnt);getchar();getchar();/*PRINTRECORD*/int menu _select()/*主菜单选择模块*/ char c; int kk;system(cls);/*清屏函数*/printf( 内排序算法的比较-主控模块:nn);prin tf(ttt1.直接插入排序n);prin tf(ttt2.希尔排序n);prin tf(ttt3.冒泡排序n);prin tf(ttt4.快速排序n);prin tf(ttt5.直接选择排序n);prin tf(ttt6.堆排序n);prin tf(ttt7.二路归并排序n);p

18、rin tf(ttt0.退出n);do pri ntf(nttt请按数位 07 键选择功能:);c=getchar(); kk=c-48;while (kk7);return(kk);/*MENU_SELECT*/main() /*算法比较-主程序模块*/11double timel, time2, time3, time4, time5, time6, time7;clock_t start, fini sh;int kk;do kk=me nu_select(); /*进入主菜单选择模块 */if(kk!=O) create(); /*建立记录数组 */switch(kk) case 1:

19、 start=clock();in sert_sort(s1);fini sh=clock();time1 = (double)(fi nish - start)/ CLOCKS_PER_SEC ;printf(”直接插入排序耗时 %f seco ndsn, time1); break;case 2: start=clock();shell_sort(s1);fini sh=clock();time2 = (double)(fi nish - start)/ CLOCKS_PER_SEC ;printf(希尔排序耗时 %f sec on dsn, time2); break;case 3: s

20、tart=clock();bubble_sort(s1);fini sh=clock();time3 = (double)(fi nish - start)/ CLOCKS_PER_SEC ;printf(冒泡排序耗时 %f sec on dsn, time3); break;case 4: start=clock();quick_sort(s1,1,NUM);fini sh=clock();time4 = (double)(fi nish - start)/ CLOCKS_PER_SEC ;printf(快速排序耗时 %f sec on dsn, time4); break;case 5:

21、start=clock();select_sort(s1);fin ish=clock();12time5 = (double) nish - start)/ CLOCKS_PER_SEC ;printf(”直接选择排序耗时 %f seco ndsn, time5); break;case 6: start=clock();heap_sort(s1);fini sh=clock();time6 = (double)(fi nish - start)/ CLOCKS_PER_SEC ;prin tf(堆排序耗时 %f sec on dsn, time6);break;case 7: start=

22、clock();merge_sort(s1);fini sh=clock();time7 = (double)(fi nish - start)/ CLOCKS_PER_SEC ;printf(二路归并排序耗时 %f seco ndsn, time7); break;case 0: exit(O);prin t_record(s1);while (kk!=0);/*MAIN*/4 4 测试结果13巧 * DACbOebuggg.exe .J 叵内排序算法的比较一主控模块:请按数字Q-7键选择功能:(1)选择直接插入排序:入序序序择并插排排排选序归接尔泡速接排路岀直希冒快直堆二退12312356

23、70567014直接选择排序堆排序二路归并排序排序前本有 3000030000 个随机数显示，但数据太多，只截一部分图来表示。排序后也一样，应有 3000030000 个排好顺序的整数显示，但由于数据过多，也只截一 部分图来表示。1SS9 25231277631B736逝299G7冲413113515253 103H7240521626211023879107823025730435409421B3627923251曲126551365022H 30831361G 26G54193573O0OH 26999内排序算法的比较一一主控模块:擂入排序1.请按数字-了键选择功能：1排序前的原始随机整数

24、为: O:CbXOebu ggg.exe5,7.15由图可知，直接插入排序耗时 0.8780000.878000 秒16D:CbDebu ggg-e)ce直接插入排序耗时0.878GOO seconds排序后的有序随机整数:2223358g1013151 7132G2022222626272329292931333433535363?3S3941434343屿帕4748H85152535357B0BG3G3G365655676S&9S9707172727272737575767676787881328282338385873903537961011921G31G310410510911

25、21121121 1411511511611E1 181201201211Z31241241261271Z712712713G13013213313313413513&13&1361371391391421421斗31451451451H71H81*91511511521S315315315315415H(2)选择希尔排序: 排序前本有 3000030000 个随机数显示，但数据太多，只截一部分图来表示。排序后也一样，应有 3000030000 个排好顺序的整数显示，但由于数据过多，也只截一 部分图来表示。由图可知，希尔排序耗时 0.0260000.026000 秒 DACbD

26、EbLiggg启畑17内排序篦法的比较一一主控模块:體按数字二;键选择功蟲2琲序前的源妬陲机整数为:序序序-IJ.L.-IJ.L. -kXL.-kXL.LhrLhr flfl flfl flfl入序序序择并插排排排选序归接尔泡速接排路出直希冒快直堆二退123123 4567045670 DACbDEbLiggg启畑1835G1 233911386094129Q3981G0391S94561741662790232165120472M4802112209623119315311233992223343602G4ZG Z5O341385 1205411861 2S7S72G666 17724322

27、1 103431947183843225耳863657B2 19SSS3265 1G5962392? 1642333925EJ515829171263Q32419322331130GSG25641 1182965北1774727717750483253G783220951238014379870114637 116991147M37772673 272313742184812413 17224H537 2638411613 29431414917717755 2T67G20431 227694B8255730963 261908938 2G9731896935553722 2852736665

28、 26014843032371233H693131456&252428676454湖121592379307239H5 296007221 2牺2斗32OGG250930350120573089H65921701H191132762739BG1853G1279322817 156664975755021713 2416115048265888S 139351825516021GG3155332924132385225653216T30812195673G7S713B49235512909625*9813391311633185523E14 256002TB9 2426311632 29

29、1昨2698Cl3DEbLiggg启昭11内排序算法的比较一一主控模块:序序序-IJ.L.-kXL.Lkrfl fl fl入序序序择并插排排排选序归接尔泡速接排路出直希冒快直堆二退書按数字;一;键选择功盛汕排序前的原始随机整数为:H9071845821804321332S2211418225471191742G430199921924538G0汕斛1888G194552359&2805427559301941969311943707258屮I770311381954116455189221577S2097824238765G19136 2853411199 1002931487 26m

30、E8450 2889223099 3273212706228H29831 26S8727320 2128938234 3254820456 1TB01323 17556973448291576576eeee9381781794871543610591238 209583572 2716123B233314942 28G232393 208892124336751679H 2352B3078 1313B14224 3B6522388530 2094327620 1H5042658313313587413Q171519410691562729483 261941676248852158443837

31、91131132917937093778247931885232G95139732415828960197511331022m57?0131772233531 1308873Q152934 1808224973797GBGH272611849632F00207594782292576732748716641251792G398282S114216185621431837531T2133212031473311656T71151993188625132 179B529189215862352221812947 11M362621333122811431123(5)选择直接选择排序：排序前本有 3

32、000030000 个随机数显示，但数据太多，只截一部分图来表示。排序后也一样，应有 3000030000 个排好顺序的整数显示，但由于数据过多，也只截一 部分图来表示。由图可知，直接选择排序耗时 1.5280001.528000 秒2425(6)选择堆排序: 排序前本有 3000030000 个随机数显示，但数据太多，只截一部分图来表示。排序后也一样，应有 3000030000 个排好顺序的整数显示，但由于数据过多，也只截一 部分图来表示。由图可知，堆排序耗时 0.0080000.008000 秒 D:CbDebijggg.exe直接选择排序耗时1-523903 seconds排序后的有序随机整数:223137GQ8550S77177871007480871Q3821041041051051Q61G310911211411511