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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告課題：排序算法的比較學院:信息學院班級：2011級電子信息工程1班小組成員：韋志東（組長）20111601310027夏琪20111601310028完成時間:2014-01-08教師:周鐵目錄1、課程分析1.1、 選題2.1.2、 選題的意義及背景2.1.3、 設(shè)計任務(wù)書22、設(shè)計分析2.1、原始數(shù)據(jù)錯誤！未定義書簽。2.2、輸出數(shù)據(jù)錯誤！未定義書簽。2.3、程序流程圖3.3、程序源代碼及注釋4、測試結(jié)果錯誤！未定義書簽。5、總結(jié)266、參考文獻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)，進一步理解和熟練掌握課本中所學的各種數(shù)據(jù)結(jié)構(gòu)，學會如何把學到的知識用于解決實際問題，培養(yǎng)我們的動手能力。

3、1.3、 設(shè)計任務(wù)書(1)定義結(jié)構(gòu)體，頭文件，定義數(shù)組范圍，大小。(2)依次描寫七種排序的算法。(3)描寫產(chǎn)生隨機函數(shù)的算法。(4)描寫菜單函數(shù)。(5)描寫主函數(shù)，調(diào)用七種排序的算法。2、設(shè)計分析2.1 原始資料用戶輸入記錄的個數(shù)30000t,數(shù)據(jù)由隨機函數(shù)生成。2.2 輸出數(shù)據(jù)產(chǎn)生的隨機數(shù)分別用冒泡排序、直插排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序這些排序方法進行排序，并統(tǒng)計每一種排序上機所花費的時間。2.3程序流程圖主程序LJ產(chǎn)生1組隨機數(shù)將隨機數(shù)保存在數(shù)組中#include"stdlib.h"#include"math.h"#inclu

4、de<time.h>#include<conio.h>#defineMAX60000/*記錄數(shù)組的個數(shù)*/#defineNUM30000/*實際輸入數(shù)組的個數(shù)*/typedefintdatatype;typedefstruct/*定義記錄為結(jié)構(gòu)體類型*/intkey;/*記錄的關(guān)鍵詞域*/datatypeother;/*記錄的其它域*/rectype;rectype*s1,sMAX;/*sMAX存放原始隨機數(shù)，*s1取出原始數(shù)據(jù)后進行排序*/*直接插入排序算法如下*/voidinsert_sort(rectype*r)/*inti,j,n=NUM;/*NUMfor(i=

5、1;i<=n;i+)/*i<NUMr0=ri;/*r0j=i-1;/*while(r0.key<rj.key)/*巾+1=rj-;/*rj+1=r0;/*對數(shù)組r按遞增順序進行才1入排序算法*/為實際輸入的記錄數(shù)，是一個常量*/條件很重要，NUM；實際記錄數(shù)*/為監(jiān)視哨*/依次插入記錄r1,rNUM*/查找ri合適的位置*/將記錄關(guān)鍵詞大于ri.key的記錄后移*/將記錄ri插入到有序表的合適的位置上*/*INSERTSORT*/*希爾排序算法如下*/voidshell_sort(rectype*r)/*取增量為d(i+1)=d(i)/2的希爾排序的算法*/inti,n,ju

6、mp,change,temp,m;/*change為交換標志，jump為增量步長*/jump=NUM;n=NUM;/*NUM為順序表的實際長度*/while(jump>0)jump=jump/2;/*取步長d(i+1)=d(i)/2*/dochange=0;/*設(shè)置交換標志，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

7、*/*本趟排序完成*/while(change=1);/*當change=0時終止本趟排序*/*while*/*當增量jump=1且change=0時終止算法*/*SHELLSORT*/*冒泡排序算法如下*/voidbubble_sort(rectype*r)/*從下往上掃描的冒泡排序*/inti,j,noswap=0,n=NUM;/*noswap為交換標志，NUM實際輸入記錄數(shù)*/rectypetemp;for(i=1;i<n;i+)noswap=1;for(j=n;j>=i;j-)if(rj.key<rj-1.key)/*進行n-1趟冒泡排序*/*設(shè)置交換標志，noswa

8、p=1表示沒有記錄交換*/*從下往上掃描*/*交換記錄*/temp.key=rj-1.key;rj-1.key=rj.key;rj.key=temp.key;noswap=0;/*當交換記錄時，將交換標志置0即noswap=0*/if(noswap)break;/*若本趟排序中未發(fā)生記錄交換，則終止排序*/*for*/*終止排序算法*/*BUBBLESORT*/*快速排序算法如下*/intpartition(rectype*r,ints,intt)/*快速排序算法中的一趟劃分函數(shù)*/inti,j;rectypetemp;i=s;j=t;temp=ri;/*初始化，temp為基準記錄*/dowh

9、ile(rj.key>=temp.key)&&(i<j)j-;/*從右往左掃描，查找第一個關(guān)鍵詞小于temp的記錄*/if(i<j)ri+=rj;/*交換ri和rj*/while(ri.key<=temp.key)&&(i<j)i+;/*從左往右掃描，查找第一個關(guān)鍵詞大于temp的記錄*/if(i<j)rj-=ri;/*交換ri和rj*/while(i!=j);/*i=j,z則一次劃分結(jié)束，基準記錄達到其最終位置*/ri=temp;/*最后將基準記錄temp定位*/return(i);/*PARTITION*/voidquic

10、k_sort(rectype*r,inths,intht)/*rhs至1Jrht進行快速排序*/inti;if(hs<ht)/*只有一個記錄或無記錄時無需排序*/i=partition(r,hs,ht);/*rhs至1Jrht進行一次劃分*/quick_sort(r,hs,i-1);/*遞歸處理左區(qū)間*/quick_sort(r,i+1,ht);/*遞歸處理右區(qū)間*/*QUICK_SORT*/*直接選擇排序算法如下*/voidselect_sort(rectype*r)rectypetemp;inti,j,k,n=NUM;/*NUM為實際輸入t己錄數(shù)*/for(i=1;i<=n;i

11、+)/*做n-1趟選擇排序*/k=i；for(j=i+1;j<=n;j+)/*在當前無序區(qū)中選擇關(guān)鍵詞最小的記錄rk*/if(rj.key<rk.key)k=j;if(k!=i)temp=ri;/*交換記錄ri和rk*/ri=rk;rk=temp;/*for*/*SELECT_SORT*/堆的篩選算法，在數(shù)組中ri至km中，調(diào)整堆/*堆排序算法如下*/voidshift(rectype*r,inti,intm)/*ri*/intj;rectypetemp;temp=ri;j=2*i;while(j<=m)/*j<=m,r2*i是ri的左孩子*/if(j<m)&am

12、p;&(rj.key<rj+1.key)j+;/*j指向ri的左右孩子中關(guān)鍵詞較大者*/if(temp.key<rj.key)/*若孩子結(jié)點的關(guān)鍵詞大于父結(jié)點*/ri=rj;/*將rj調(diào)到父親結(jié)點的位置上*/i=j;/*調(diào)整i和j的值，以便繼續(xù)“篩”結(jié)點*/j=2*i;elsej=m+2;/*調(diào)整完畢，退出循環(huán)*/ri=temp;/*將被篩選的結(jié)點放入正確的位置*/*SHIFT*/voidheap_sort(rectype*r)/*對數(shù)組r1至kNUM進行堆排序*/rectypetemp;inti,n;n=NUM;/*NUM為數(shù)組的實際長度*/for(i=n/2;i>

13、0;i-)/*建立初始堆*/shift(r,i,n);for(i=n;i>1;i-)/*進行n-1趟篩選，交換，調(diào)整，完成堆排序*/temp=r1;/*將堆頂元素r1與最后一個元素交換位置*/r1=ri;ri=temp;shift(r,1,i-1);/*將數(shù)組元素r1至hi-1重新調(diào)整成為一個新堆*/*FOR*/*HEAP_SORT*/*二路歸并排序算法如下*/voidmerge(rectype*a,rectype*r,intlow,intmid,inthigh)inti,j,k;將兩個相鄰有序子表進行合并*/i=low;j=mid+1;k=low;while(i<=mid)&am

14、p;&(j<=high)/*if(ai.key<=aj.key)/*取兩表中小者復制*/rk+=ai+;elserk+=aj+;while(i<=mid)rk+=ai+;/*復制第一個有序子表的剩余記錄*/while(j<=high)rk+=aj+;/*復制第二個有序子表的剩余記錄*/*MERGE*/voidmerge_pass(rectype*r,rectype*r1,intlength)inti=1,j,n=NUM;while(i+2*length-1)<=n)/*歸并若干長度為2*length的兩個相鄰有序子表*/merge(r,r1,i,i+len

15、gth-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的部分*/elsefor(j=i;j<=n;j+)r1j=rj;/*將最后一個子表復制到r1中*/*MERGEPASS*/voidmerge_sort(rectype*r)intlength;rectyper1MAX;length=1;/*歸并長度從1開始*/while(length<NUM)merge_pass(r,r1,length);/*一趟歸并，結(jié)果存放

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

17、;i<=NUM;i+)printf("%6d",ai);/*輸出隨機整數(shù)*/if(i%10=0)printf("nt");printf("n");/*CREAT_RANDNUM*/voidcreate()/*產(chǎn)生NUMb隨機整數(shù)并保存到記錄數(shù)組s中*/intbMAX;intrange=30000,i;b中*/creat_randnum(b);/*調(diào)用隨機整數(shù)生成函數(shù)，結(jié)果存放在數(shù)組for(i=1;i<=NUM;i+)si.key=bi;/*將隨機整數(shù)存放到數(shù)組s中*/s1=s;/*s1指向s,以便保存原始數(shù)據(jù)*/*CREA

18、T*/voidprint_record(rectype*r)/*記錄數(shù)組的輸出函數(shù)*/inti;printf("nttt排序后的有序隨機整數(shù)：nnt");for(i=1;i<=NUM;i+)printf("%6d",ri.key);if(i%10=0)printf("nn't");getchar();getchar();/*PRINTRECORD*/intmenu_select()/*主菜單選擇模塊*/charc;intkk;system("cls");/*清屏函數(shù)*/printf("內(nèi)排序

19、算法的比較一主控模塊：nn");printf("ttt1.直接插入排序n");printf("ttt2.希爾排序n");printf("ttt3.冒泡排序n");printf("ttt4.快速排序n");printf("ttt5.直接選擇排序n");printf("ttt6.堆排序n");printf("ttt7.二路歸并排序n");printf("ttt0.退出n");doprintf("nttt請按數(shù)位07鍵選擇

20、功能：“c=getchar();kk=c-48;while(kk<0)|(kk)>7);return(kk);/*MENU_SELECT*/main()/*算法比較-主程序模塊*/(doubletimel,time2,time3,time4,time5,time6,time7;clock_tstart,finish;intkk;dokk=menu_select();/*進入主菜單選擇模塊*/if(kk!=0)create();/*建立記錄數(shù)組*/switch(kk)case1:start=clock();insert_sort(s1);finish=clock();time1=(d

21、ouble)(finish-start)/CLOCKS_PER_SEC;printf("直接插入排序耗時fsecondsn",time1);break;case2:start=clock();shell_sort(s1);finish=clock();time2=(double)(finish-start)/CLOCKS_PER_SEC;printf("希爾排序耗時%fsecondsn",time2);break;case3:start=clock();bubble_sort(s1);finish=clock();time3=(double)(finis

22、h-start)/CLOCKS_PER_SEC;printf("冒泡排序耗時%fsecondsn",time3);break;case4:start=clock();quick_sort(s1,1,NUM);finish=clock();time4=(double)(finish-start)/CLOCKS_PER_SEC;printf("快速排序耗時%fsecondsn",time4);break;case5:start=clock();select_sort(s1);finish=clock();time5=(double)(finish-start

23、)/CLOCKS_PER_SEC;printf("直接選擇排序耗時%fsecondsn",time5);break;case6:start=clock();heap_sort(s1);finish=clock();time6=(double)(finish-start)/CLOCKS_PER_SEC;printf("堆排序耗時fsecondsn",time6);break;case7:start=clock();merge_sort(s1);finish=clock();time7=(double)(finish-start)/CLOCKS_PER_SE

24、C;printf("二路歸并排序耗時%fsecondsn",time7);break;case0:exit(0);print_record(s1);while(kk!=0);/*MAIN*/4.測試結(jié)果(1)選擇直接插入排序：排序前本有30000t隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應(yīng)有3000辦排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一部分圖來表示。由圖可知，直接插入排序耗時0.878000秒(2)選擇希爾排序：排序前本有30000t隨機數(shù)顯示，但數(shù)據(jù)太多，只截一部分圖來表示。排序后也一樣，應(yīng)有3000辦排好順序的整數(shù)顯示，但由于數(shù)據(jù)過多，也只截一

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