七種排序算法的比較及每種排序的上機統(tǒng)計時間

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告課題: 排序算法的比較學(xué)院:信息學(xué)院班級: 2011級電子信息工程1班小組成員:韋志東（組長） 20111601310027 夏琪 20111601310028完成時間: 2014-01-08教師:周鐵目錄1、課程分析21.1、選題21.2、選題的意義及背景2 1.3、設(shè)計任務(wù)書22、設(shè)計分析22.1、原始數(shù)據(jù)22.2、輸出數(shù)據(jù)22.3、程序流程圖33、程序源代碼及注釋34、測試結(jié)果125、總結(jié)266、參考文獻(xiàn)277、小組人員分工271、課程分析1.1、選題要求利用隨機函數(shù)產(chǎn)生30000個隨機整數(shù)，利用直接插入排序、希爾排序，冒泡排序、直接選擇排序、快速排序、堆排序、歸并排

2、序的排序方法進行排序，并統(tǒng)計每一種排序上機所花費的時間。 1.2、選題的意義及背景排序是計算機程序設(shè)計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關(guān)鍵詞有序的序列。此實驗通過對各種內(nèi)部排序算法進行比較，能使我們更好的掌握各種排序的基本思想，掌握各種排序方法的算法實現(xiàn)，掌握各種排序方法的優(yōu)劣分析及花費的時間的計算，掌握各種排序方法所適應(yīng)的不同場合。通過該題目的設(shè)計，可以加深理解各種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)上運算的實現(xiàn)，進一步理解和熟練掌握課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，學(xué)會如何把學(xué)到的知識用于解決實際問題，培養(yǎng)我們的動手能力。1.3、設(shè)計任務(wù)書（1）定義結(jié)構(gòu)體，頭文

3、件，定義數(shù)組范圍，大小。（2）依次描寫七種排序的算法。（3）描寫產(chǎn)生隨機函數(shù)的算法。（4）描寫菜單函數(shù)。（5）描寫主函數(shù)，調(diào)用七種排序的算法。2、設(shè)計分析2.1 原始資料用戶輸入記錄的個數(shù)30000個，數(shù)據(jù)由隨機函數(shù)生成。2.2 輸出數(shù)據(jù)產(chǎn)生的隨機數(shù)分別用冒泡排序、直插排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序這些排序方法進行排序，并統(tǒng)計每一種排序上機所花費的時間。 2.3 程序流程圖主程序產(chǎn)生1組隨機數(shù) 將隨機數(shù)保存在數(shù)組中二路歸并排序冒泡排序直接插入排序堆排序直接選擇排序快速排序Shell排序 輸出排序上機所花費的時間 3程序源代碼及其注釋#include "stdio

4、.h"#include "stdlib.h"#include "math.h"#include<time.h>#include<conio.h>#define MAX 60000 /*記錄數(shù)組的個數(shù)*/#define NUM 30000 /*實際輸入數(shù)組的個數(shù)*/typedef int datatype; typedef struct /*定義記錄為結(jié)構(gòu)體類型*/ int key; /*記錄的關(guān)鍵詞域*/ datatype other; /*記錄的其它域*/ rectype;rectype *s1,sMAX;/*sMAX

5、存放原始隨機數(shù)，*s1取出原始數(shù)據(jù)后進行排序*/*直接插入排序算法如下*/void insert_sort(rectype *r) /*對數(shù)組r按遞增順序進行插入排序算法*/ int i,j,n=NUM; /*NUM為實際輸入的記錄數(shù)，是一個常量*/ for(i=1;i<=n;i+) /* i<NUM 條件很重要，NUM為實際記錄數(shù)*/ r0=ri; /*r0為監(jiān)視哨*/ j=i-1; /*依次插入記錄r1,，rNUM*/ while(r0.key<rj.key) /*查找ri合適的位置*/ rj+1=rj-; /*將記錄關(guān)鍵詞大于ri.key的記錄后移*/ rj+1=r0;

6、 /*將記錄ri插入到有序表的合適的位置上*/ /*INSERTSORT*/*希爾排序算法如下*/void shell_sort(rectype *r) /*取增量為d(i+1)=d(i)/2的希爾排序的算法*/ int i,n,jump,change,temp,m; /*change為交換標(biāo)志，jump為增量步長*/ jump=NUM; n=NUM; /*NUM為順序表的實際長度*/ while(jump>0) jump=jump/2; /*取步長d(i+1)=d(i)/2*/ do change=0; /*設(shè)置交換標(biāo)志，change=0表示未交換*/ for(i=1;i<=n-

7、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*/ /*本趟排序完成*/ while(change=1); /*當(dāng)change=0時終止本趟排序*/ /*while*/*當(dāng)增量jump=1且change=0時終止算法*/*SHELLSORT*/*冒泡排序算法如下*/void bubble_sort(rectype *r) /*從下往上掃描的冒泡排序*/ int

8、i,j,noswap=0,n=NUM;/*noswap為交換標(biāo)志,NUM為實際輸入記錄數(shù)*/rectype temp;for(i=1;i<n;i+) /*進行n-1趟冒泡排序*/ noswap=1;/*設(shè)置交換標(biāo)志，noswap=1表示沒有記錄交換*/for(j=n;j>=i;j-)/*從下往上掃描*/ if(rj.key<rj-1.key)/*交換記錄*/ temp.key=rj-1.key; rj-1.key=rj.key; rj.key=temp.key; noswap=0; /*當(dāng)交換記錄時，將交換標(biāo)志置0即noswap=0 */ /*if*/ if(noswap)

9、break; /*若本趟排序中未發(fā)生記錄交換，則終止排序*/*for*/ /*終止排序算法*/*BUBBLESORT*/*快速排序算法如下*/int partition(rectype *r,int s,int t) /*快速排序算法中的一趟劃分函數(shù)*/ int i,j;rectype temp; i=s;j=t;temp=ri; /*初始化，temp為基準(zhǔn)記錄*/do while(rj.key>=temp.key)&&(i<j) j-; /*從右往左掃描，查找第一個關(guān)鍵詞小于temp的記錄*/ if(i<j) ri+=rj;/*交換ri和rj*/ while

10、(ri.key<=temp.key)&&(i<j) i+;/*從左往右掃描，查找第一個關(guān)鍵詞大于temp的記錄*/ if(i<j) rj-=ri; /*交換ri和rj*/while(i!=j);/*i=j,z則一次劃分結(jié)束，基準(zhǔn)記錄達(dá)到其最終位置*/ri=temp; /*最后將基準(zhǔn)記錄temp定位*/return(i);/*PARTITION*/void quick_sort(rectype *r,int hs,int ht)/*對rhs到rht進行快速排序*/ int i;if(hs<ht) /*只有一個記錄或無記錄時無需排序*/ i=partitio

11、n(r,hs,ht); /*對rhs到rht進行一次劃分*/ quick_sort(r,hs,i-1);/*遞歸處理左區(qū)間*/ quick_sort(r,i+1,ht);/*遞歸處理右區(qū)間*/*QUICK_SORT*/*直接選擇排序算法如下*/void select_sort(rectype *r) rectype temp;int i,j,k,n=NUM; /*NUM為實際輸入記錄數(shù)*/for(i=1;i<=n;i+)/*做n-1趟選擇排序*/ k=i;for(j=i+1;j<=n;j+)/*在當(dāng)前無序區(qū)中選擇關(guān)鍵詞最小的記錄rk*/ if(rj.key<rk.key) k

12、=j; if(k!=i) temp=ri;/*交換記錄ri和rk*/ ri=rk; rk=temp; /*for*/*SELECT_SORT*/*堆排序算法如下*/void shift(rectype *r,int i,int m)/*堆的篩選算法,在數(shù)組中ri到rm中，調(diào)整堆ri*/ 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的左右孩子中關(guān)鍵詞較大者*/ if(temp.key&l

13、t;rj.key) /*若孩子結(jié)點的關(guān)鍵詞大于父結(jié)點*/ ri=rj; /*將rj調(diào)到父親結(jié)點的位置上*/ i=j; /*調(diào)整i和j的值，以便繼續(xù)“篩”結(jié)點*/ j=2*i; else j=m+2; /*調(diào)整完畢，退出循環(huán)*/ ri=temp; /*將被篩選的結(jié)點放入正確的位置*/*SHIFT*/void heap_sort(rectype *r)/*對數(shù)組r1到rNUM進行堆排序*/ rectype temp; int i,n; n=NUM; /*NUM為數(shù)組的實際長度*/ for(i=n/2;i>0;i-)/*建立初始堆*/ shift(r,i,n); for(i=n;i>1;

14、i-)/*進行n-1趟篩選，交換，調(diào)整，完成堆排序*/ temp=r1;/*將堆頂元素r1與最后一個元素交換位置*/ r1=ri;ri=temp;shift(r,1,i-1);/*將數(shù)組元素r1到ri-1重新調(diào)整成為一個新堆*/ /*FOR*/*HEAP_SORT*/*二路歸并排序算法如下*/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.k

15、ey<=aj.key)/*取兩表中小者復(fù)制*/ rk+=ai+;else rk+=aj+;while(i<=mid) rk+=ai+;/*復(fù)制第一個有序子表的剩余記錄*/while(j<=high) rk+=aj+;/*復(fù)制第二個有序子表的剩余記錄*/*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

16、-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;j+) r1j=rj;/*將最后一個子表復(fù)制到r1中*/*MERGEPASS*/void merge_sort(rectype *r) int length;rectype r1MAX; length=1;/*歸并長度從1開始*/ while(length<NUM) merge_pass(r,r1,length);/*一趟歸并，結(jié)果存放在r1中

17、*/ length=2*length;/*歸并后有序表的長度加倍*/ merge_pass(r1,r,length);/*再次歸并，結(jié)果存放在r中*/ length=2*length;/*再次將歸并后有序表的長度加倍*/ /*MERGE_SORT*/void creat_randnum(int *a )/*產(chǎn)生給定個數(shù)和范圍的隨機整數(shù)函數(shù)*/ int i;int range=30000;srand(time(NULL);for(i=1;i<=NUM;i+)ai=rand(); /*調(diào)用rand生成隨機整數(shù)*/printf("nnttt排序前的原始隨機整數(shù)為:nnt")

18、;for(i=1;i<=NUM;i+) printf("%6d",ai); /*輸出隨機整數(shù)*/ if(i%10=0) printf("nt");printf("n");/*CREAT_RANDNUM*/void create() /*產(chǎn)生NUM個隨機整數(shù)并保存到記錄數(shù)組s中*/ int bMAX; int range=30000,i; creat_randnum(b); /*調(diào)用隨機整數(shù)生成函數(shù)，結(jié)果存放在數(shù)組b中*/ for(i=1;i<=NUM;i+) si.key=bi;/*將隨機整數(shù)存放到數(shù)組s中*/ s1=s;

19、/*s1指向s,以便保存原始數(shù)據(jù)*/*CREAT*/void print_record(rectype *r)/*記錄數(shù)組的輸出函數(shù)*/ int i;printf("nttt排序后的有序隨機整數(shù):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;system("cls&qu

20、ot;);/*清屏函數(shù)*/printf("內(nèi)排序算法的比較-主控模塊:nn");printf("ttt1. 直接插入排序n");printf("ttt2. 希爾排序n");printf("ttt3. 冒泡排序n");printf("ttt4. 快速排序n");printf("ttt5. 直接選擇排序n");printf("ttt6. 堆排序n");printf("ttt7. 二路歸并排序n");printf("ttt0. 退出

21、n");do printf("nttt請按數(shù)位07鍵選擇功能:"); c=getchar(); kk=c-48;while (kk<0)|(kk)>7);return(kk);/*MENU_SELECT*/main() /*算法比較-主程序模塊*/ double time1, time2, time3, time4, time5, time6, time7; clock_t start, finish;int kk; do kk=menu_select(); /*進入主菜單選擇模塊*/ if(kk!=0) create(); /*建立記錄數(shù)組*/swi

22、tch(kk) case 1:start=clock();insert_sort(s1); finish=clock();time1 = (double)(finish - start)/ CLOCKS_PER_SEC ; printf( "直接插入排序耗時%f secondsn", time1); break;case 2: start=clock();shell_sort(s1); finish=clock();time2 = (double)(finish - start)/ CLOCKS_PER_SEC ;printf( "希爾排序耗時%f seconds

23、n", time2); break; case 3: start=clock();bubble_sort(s1); finish=clock();time3 = (double)(finish - start)/ CLOCKS_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( &

24、quot;快速排序耗時%f secondsn", time4); break; case 5: start=clock();select_sort(s1); finish=clock();time5 = (double)(finish - start)/ CLOCKS_PER_SEC ;printf( "直接選擇排序耗時%f secondsn", time5); break; case 6: start=clock();heap_sort(s1); finish=clock();time6 = (double)(finish - start)/ CLOCKS_PE

25、R_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(s1);while (kk!=0);/*MAIN*/4測試結(jié)果 （1）選擇直接插入排序：排序前本有30

26、000個隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應(yīng)有30000個排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一部分圖來表示。由圖可知，直接插入排序耗時0.878000秒（2）選擇希爾排序：排序前本有30000個隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應(yīng)有30000個排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一部分圖來表示。由圖可知，希爾排序耗時0.026000秒（3）選擇冒泡排序：排序前本有30000個隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應(yīng)有30000個排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一部分圖來表示。由圖可知，冒泡排序耗時3.4

27、56000秒（4）選擇快速排序：排序前本有30000個隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應(yīng)有30000個排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一部分圖來表示。由圖可知，快速排序耗時0.005000秒（5）選擇直接選擇排序：排序前本有30000個隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應(yīng)有30000個排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一部分圖來表示。由圖可知，直接選擇排序耗時1.528000秒（6）選擇堆排序：排序前本有30000個隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應(yīng)有30000個排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一部分圖來表示。由圖可知，堆排序耗時0.008000秒（7）選擇二路歸并排序：排序前本有30