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

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

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

3、的个数3000Ot,数据由随机函数生成2.2 输出数据产生的随机数分别用冒泡排序、直插排序、希尔排序、选择排序、快速排序、 堆排序、归并排序这些排序方法进行排序，并统计每一种排序上机所花费的时间。输出排序上机所花费的时间3程序源代码及其注释#include "stdio.h"#include "stdlib.h"#include "math.h"#include<time.h>#include<conio.h>#define MAX 60000 /* 记录数组的个数*/#define NUM 30000 /*

4、实际输入数组的个数*/typedef int datatype;typedef struct /* 定义记录为结构体类型*/ int key; /* 记录的关键词域 */datatype other; /* 记录的其它域*/ rectype;rectype *s1,sMAX;/*sMAX 存放原始随机数， *s1 取出原始数据后进行排序 */* 直接插入排序算法如下 */void insert_sort(rectype *r) /* int i,j,n=NUM;/*NUMfor(i=1;i<=n;i+)/* i<NUM r0=ri;/*r0j=i-1;/*while(r0.key&

5、lt;rj.key) /*rj+1=rj-;/*rj+1=r0;/*/*INSERTSORT*/对数组 r 按递增顺序进行插入排序算法*/为实际输入的记录数，是一个常量*/条件很重要，NUM；实际记录数*/为监视哨 */依次插入记录r1,，rNUM*/查找ri 合适的位置 */将记录关键词大于ri.key的记录后移 */将记录 ri 插入到有序表的合适的位置上*/* 希尔排序算法如下*/void shell_sort(rectype *r) /*取增量为 d(i+1)=d(i)/2 的希尔排序的算法*/ int i,n,jump,change,temp,m;/*change为交换标志，jump

6、为增量步长 */jump=NUM; n=NUM; /*NUM 为顺序表的实际长度 */while(jump>0) jump=jump/2; /* 取步长 d(i+1)=d(i)/2*/do change=0;/*设置交换标志，change=0表示未交换*/for(i=1;i<=n-jump;i+) m=i+jump; /* 取本趟的增量*/if(ri.key>rm.key) /*记录交换 */ temp=rm.key;rm.key=ri.key;ri.key=temp;change=1; /*change=1表示有交换 */*if*/*for*/ /* 本趟排序完成*/whi

7、le(change=1); /* 当 change=0 时终止本趟排序*/*while*/* 当增量 jump=1 且 change=0 时终止算法*/*SHELLSORT*/* 冒泡排序算法如下*/void bubble_sort(rectype *r) /*从下往上扫描的冒泡排序*/ int i,j,noswap=0,n=NUM;/*noswap为交换标志，NUM/实际输入记录数*/rectype temp;for(i=1;i<n;i+) noswap=1;for(j=n;j>=i;j-)if(rj.key<rj-1.key)/* 进行 n-1 趟冒泡排序*/*设置交换标

8、志，noswap=1表示没有记录交换*/* 从下往上扫描*/* 交换记录 */ temp.key=rj-1.key;rj-1.key=rj.key;rj.key=temp.key;noswap=0;/* 当交换记录时，将交换标志置0即noswap=0 */*if*/if(noswap) break; /* 若本趟排序中未发生记录交换，则终止排序*/*for*/* 终止排序算法*/*BUBBLESORT*/* 快速排序算法如下*/int partition(rectype *r,int s,int t) /* int i,j;rectype temp;i=s;j=t;temp=ri;/*do w

9、hile(rj.key>=temp.key)&&(i<j)快速排序算法中的一趟划分函数*/初始化，temp为基准记录*/j-;/* 从右往左扫描，查找第一个关键词小于temp的记录*/if(i<j) ri+=rj; /*交换 ri 和 rj*/while(ri.key<=temp.key)&&(i<j)i+;/* 从左往右扫描，查找第一个关键词大于temp 的记录 */if(i<j) rj-=ri; /*交换 ri 和 rj*/while(i!=j);/*i=j,z则一次划分结束，基准记录达到其最终位置*/ri=temp;/*

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

11、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.key<rk.key) k=j;if(k!=i) temp=ri;/*交换记录 ri 和 rk*/ri=rk;rk=temp;/*for*/*SELECT_SORT*/* 堆排序算法如下 */ ri*/void shift(rectype *r,int i,int m)/*堆的筛选算法,在数组中ri至3m中，调整

12、堆 int j; rectype temp;temp=ri; j=2*i;while (j<=m)/*j<=m,r2*i 是 ri 的左孩子 */ if(j<m)&&(rj.key<rj+1.key)j+; /*j指向 ri 的左右孩子中关键词较大者 */if(temp.key<rj.key) /*若孩子结点的关键词大于父结点 */ ri=rj;/* 将 rj 调到父亲结点的位置上*/i=j;/* 调整i和j的值，以便继续“筛”结点 */j=2*i;elsej=m+2;/* 调整完毕，退出循环*/ri=temp;/* 将被筛选的结点放入正确的位置

13、*/*SHIFT*/void heap_sort(rectype *r)/* 对数组 r1 到 rNUM 进行堆排序 */ rectype temp;int i,n;n=NUM;/*NUM 为数组的实际长度*/for(i=n/2;i>0;i-)/*建立初始堆*/shift(r,i,n);for(i=n;i>1;i-)/* 进行 n-1 趟筛选，交换，调整，完成堆排序*/ temp=r1;/* 将堆顶元素 r1 与最后一个元素交换位置*/r1=ri;ri=temp;shift(r,1,i-1);/*将数组元素r1到ri-1重新调整成为一个新堆*/*FOR*/*HEAP_SORT*/*

14、 二路归并排序算法如下*/ 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+;/*复制第二个有序子表的剩余记

15、录 */ /*MERGE*/void merge_pass(rectype *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-1<n)merge(r,r1,i,i+length-1,n);/*处理表长不足 2*length 的部分 */else for(j=i;j<=n

16、;j+)r1j=rj;/*将最后一个子表复制到 r1 中*/*MERGEPASS*/void merge_sort(rectype *r) int length;rectype r1MAX;length=1;/* 归并长度从1 开始 */while(length<NUM) merge_pass(r,r1,length);/*一趟归并，结果存放在r1 中*/length=2*length;/*归并后有序表的长度加倍 */merge_pass(r1,r,length);/*再次归并，结果存放在r 中*/length=2*length;/* 再次将归并后有序表的长度加倍 */*MERGE_SO

17、RT*/void creat_randnum(int *a )/* 产生给定个数和范围的随机整数函数*/ int i;int range=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");

18、/*CREAT_RANDNUM*/void create。/* 产生NUMb随机整数并保存到记录数组s中*/ int bMAX;int range=30000,i;creat_randnum(b);/*调用随机整数生成函数，结果存放在数组b中*/for(i=1;i<=NUM;i+)si.key=bi;/*将随机整数存放到数组 s中*/s1=s;/*s1 指向 s, 以便保存原始数据*/*CREAT*/void print_record(rectype *r)/*记录数组的输出函数 */ int i;printf("nttt 排序后的有序随机整数 :nnt");for(

19、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;system("cls");/* 清屏函数 */printf(" 内排序算法的比较 主控模块 :nn");printf("ttt1.直接插入排序 n");printf("ttt2.希尔排序n"

20、);printf("ttt3.冒泡排序n");printf("ttt4.快速排序n");printf("ttt5.直接选择排序 n");printf("ttt6.堆排序 n");printf("ttt7.二路归并排序n");printf("ttt0.退出 n");do printf("nttt请按数位07键选择功能:");c=getchar(); kk=c-48;while (kk<0)|(kk)>7);return(kk);/*MENU_SE

21、LECT*/main() /* 算法比较 - 主程序模块*/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();time1 = (double)(finish - start)/ CLOCKS_PER_SEC ;print

22、f( " 直接插入排序耗时 %f secondsn", time1); break;case 2: start=clock();shell_sort(s1);finish=clock();time2 = (double)(finish - start)/ CLOCKS_PER_SEC ;printf( " 希尔排序耗时%f secondsn", time2); break;case 3: start=clock();bubble_sort(s1);finish=clock();time3 = (double)(finish - start)/ CLOCK

23、S_PER_SEC ;printf( " 冒泡排序耗时%f secondsn", time3); break;case 4: start=clock();quick_sort(s1,1,NUM);finish=clock();time4 = (double)(finish - start)/ CLOCKS_PER_SEC ;printf( " 快速排序耗时%f secondsn", time4); break;case 5: start=clock();select_sort(s1);finish=clock();time5 = (double)(fin

24、ish - start)/ CLOCKS_PER_SEC ;printf( " 直接选择排序耗时%f secondsn", time5); break;case 6: start=clock();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 =

25、(double)(finish - start)/ CLOCKS_PER_SEC ;printf( " 二路归并排序耗时%f secondsn", time7); break;case 0:exit(0);print_record(s1);while (kk!=0);/*MAIN*/4.测试结果r- * D:CbDebuggg.exe"内排序算法的比较-主拧模块;入序序序择并 插排排排选序归 接尔泡速接排路出 直希冒快直堆二退 1235670请按数字。一了犍选择功能:(1)选择直接插入排序:排序前本有3000Ot随机数显示，但数据太多，只截一部分图来表示。排序后也

26、一样，应有3000办排好顺序的整数显示，但由于数据过多，也只截一 部分图来表示。(2)选择希尔排序:排序前本有3000Ot随机数显示，但数据太多，只截一部分图来表示。排序后也一样，应有3000办排好顺序的整数显示，但由于数据过多，也只截一 部分图来表示由图可知，希尔排序耗时0.026000秒由图可知，冒泡排序耗时3.456000秒(3)选择冒泡排序：排序前本有3000Ot随机数显示，但数据太多，只截一部分图来表示。排序后也一样，应有3000办排好顺序的整数显示，但由于数据过多，也只截一 部分图来表示。* * D:CbDebuggg.exe*排序前的原始随机整数为:直接插入排序 希尔排序 冒泡排

27、序 快速排序 直接选择排序 堆排序 二路归并排序 退出请按数字。一7键选择功能： 请按数字。一7键选择功能：342349338918219459635631252309572650485591971516159184865343935719507271661817027901255661035329506196171862423201300661896522935196512875910179376359442224163152756265402938128961466873262454164677129245771985223636228985795283242875825806580480

28、4913954616553214510723219250661243418945228305672268551435218162775627996799421827212911243811G102680140221471163312582717618731216168267731961894326710170642708695329925295365086290942558619919253191146。287211985724170438526793298821317715767160321793356598479174011214320978227592482630875199951347

29、72235525822134218041391682941930364602575916255940419615252383135823887198251093425497311827104211641442215301877209667676121092862444375832940719195103532979225226259442751825721774043481204695085870(4)选择快速排序:排序前本有3000Ot随机数显示，但数据太多，只截一部分图来表示 排序后也一样，应有3000口排好顺序的整数显示，但由于数据过多，也只截一 部分图来表示由图可知，快速排序耗时0.0

30、05000秒由图可知，直接选择排序耗时1.528000秒(5)选择直接选择排序：排序前本有3000Ot随机数显示，但数据太多，只截一部分图来表示。排序后也一样，应有3000办排好顺序的整数显示，但由于数据过多，也只截一 部分图来表示。1 .直接插入排序2 .希尔排序3 .冒泡排序4 .快速排序5 .直接选择排序6 .堆排序7 .二路归并排序0.退出请按数字。一7谑选择功能：请按数字。一7诞选择功能：5排序前的原始随机整数为:57266160138776345152523527115553222817716280961410258473026516203245208171876126852102

31、37132233512165173188817607189532655628845123998023200423170631644317322900137442387624911652010126391116667214601472111172137412263218210271126566213492244720717171071752510H951248。25681267011708838947235412470520228160532839434852354820941474820337273941198322229816828893283775501502111073383981472

32、91909328566277387721859322266443313585223127529677230075902215068145921447512595291351611116036370525992128999388574511701380828780378713332991315418134682386514536178778112119163682257442870555211370610931312721342。111091385425652224362799297432744931015509923782167152983877122695114955206431965018

33、688152651692856796988826719386296601205524848G302011036831968894033143722762293831868822933128053234531719290081786828001(6)选择堆排序：排序前本有3000Ot随机数显示，但数据太多，只截一部分图来表示。排序后也一样，应有3000办排好顺序的整数显示，但由于数据过多，也只截一 部分图来表示。由图可知，堆排序耗时0.008000秒 * D:CbDebuggg.exe *序 序序 入序序序择并 插排排排选序归 接尔泡速接排路出 直希冒快直堆二退 12345670请按数字。一7谑

34、选择功能： 请按数字。一7诞选择功能：6 排序前的原始随机整数为:61256746306182571814719110683082627805143169528825112211146421424237136144137561373742932417199484648286892142。3104H322397G482358414748166524606216542738221004412626138135684460117102386513793228643245022363189931368715165231245705223831301826131350269173963290321181

35、612032110393836772013839320097997106652969525119211281085323345175522620513227366026297216862160010799218343479149172769017572283916775215723942282868281760015593108793148411125110482148。42382729120068100871656613173235912673621739118193655474880292195024334135561439920545206311135882245959172751205

36、52765611768366244G2240985928232032246441421097248726208485726911101882703310022123721208490229486148H02603323206174381369117987232331036316034233864117612631285251161885048782400221484197282955173905403123442843928359133122762228721(7)选择二路归并排序：排序前本有3000Ot随机数显示，但数据太多，只截一部分图来表示。排序后也一样，应有3000办排好顺序的整数显示

37、，但由于数据过多，也只截一 部分图来表示。由图可知，二路归并排序耗时0.006000秒 *D:CbDebuggg.exe*序 序序 入序序序择并 插排排排选序归 接尔泡速接排路出 直希冒快直堆二退 12345670请按数字。一7谑选择功能： 请按数字。一7诞选择功能：7 排序前的原始随机整数为:6523733114591123222791331377173296100160802527107811659425431846。1141324239875262330948188433615255462549。252331Q367515418019200221474132621027311665230

38、3213007H5072840。222623991329411051109182426817411787242464743121211913548442341635891727898972907730199128153071930131499。9493246672972110233270925703231372669073946958263547709765942263197923701149959882657732594932915104351865792124147791848925618193712083920236571498612613228702828368267699220110014064170952264121190780H132217892283785688200H5734625671719813362276231739881803134。3806226352042729569641411210232944981335121910502719893101530616850127392637222130161982903080302709826859I32022178412892825183277241961210454362956709124581268317113289479768217713012312492283658331153