




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、課 程 設(shè) 計 課程:數(shù)據(jù)結(jié)構(gòu) 題目:排序算法比較 專業(yè)班級: 姓名: 學(xué)號: 設(shè)計時間: 指導(dǎo)教師:一、 設(shè)計題目排序算法比較二、 運行環(huán)境(軟、硬件環(huán)境)操作系統(tǒng)windows運行環(huán)境vc6.0三、 算法設(shè)計的思想大架構(gòu)采用模塊化編程的思想,將每個不同的功能分別寫成不同的子程序,分別進(jìn)行封裝構(gòu)成各個小的模塊,最后將各個模塊組合起來。在每個子程序的編寫過程中特事特辦面對不同的預(yù)想功能采取不同的數(shù)據(jù)結(jié)構(gòu)不同的算法實現(xiàn)。總體算法思想為按功能分塊,依照預(yù)想功能實現(xiàn)順序拼裝。具體思想請見流程圖。四、 流程圖開始功能流程圖請用戶輸入將要生成隨機(jī)數(shù)的上下限,按照上下限生成30000個隨機(jī)數(shù)并輸出隨機(jī)生成
2、隨機(jī)數(shù)并輸出請用戶選擇想要使用的排序方法計算其使用的排序時間并輸出詢問用戶是否繼續(xù)運行程序否是輸出結(jié)束語句結(jié)束程序編寫流程圖開始定義全局變量a30000,aaaa3000,結(jié)構(gòu)體數(shù)組aa30000用來存放隨機(jī)數(shù),choice,choice1編寫各個子算法子函數(shù),和時間選擇函數(shù),既菜單選擇函數(shù),部分需要聲明的函數(shù)在頭文件下聲明。各模塊依據(jù)功能流程圖組裝結(jié)束算法流程圖開始局部變量l,h收集上下限,sjs()將用戶選擇數(shù)值賦值于choice,將choice作為參數(shù)調(diào)用time(),用if語句判斷選擇將要調(diào)用的算法子函數(shù)main1()menu()choice1=1Choice1=2結(jié)束五、 算法設(shè)計分
3、析 程序總體采用模塊化設(shè)計,程序間通過傳參和調(diào)用進(jìn)行有機(jī)組合。這樣的總體布局將將各個功能隔離開來,每個模塊負(fù)責(zé)每個模塊的功能,使得程序的布局簡單明了。且子程序只有在被調(diào)用時才會運行大大節(jié)約系統(tǒng)資源減少了運算時間。同時由于功能的隔離使得程序的擴(kuò)展性大大提高,無論程序?qū)⒁魏胃膭訒r,都會方便很多。六、 源代碼#include<stdio.h>#include<time.h>#include<stdlib.h>int a30000;int choice;int choice1;struct xlxint key;int link; aa30000;int aaa3
4、00000;void main1();/*直接插入排序函數(shù)*/void direct(int a)printf("n現(xiàn)在使用直接插入排序法進(jìn)行排序:n");int i,j,w; for(i=0;i<30000;i+) for(j=i;j>=0;j-) if(aj>=aj+1) w=aj; aj=aj+1; aj+1=w; /*冒泡排序函數(shù)*/void bubble_sort(int a) printf("n下面使用冒泡排序法進(jìn)行排序:"); int i,j,w; for(i=0;i<30000;i+) for(j=0;j<3
5、0000-i;j+)if(aj>aj+1) w=aj; aj=aj+1; aj+1=w; /*選擇排序*/void choices_sort(int a) printf("n現(xiàn)在使用選擇排序法進(jìn)行排序:n"); int i,j,k,t; for(i=0;i<30000;i+) k=i; for(j=i+1;j<30000;j+) if(ak>aj) k=j; t=ai; ai=ak; ak=t; /*快速排序*/ quick(int first,int end,int L) int left=first,right=end,key; key=Lfir
6、st; while(left<right) while(left<right)&&(Lright>=key) right-; if(left<right) Lleft+=Lright; while(left<right)&&(Lleft<=key) left+; if(left<right)Lright-=Lleft; Lleft=key; return left; void quick_sort(int L,int first,int end) int split; if(first<end) split=qui
7、ck(first,end,L); quick_sort(L,first,split-1); quick_sort(L,split+1,end); /*堆排序*/void sift(int *x, int n, int s) int t, k, j; t = *(x+s); /*暫存開始元素*/ k = s; /*開始元素下標(biāo)*/ j = 2*k + 1; /*右子樹元素下標(biāo)*/ while (j<n) if (j<n-1 && *(x+j) < *(x+j+1) /*判斷是否滿足堆的條件:滿足就繼續(xù)下一輪比較,否則調(diào)整。*/ j+; if (t<*(x+
8、j) /*調(diào)整*/ *(x+k) = *(x+j); k = j; /*調(diào)整后,開始元素也隨之調(diào)整*/ j = 2*k + 1; else /*沒有需要調(diào)整了,已經(jīng)是個堆了,退出循環(huán)。*/ break; *(x+k) = t; /*開始元素放到它正確位置*/void heap_sort(int *x, int n) int i, k, t; for (i=n/2-1; i>=0; i-) sift(x,n,i); /*初始建堆*/ for (k=n-1; k>=1; k-) t = *(x+0); /*堆頂放到最后*/ *(x+0) = *(x+k); *(x+k) = t; si
9、ft(x,k,0); /*剩下的數(shù)再建堆*/ /*歸并排序*/int listmerge(struct xlx list,int first,int second)/*遞歸傳遞*/int start=30000;while(first!=-1&&second!=-1)if(listfirst.key<=listsecond.key) liststart.link=first; first=listsecond.link;elseliststart.link=second;start=second;second=listsecond.link;if (first=-1) l
10、iststart.link=second;else liststart.link=first;return list30000.link;int rmerge(struct xlx list,int lower,int upper) /* 歸并并返回已排序的結(jié)果數(shù)組的起始位置*/int middle;if(lower>=upper)return lower;elsemiddle=(lower+upper);return listmerge(list,rmerge(list,lower,middle), rmerge(list,middle+1,upper); /*時間計算函數(shù)*/void
11、 timer(int choice)double t1,t2,t;int i;t1=(double) clock(); if(choice=1) direct(a);if(choice=2) bubble_sort(a);if(choice=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=
12、difftime(t2,t1)/1000;for(i=0;i<30000;i+) printf("%d ",ai);printf("n排序結(jié)束您所用排序時間為:%f秒n",t);/*菜單函數(shù)*/void menu(int choice1) int i;if (choice1=1) for(i=0;i<=30000;i+)ai=aaai;aai.key=aaai;main1();if (choice1=2)printf("謝謝使用,再見!");/*生成隨機(jī)數(shù)函數(shù)*/void sjs()int i=0,j,b,h,l;prin
13、tf("請輸入你所期望的將要生成隨機(jī)數(shù)的取值范圍:n");printf("最小值(不能為負(fù)數(shù)):");scanf("%d",&l);printf("最大值(無上限):");scanf("%d",&h);srand( (int) time(0);for(j=0;i<30000;j+)b=rand();if(b>=l&&b<=h)ai=b;aai.key=b;aaai=b;i+;for(i=0;i<30000;i+)printf("%
14、d ",ai); void main1()printf("nn請選擇你所希望使用的排序方法:nn1。直接插入排序n2。冒泡排序n3。選擇排序n4??焖倥判騨5。堆排序n6。歸并排序n");scanf("%d",&choice);timer(choice);printf("nn排序完畢,請選擇下一步您要完成的工作:nn1.返回選擇另一種排序方法排序n2.退出n");scanf("%d",&choice1);menu(choice1);/*主函數(shù)*/void main()sjs();main1
15、(); for (k=n-1; k>=1; k-) t = *(x+0); /*堆頂放到最后*/ *(x+0) = *(x+k); *(x+k) = t; sift(x,k,0); /*剩下的數(shù)再建堆*/ /*歸并排序*/int listmerge(struct xlx list,int first,int second)/*遞歸傳遞*/int start=30000;while(first!=-1&&second!=-1)if(listfirst.key<=listsecond.key) liststart.link=first; first=listsecond
16、.link;elseliststart.link=second;start=second;second=listsecond.link;if (first=-1) liststart.link=second;else liststart.link=first;return list30000.link;int rmerge(struct xlx list,int lower,int upper) /* 歸并并返回已排序的結(jié)果數(shù)組的起始位置*/int middle;if(lower>=upper)return lower;elsemiddle=(lower+upper);return li
17、stmerge(list,rmerge(list,lower,middle), rmerge(list,middle+1,upper); /*時間計算函數(shù)*/void time(int choice) double t1,t2,t;int i;t1=(double) clock(); if(choice=1) direct(a);if(choice=2) bubble_sort(a);if(choice=3) choices_sort(a);if(choice=4) printf("n現(xiàn)在使用快速排序法進(jìn)行排序:n"); quick_sort(a,0,29999); if(
18、choice=5) heap_sort(a,30000);if(choice=6) rmerge(aa,0,29999);t2=(double) clock();t=difftime(t2,t1)/1000;for(i=0;i<30000;i+) printf("%d ",ai);printf("n排序結(jié)束您所用排序時間為:%f秒n",t);/*菜單函數(shù)*/void menu(int choice1) int i;if (choice1=1) for(i=0;i<=30000;i+)ai=aaai;aai.key=aaai;main1();if (choice1=2)printf("謝謝使用,再見!"); void main1()printf("nn請選擇你所希望使用的排序方法:nn1。直接插入排序n2。冒泡排序n3。選擇排序n4。快速排序n5。堆排序n6。歸并排序n");scanf("%d",&choice);time(choice);printf("
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025至2030中國胸水細(xì)胞行業(yè)產(chǎn)業(yè)運行態(tài)勢及投資規(guī)劃深度研究報告
- 2025至2030中國胎壓監(jiān)測傳感器行業(yè)市場現(xiàn)狀分析及競爭格局與投資發(fā)展報告
- 2025至2030中國聚氨酯夾芯板行業(yè)產(chǎn)業(yè)運行態(tài)勢及投資規(guī)劃深度研究報告
- 2025至2030中國網(wǎng)上銀行行業(yè)市場深度調(diào)研及競爭格局與投資策略報告
- 2025至2030中國細(xì)胞學(xué)刷行業(yè)發(fā)展趨勢分析與未來投資戰(zhàn)略咨詢研究報告
- 2025至2030中國組氨酸(水解法)行業(yè)市場深度研究及發(fā)展前景投資可行性分析報告
- 全球車載火災(zāi)應(yīng)對技術(shù)與設(shè)備市場趨勢分析
- 大學(xué)生班干部述職報告5篇
- 2025至2030工業(yè)互聯(lián)網(wǎng)行業(yè)發(fā)展趨勢分析與未來投資戰(zhàn)略咨詢研究報告
- 2025至2030個人空氣取樣泵行業(yè)市場占有率及投資前景評估規(guī)劃報告
- 2024年廣東廣州市天河區(qū)社區(qū)專職工作人員招聘筆試參考題庫附帶答案詳解
- 電池的歷史與發(fā)展
- 醫(yī)患溝通原則與技巧課件
- 小學(xué)學(xué)業(yè)生涯規(guī)劃與目標(biāo)
- 2023年CQE客訴工程師年度總結(jié)及下年規(guī)劃
- 國家開放大學(xué)《中國法律史》形成性考核1
- 攪拌類設(shè)備單機(jī)試車原始記錄
- 老舊小區(qū)物業(yè)投標(biāo)方案(技術(shù)標(biāo))
- 國家開放大學(xué)法學(xué)本科《商法》歷年期末考試試題及答案題庫
- 城市水工程概論
- 空調(diào)溫度控制系統(tǒng)的設(shè)計與實現(xiàn)畢業(yè)論文
評論
0/150
提交評論