數(shù)據(jù)結(jié)構(gòu)課程設(shè)計各種排序算法比較

1、課程設(shè)計課程：數(shù)據(jù)結(jié)構(gòu)題目：排序算法比較專業(yè)班級：姓名：學(xué)號：設(shè)計時間：指導(dǎo)教師：一、設(shè)計題目排序算法比較二、運行環(huán)境（軟、硬件環(huán)境）操作系統(tǒng)windows7運行環(huán)境vc6.0三、算法設(shè)計的思想大架構(gòu)采用模塊化編程的思想，將每個不同的功能分別寫成不同的子程序，分別進行封裝構(gòu)成各個小的模塊，最后將各個模塊組合起來。在每個子程序的編寫過程中特事特辦面對不同的預(yù)想功能采取不同的數(shù)據(jù)結(jié)構(gòu)不同的算法實現(xiàn)?？傮w算法思想為按功能分塊，依照預(yù)想功能實現(xiàn)順序拼裝。具體思想請見流程圖。四、流程圖是結(jié)束程序編寫流程圖choice1=1五、算法設(shè)計分析程序總體采用模塊化設(shè)計，程序間通過傳參和調(diào)用進行有機組合。這樣的總

2、體布局將將各個功能隔離開來，每個模塊負(fù)責(zé)每個模塊的功能，使得程序的布局簡單明了。且子程序只有在被調(diào)用時才會運行大大節(jié)約系統(tǒng)資源減少了運算時間。同時由于功能的隔離使得程序的擴展性大大提高，無論程序?qū)⒁魏胃膭訒r，都會方便很多。六、源代碼#include#include#includeinta30000;intchoice;intchoice1;structxlxintkey;intlink;aa30000;intaaa300000;voidmain1();I*生成隨機數(shù)函數(shù)*/voidsjs()inti=0,j,b,h,l;printf(請輸入你所期望的將要生成隨機數(shù)的取值范圍：n);print

3、f(最小值(不能為負(fù)數(shù))：)；scanf(%d,&l);printf(最大值(無上限)：);scanf(%d,&h);srand(int)time(0);for(j=0;i=l&b=h)(ai=b;aai.key=b;aaai=b;i+;for(i=0;i30000;i+)printf(%d,ai);/*直接插入排序函數(shù)*voiddirect(inta)printf(n現(xiàn)在使用直接插入排序法進行排序：n);inti,j,w;for(i=0;i=0;j-)w=aj;aj=aj+1;aj+1=w;/*/voidbubble_sort(inta)printf（n下面使用冒泡排序法進行排序:）;int

4、i,j,w;for(i=0;i30000;i+)for(j=0;jaj+1)w=aj;aj=aj+1;/*aj+1=w;選擇排序*/voidchoices_sort(inta)printf（n現(xiàn)在使用選擇排序法進行排序：n）;inti,j,k,t;for(i=0;i30000;i+)(k=i;for(j=i+1;jaj)k=j;t=ai;ai=ak;ak=t;)/*快速排序*/quick(intfirst,intend,intL)(intleft=first,right=end,key;key=Lfirst;while(leftright)while(left=key)right-;if(le

5、ftright)Lleft+=Lright;while(leftright)&(Lleft=key)left+;if(leftright)Lright-=Lleft;Lleft=key;returnleft;voidquick_sort(intL,intfirst,intend)intsplit;if(firstend)split=quick(first,end,L);quick_sort(L,first,split-1);quick_sort(L,split+1,end);/*堆排序*/voidsift(int*x,intn,ints)intt,k,j;t=*(x+s);k=s;j=2*k+

6、1;while(jn)if(jn-1&*(x+j)*(x+j+1)足就繼續(xù)下一輪比較，否則調(diào)整。*/*暫存開始元素*/*開始元素下標(biāo)*/*右子樹元素下標(biāo)*/*判斷是否滿足堆的條件：滿j+;)if(t=0;i-)(sift(x,n,i);)for(k=n-1;k=1;k-)(t=*(x+0);*(x+0)=*(x+k);*(x+k)=t;sift(x,k,0);)/*調(diào)整*/*調(diào)整后，開始元素也隨/*沒有需要調(diào)整了，已經(jīng)/*開始元素放到它正確/*初始建堆*/*堆頂放到最后*/*剩下的數(shù)再建堆*/I*歸并排序*/intlistmerge(structxlxlist,intfirst,intseco

7、nd)/*遞歸傳遞*/(intstart=30000;while(first!=-1&second!=-1)if(listfirst.key=upper)returnlower;elsemiddle=(lower+upper);returnlistmerge(list,rmerge(list,lower,middle),rmerge(list,middle+1,upper);*voidtime(intchoice)doublet1,t2,t;inti;t1=(double)clock();if(choice=1)direct(a);if(choice=2)bubble_sort(a);if(c

8、hoice=3)choices_sort(a);if(choice=4)printf(n現(xiàn)在使用快速排序法進行排序：n);quick_sort(a,0,29999);if(choice=5)heap_sort(a,30000);if(choice=6)rmerge(aa,0,29999);t2=(double)clock();t=difftime(t2,t1)/1000;for(i=0;i30000;i+)printf(%d,ai);printf（n排序結(jié)束您所用排序時間為：秒坨1）;菜單函數(shù)*/*voidmenu(intchoice1)inti;if(choice1=1)for(i=0;i=

9、30000;i+)ai=aaai;aai.key=aaai;main1();)if(choice1=2)(printf(謝謝使用，再見！);)voidmain1()printf(nn請選擇你所希望使用的排序方法：nn1。直接插入排序n2。冒泡排序n3。選擇排序n4?？焖倥判騨5。堆排序n6。歸并排序n);scanf(%d”,&choice);time(choice);printf(nn排序完畢，請選擇下一步您要完成的工作：nn1.返回選擇另一種排序方法排序n2.退出n);scanf(%d,&choice1);menu(choice1);)/*主函數(shù)*/voidmain()sjs();main1

10、();)七、運行結(jié)果分析C;UsersAdministratorDesktopciWDebijgCpplexe生成30000個隨機數(shù)4912306146492821711084142203362807319456121451075918423120341472152681007020請選擇你所希望使用的排序方法；序二入序亡u.lur/二二.一卜ILIkHplL二二二二r*l*L二靠茬排開直冒選歸選擇使用排序算法.32752327533275532755327553275732非序結(jié)束您所用排序時間為：448。碉秒非序完畢，請選擇下一步您要完成的工作,一返晅選擇另一種排序方法排序L退出直接排序排

11、序所用時間32731327323273232736327383273832739!7453274932749327513275132752327533)43276432764俳序結(jié)束您所用排序時間為，九76萌的秒排序完畢，請選擇下一步您要完成的工作：增用選擇另一種排序方法排序?.退出冒泡排序所用時間I32738327393274132742327433274532(2752327533275532755327553275?3276俳序結(jié)束您所用排序時間為：1.575000俳序完畢，請選擇下一步您要完成的工作,返回選擇另一種排序方法排序L退出選擇排序所用時間5132751327513275232

12、7533275s327ss32755327563275732757327583278327s932759327593276032760327603276132761327B1327613276332764327653276532765排束您所用排序時間為：目加西。砥秒排序完畢，請選1圣下一步您要完成的工作；1 .謳日選擇另一種排序方法排序2 .退出快速排序所用時間83273832739327413274232743327453213275232753327553275532755327573276：心序結(jié)束您所用排序時間為工目.幅160秒，序完畢，請選擇下一步您要完成的工作：1,返日選擇另一種排序方法排序3 .退出堆排序所用時間各排序排序時間分別為：直接排序：3.448秒冒泡排序：3.76秒選擇排序：1.575秒快速排序：0.00秒堆排序：0.016秒歸并排序：7.487秒（注：此處快速排序弁非排序時間為0,而是時間很短在表示范圍外，當(dāng)實驗數(shù)據(jù)擴大到一定數(shù)值后會有相應(yīng)時間顯示）通過數(shù)據(jù)不難看出6種排序方法處理一組相同數(shù)據(jù)時，快速排序處理速度最快堆排序次之，歸弁排序最慢。六.課設(shè)心得整個程序前前后后整整用了一個星期，每天只要有空閑時間就在翻書本，畫流程圖，寫代