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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告課題：排序算法的比較學(xué)院:信息學(xué)院 班級:2011級電子信息工程1班 小組成員：韋志東（組長） 20111601310027夏琪20111601310028完成時間:2014-01-08 教師:周鐵11 1、課程分析1.11.1、選題.2.2.1.21.2、選題的意義及背景 .2.1.31.3、設(shè)計任務(wù)書. 2 22 2、設(shè)計分析5 5、總結(jié)& &參考文獻(xiàn). 27277 7、小組人員分工.27271、課程分析1.11.1 選題要求利用隨機函數(shù)產(chǎn)生 3000030000 個隨機整數(shù)，利用直接插入排序、希爾排序，冒泡 排序、直接選擇排序、快速排序、堆排序、歸并排

2、序的排序方法進(jìn)行排序，并統(tǒng) 計每一種排序上機所花費的時間。1.21.2、 選題的意義及背景排序是計算機程序設(shè)計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素的任 意序列，重新排列成一個按關(guān)鍵詞有序的序列。此實驗通過對各種內(nèi)部排序算法進(jìn)行比較，能使我們更好的掌握各種排序的 基本思想，掌握各種排序方法的算法實現(xiàn)，掌握各種排序方法的優(yōu)劣分析及花費 的時間的計算，掌握各種排序方法所適應(yīng)的不同場合。 通過該題目的設(shè)計，可以 加深理解各種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、 存儲結(jié)構(gòu)及相應(yīng)上運算的實現(xiàn)，進(jìn)一步理解 和熟練掌握課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，學(xué)會如何把學(xué)到的目錄2.12.1、原始數(shù)據(jù).錯誤！未定義書簽2.22.2、輸

3、出數(shù)據(jù).錯誤！未定義書簽2.32.3、程序流程圖.3.3.3 3、程序源代碼及注釋.3 34 4、測試結(jié)果.錯誤！未定義書簽26262知識用于解決實際問 題，培養(yǎng)我們的動手能力。1.31.3、 設(shè)計任務(wù)書（1 1）定義結(jié)構(gòu)體，頭文件，定義數(shù)組范圍，大小。（2 2）依次描寫七種排序的算法。（3 3）描寫產(chǎn)生隨機函數(shù)的算法。（4 4）描寫菜單函數(shù)。（5 5）描寫主函數(shù)，調(diào)用七種排序的算法。2、設(shè)計分析2.12.1 原始資料用戶輸入記錄的個數(shù) 3000030000 個，數(shù)據(jù)由隨機函數(shù)生成。2.22.2 輸出數(shù)據(jù)產(chǎn)生的隨機數(shù)分別用冒泡排序、直插排序、希爾排序、選擇排序、快速排序、 堆排序、歸并排序這些

4、排序方法進(jìn)行排序，并統(tǒng)計每一種排序上機所花費的時間。2.32.3 程序流程圖主程序產(chǎn)生 1 1 組隨機數(shù)3輸出排序上機所花費的時間3 3 程序源代碼及其注釋#i nclude stdio.h#in elude stdlib.h#in elude math.h#in clude#in clude#define MAX 60000 /*記錄數(shù)組的個數(shù) */ #defi ne NUM 30000 /* 實際輸入數(shù)組的個數(shù) */直接冒泡排序ShellShell排序插入排序二路歸并堆排排序序快速排序排序直接選擇將隨機數(shù)保存在數(shù)組中4typedef int datatype;typedef struct

5、/*定義記錄為結(jié)構(gòu)體類型*/ int key; /*記錄的關(guān)鍵詞域*/datatype other; /*記錄的其它域*/ rectype;rectype *s1,sMAX;/*sMAX存放原始隨機數(shù)，*s1 取出原始數(shù)據(jù)后進(jìn)行排序*/對數(shù)組 r 按遞增順序進(jìn)行插入排序算法*/為實際輸入的記錄數(shù)，是一個常量*/條件很重要，NUM 為實際記錄數(shù)*/為監(jiān)視哨*/依次插入記錄 r1,rNUM*/查找 ri合適的位置*/將記錄關(guān)鍵詞大于 ri.key 的記錄后移*/將記錄 ri插入到有序表的合適的位置上*/*希爾排序算法如下*/取增量為 d(i+1)=d(i)/2的希爾排序的算法*/ int i,n,

6、jump,change,temp,m; /*change為交換標(biāo)志， jump 為增量步長 */jump=NUM; n=NUM; /*NUM為順序表的實際長度 */while(jump0) jump=jump/2; /* 取步長 d(i+1)=d(i)/2*/do change=0; /*設(shè)置交換標(biāo)志， 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); /*當(dāng) change=0 時終止本趟排序 */*while*/* 當(dāng)增量 jump=1 且 change=0 時終止算法 */*SHELLSORT*/*冒泡排序算法如下*/void bubble_sort(rect

8、ype *r) /*從下往上掃描的冒泡排序*/ int i,j,no swap=0, n=NUM;/*noswap 為交換標(biāo)志，NUM 為實際輸入記錄數(shù)*/rectype temp;for(i=1;i=i;j-)/*從下往上掃描*/if(rj.key=temp.key)&(ij)j-;/*從右往左掃描，查找第一個關(guān)鍵詞小于temp 的記錄*/if(ij) ri+=rj; /*交換 ri和 rj*/ri=temp; /*最后將基準(zhǔn)記錄 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為實際輸入記錄數(shù) */for(i=1;i=n;i+)/*做 n-1 趟選擇排序 */ k=i;if(rj.keyrk.key) k=j;if(k!=i) temp=ri;/*ri=rk;i+;/*從左往右掃描，查找第一個關(guān)鍵詞大于temp 的記錄*/if(ij) rj-=ri; /*交換 ri和 rj*/while(ri.key=temp.key) &(ij)則一次劃分結(jié)束，基準(zhǔn)記錄達(dá)到其最

10、終位置*/for(j=i+1;j=n ;j+)/*在當(dāng)前無序區(qū)中選擇關(guān)鍵詞最小的記錄rk*/while(i!=j);/*i=j,z對 rhs到 rht進(jìn)行快速排序*/*/進(jìn)行一次劃分*/*/*/ i=partiti on( r,hs,ht); /*對 rhs到 rhtquick_sort(r,hs,i-1); /*遞歸處理左區(qū)間quick_sort(r,i+1,ht); /*遞歸處理右區(qū)間交換記錄 ri和 rk*/if(hsht) /*只有一個記錄或無記錄時無需排序7/*for*/rk=temp;/*SELECT_SORT*/*堆排序算法如下*/void shift(rectype *r,i

11、nt i,i nt 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(jm)&(rj.keyrj+1.key)j+; /*j指向 ri的左右孩子中關(guān)鍵詞較大者*/if(temp.key0;i-)/*建立初始堆*/shift(r,i,n);for(i=n;i1;i-)/*進(jìn)行 n-1 趟篩選，交換，調(diào)整，完成堆排序*/ temp=r1;/* 將堆頂元素 r1與最后一個元素交換位置*/8r1=ri；ri=temp;shift(r,1,i-

12、1);/*將數(shù)組元素 r1到 ri-1重新調(diào)整成為一個新堆 */*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;/*將最后一個子表復(fù)制到 r1 中*/*MERGEPASS*/while(i=mid)&(j=high)/*將兩個相鄰有序子表進(jìn)行合并*/ if(ai.key=aj.key)/*取兩表中小者復(fù)制*/while(i=mid) rk+=ai+;/*復(fù)制第一個有序子表的剩余記錄*/while(j=high) rk+=aj+;/*復(fù)制第二個有序子表的剩余記

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);/*趟歸并，結(jié)果存放在 r1 中 */len gth=2*le ngth;/*歸并后有序表的長度加倍*/merge_pass(r1,r,le ngth);/*再次歸并，結(jié)果存放在 r 中*/len gth=2*le ngth;/*再次將歸

15、并后有序表的長度加倍*/*MERGE_SORT*/void creat_ra ndn um(i nt *a )/*產(chǎn)生給定個數(shù)和范圍的隨機整數(shù)函數(shù)*/ int i;in t ran ge=30000;sran d(time(NULL);for(i=1;i=NUM;i+)ai=rand(); /*調(diào)用 rand 生成隨機整數(shù)*/prin tf(nnttt排序前的原始隨機整數(shù)為：nnt);for(i=1;i=NUM;i+) printf(%6d,ai); /*輸出隨機整數(shù) */if(i%10=0) pri ntf(nt);pri ntf(n);/*CREAT_RANDNUM*/void creat

16、e() /*產(chǎn)生 NUM 個隨機整數(shù)并保存到記錄數(shù)組 s 中*/ int bMAX;in t ran ge=30000,i;creat_ra ndn um(b); /*調(diào)用隨機整數(shù)生成函數(shù)，結(jié)果存放在數(shù)組b 中*/for(i=1;i=NUM;i+)si.key=bi;/*將隨機整數(shù)存放到數(shù)組 s 中*/S 仁 s;/*s1指向 s,以便保存原始數(shù)據(jù)*/10/*CREAT*/void prin t_record(rectype *r)/*記錄數(shù)組的輸出函數(shù) */ int i;prin tf(nttt排序后的有序隨機整數(shù)：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);/*清屏函數(shù)*/printf( 內(nèi)排序算法的比較-主控模塊: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請按數(shù)位 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(); /*進(jìn)入主菜單選擇模塊 */if(kk!=O) create(); /*建立記錄數(shù)組 */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 測試結(jié)果13巧 * DACbOebuggg.exe .J 叵內(nèi)排序算法的比較一主控模塊:請按數(shù)字Q-7鍵選擇功能:(1)選擇直接插入排序:入序序序擇并插排排排選序歸接爾泡速接排路岀直希冒快直堆二退12312356

23、70567014直接選擇排序堆排序二路歸并排序排序前本有 3000030000 個隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應(yīng)有 3000030000 個排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一 部分圖來表示。1SS9 25231277631B736逝299G7沖413113515253 103H7240521626211023879107823025730435409421B3627923251曲126551365022H 30831361G 26G54193573O0OH 26999內(nèi)排序算法的比較一一主控模塊:擂入排序1.請按數(shù)字-了鍵選擇功能：1排序前的原始隨機整數(shù)

24、為: O:CbXOebu ggg.exe5,7.15由圖可知，直接插入排序耗時 0.8780000.878000 秒16D:CbDebu ggg-e)ce直接插入排序耗時0.878GOO seconds排序后的有序隨機整數(shù):2223358g1013151 7132G2022222626272329292931333433535363?3S3941434343嶼帕4748H85152535357B0BG3G3G365655676S&9S9707172727272737575767676787881328282338385873903537961011921G31G310410510911

25、21121121 1411511511611E1 181201201211Z31241241261271Z712712713G13013213313313413513&13&1361371391391421421斗31451451451H71H81*91511511521S315315315315415H(2)選擇希爾排序: 排序前本有 3000030000 個隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應(yīng)有 3000030000 個排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一 部分圖來表示。由圖可知，希爾排序耗時 0.0260000.026000 秒 DACbD

26、EbLiggg啟畑17內(nèi)排序篦法的比較一一主控模塊:體按數(shù)字二;鍵選擇功蟲2琲序前的源妬陲機整數(shù)為:序序序-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內(nèi)排序算法的比較一一主控模塊:序序序-IJ.L.-kXL.Lkrfl fl fl入序序序擇并插排排排選序歸接爾泡速接排路出直希冒快直堆二退書按數(shù)字;一;鍵選擇功盛汕排序前的原始隨機整數(shù)為: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 個隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應(yīng)有 3000030000 個排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一 部分圖來表示。由圖可知，直接選擇排序耗時 1.5280001.528000 秒2425(6)選擇堆排序: 排序前本有 3000030000 個隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應(yīng)有 3000030000 個排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一 部分圖來表示。由圖可知，堆排序耗時 0.0080000.008000 秒 D:CbDebijggg.exe直接選擇排序耗時1-523903 seconds排序后的有序隨機整數(shù):223137GQ8550S77177871007480871Q3821041041051051Q61G310911211411511