數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)各種排序算法比較_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)各種排序算法比較_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)各種排序算法比較_第3頁(yè)
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)各種排序算法比較_第4頁(yè)
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)各種排序算法比較_第5頁(yè)
免費(fèi)預(yù)覽已結(jié)束,剩余13頁(yè)可下載查看

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

2、體布局將將各個(gè)功能隔離開來,每個(gè)模塊負(fù)責(zé)每個(gè)模塊的功能,使得程序的布局簡(jiǎn)單明了。且子程序只有在被調(diào)用時(shí)才會(huì)運(yùn)行大大節(jié)約系統(tǒng)資源減少了運(yùn)算時(shí)間。同時(shí)由于功能的隔離使得程序的擴(kuò)展性大大提高,無論程序?qū)⒁魏胃膭?dòng)時(shí),都會(huì)方便很多。六、源代碼#include#include#includeinta30000;intchoice;intchoice1;structxlxintkey;intlink;aa30000;intaaa300000;voidmain1();I*生成隨機(jī)數(shù)函數(shù)*/voidsjs()inti=0,j,b,h,l;printf(請(qǐng)輸入你所期望的將要生成隨機(jī)數(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)在使用直接插入排序法進(jìn)行排序:n);inti,j,w;for(i=0;i=0;j-)w=aj;aj=aj+1;aj+1=w;/*/voidbubble_sort(inta)printf(n下面使用冒泡排序法進(jì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)在使用選擇排序法進(jì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)在使用快速排序法進(jì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é)束您所用排序時(shí)間為:秒坨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請(qǐng)選擇你所希望使用的排序方法:nn1。直接插入排序n2。冒泡排序n3。選擇排序n4??焖倥判騨5。堆排序n6。歸并排序n);scanf(%d”,&choice);time(choice);printf(nn排序完畢,請(qǐng)選擇下一步您要完成的工作:nn1.返回選擇另一種排序方法排序n2.退出n);scanf(%d,&choice1);menu(choice1);)/*主函數(shù)*/voidmain()sjs();main1

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

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論