1、數(shù)據(jù)結構課程設計報告課題：排序算法的比較學院:信息學院班級:2011級電子信息工程1班小組成員:韋志東（組長）20111601310027夏琪20111601310028完成時間:2014-01-08教師:周鐵目錄1.3、設計任務書27271、課程分析1.1 、選題要求利用隨機函數(shù)產(chǎn)生30000個隨機整數(shù)， 利用直接插入排序、 希爾排序， 冒泡排序、直接選擇排序、快速排序、堆排序、歸并排序的排序方法進行排序，并統(tǒng)計每一種排序上機所花費的時間。1.2 、選題的意義及背景排序是計算機程序設計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關鍵詞有序的序列。此實驗通過對各種內(nèi)部

2、排序算法進行比較，能使我們更好的掌握各種排序的基本思想， 掌握各種排序方法的算法實現(xiàn)， 掌握各種排序方法的優(yōu)劣分析及花費的時間的計算， 掌握各種排序方法所適應的不同場合。 通過該題目的設計， 可以加深理解各種數(shù)據(jù)結構的邏輯結構、 存儲結構及相應上運算的實現(xiàn)， 進一步理解和熟練掌握課本中所學的各種數(shù)據(jù)結構， 學會如何把學到的知識用于解決實際問題，培養(yǎng)我們的動手能力。1.3 、設計任務書（ 1）定義結構體，頭文件，定義數(shù)組范圍，大小。（ 2）依次描寫七種排序的算法。（ 3）描寫產(chǎn)生隨機函數(shù)的算法。（ 4）描寫菜單函數(shù)。（ 5）描寫主函數(shù)，調用七種排序的算法。2、設計分析2.1 原始資料用戶輸入記錄

3、的個數(shù)3000Ot,數(shù)據(jù)由隨機函數(shù)生成2.2 輸出數(shù)據(jù)產(chǎn)生的隨機數(shù)分別用冒泡排序、直插排序、希爾排序、選擇排序、快速排序、 堆排序、歸并排序這些排序方法進行排序，并統(tǒng)計每一種排序上機所花費的時間。輸出排序上機所花費的時間3程序源代碼及其注釋#include "stdio.h"#include "stdlib.h"#include "math.h"#include<time.h>#include<conio.h>#define MAX 60000 /* 記錄數(shù)組的個數(shù)*/#define NUM 30000 /*

4、實際輸入數(shù)組的個數(shù)*/typedef int datatype;typedef struct /* 定義記錄為結構體類型*/ int key; /* 記錄的關鍵詞域 */datatype other; /* 記錄的其它域*/ rectype;rectype *s1,sMAX;/*sMAX 存放原始隨機數(shù)， *s1 取出原始數(shù)據(jù)后進行排序 */* 直接插入排序算法如下 */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*/對數(shù)組 r 按遞增順序進行插入排序算法*/為實際輸入的記錄數(shù)，是一個常量*/條件很重要，NUM；實際記錄數(shù)*/為監(jiān)視哨 */依次插入記錄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/實際輸入記錄數(shù)*/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; /* 若本趟排序中未發(fā)生記錄交換，則終止排序*/*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)快速排序算法中的一趟劃分函數(shù)*/初始化，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); /*遞歸處理左區(qū)間 */quick_sort(r,i+1,ht); /*遞歸處理右區(qū)間 */*QUICK_SORT*/* 直接選擇排序算法如下 */void select_sort(rectype *

11、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+)/* 在當前無序區(qū)中選擇關鍵詞最小的記錄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)/*堆的篩選算法,在數(shù)組中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的值，以便繼續(xù)“篩”結點 */j=2*i;elsej=m+2;/* 調整完畢，退出循環(huán)*/ri=temp;/* 將被篩選的結點放入正確的位置

13、*/*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;i-)/* 進行 n-1 趟篩選，交換，調整，完成堆排序*/ temp=r1;/* 將堆頂元素 r1 與最后一個元素交換位置*/r1=ri;ri=temp;shift(r,1,i-1);/*將數(shù)組元素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 )/* 產(chǎn)生給定個數(shù)和范圍的隨機整數(shù)函數(shù)*/ int i;int range=30000;srand(time(NULL);for(i=1;i<=NUM;i+)ai=rand(); /*調用 rand 生成隨機整數(shù)*/printf("nnttt排序前的原始隨機整數(shù)為 :nnt");for(i=1;i<=NUM;i+) printf("%6d",ai); /*輸出隨機整數(shù)*/if(i%10=0) printf("nt");printf("n");

18、/*CREAT_RANDNUM*/void create。/* 產(chǎn)生NUMb隨機整數(shù)并保存到記錄數(shù)組s中*/ int bMAX;int range=30000,i;creat_randnum(b);/*調用隨機整數(shù)生成函數(shù)，結果存放在數(shù)組b中*/for(i=1;i<=NUM;i+)si.key=bi;/*將隨機整數(shù)存放到數(shù)組 s中*/s1=s;/*s1 指向 s, 以便保存原始數(shù)據(jù)*/*CREAT*/void print_record(rectype *r)/*記錄數(shù)組的輸出函數(shù) */ int i;printf("nttt 排序后的有序隨機整數(shù) :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");/* 清屏函數(shù) */printf(" 內(nèi)排序算法的比較 主控模塊 :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請按數(shù)位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(); /*建立記錄數(shù)組 */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"內(nèi)排序算法的比較-主擰模塊;入序序序擇并 插排排排選序歸 接爾泡速接排路出 直希冒快直堆二退 1235670請按數(shù)字。一了犍選擇功能:(1)選擇直接插入排序:排序前本有3000Ot隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也

26、一樣，應有3000辦排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一 部分圖來表示。(2)選擇希爾排序:排序前本有3000Ot隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應有3000辦排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一 部分圖來表示由圖可知，希爾排序耗時0.026000秒由圖可知，冒泡排序耗時3.456000秒(3)選擇冒泡排序：排序前本有3000Ot隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應有3000辦排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一 部分圖來表示。* * D:CbDebuggg.exe*排序前的原始隨機整數(shù)為:直接插入排序 希爾排序 冒泡排

27、序 快速排序 直接選擇排序 堆排序 二路歸并排序 退出請按數(shù)字。一7鍵選擇功能： 請按數(shù)字。一7鍵選擇功能：342349338918219459635631252309572650485591971516159184865343935719507271661817027901255661035329506196171862423201300661896522935196512875910179376359442224163152756265402938128961466873262454164677129245771985223636228985795283242875825806580480

28、4913954616553214510723219250661243418945228305672268551435218162775627996799421827212911243811G102680140221471163312582717618731216168267731961894326710170642708695329925295365086290942558619919253191146。287211985724170438526793298821317715767160321793356598479174011214320978227592482630875199951347

29、72235525822134218041391682941930364602575916255940419615252383135823887198251093425497311827104211641442215301877209667676121092862444375832940719195103532979225226259442751825721774043481204695085870(4)選擇快速排序:排序前本有3000Ot隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示 排序后也一樣，應有3000口排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一 部分圖來表示由圖可知，快速排序耗時0.0

30、05000秒由圖可知，直接選擇排序耗時1.528000秒(5)選擇直接選擇排序：排序前本有3000Ot隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應有3000辦排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一 部分圖來表示。1 .直接插入排序2 .希爾排序3 .冒泡排序4 .快速排序5 .直接選擇排序6 .堆排序7 .二路歸并排序0.退出請按數(shù)字。一7謔選擇功能：請按數(shù)字。一7誕選擇功能：5排序前的原始隨機整數(shù)為:57266160138776345152523527115553222817716280961410258473026516203245208171876126852102

31、37132233512165173188817607189532655628845123998023200423170631644317322900137442387624911652010126391116667214601472111172137412263218210271126566213492244720717171071752510H951248。25681267011708838947235412470520228160532839434852354820941474820337273941198322229816828893283775501502111073383981472

32、91909328566277387721859322266443313585223127529677230075902215068145921447512595291351611116036370525992128999388574511701380828780378713332991315418134682386514536178778112119163682257442870555211370610931312721342。111091385425652224362799297432744931015509923782167152983877122695114955206431965018

33、688152651692856796988826719386296601205524848G302011036831968894033143722762293831868822933128053234531719290081786828001(6)選擇堆排序：排序前本有3000Ot隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應有3000辦排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一 部分圖來表示。由圖可知，堆排序耗時0.008000秒 * D:CbDebuggg.exe *序 序序 入序序序擇并 插排排排選序歸 接爾泡速接排路出 直希冒快直堆二退 12345670請按數(shù)字。一7謔

34、選擇功能： 請按數(shù)字。一7誕選擇功能：6 排序前的原始隨機整數(shù)為:61256746306182571814719110683082627805143169528825112211146421424237136144137561373742932417199484648286892142。3104H322397G482358414748166524606216542738221004412626138135684460117102386513793228643245022363189931368715165231245705223831301826131350269173963290321181

35、612032110393836772013839320097997106652969525119211281085323345175522620513227366026297216862160010799218343479149172769017572283916775215723942282868281760015593108793148411125110482148。42382729120068100871656613173235912673621739118193655474880292195024334135561439920545206311135882245959172751205

36、52765611768366244G2240985928232032246441421097248726208485726911101882703310022123721208490229486148H02603323206174381369117987232331036316034233864117612631285251161885048782400221484197282955173905403123442843928359133122762228721(7)選擇二路歸并排序：排序前本有3000Ot隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應有3000辦排好順序的整數(shù)顯示

37、，但由于數(shù)據(jù)過多，也只截一 部分圖來表示。由圖可知，二路歸并排序耗時0.006000秒 *D:CbDebuggg.exe*序 序序 入序序序擇并 插排排排選序歸 接爾泡速接排路出 直希冒快直堆二退 12345670請按數(shù)字。一7謔選擇功能： 請按數(shù)字。一7誕選擇功能：7 排序前的原始隨機整數(shù)為:6523733114591123222791331377173296100160802527107811659425431846。1141324239875262330948188433615255462549。252331Q367515418019200221474132621027311665230

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