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

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)windows運(yùn)行環(huán)境vc6.0三、 算法設(shè)計(jì)的思想大架構(gòu)采用模塊化編程的思想，將每個(gè)不同的功能分別寫(xiě)成不同的子程序，分別進(jìn)行封裝構(gòu)成各個(gè)小的模塊，最后將各個(gè)模塊組合起來(lái)。在每個(gè)子程序的編寫(xiě)過(guò)程中特事特辦面對(duì)不同的預(yù)想功能采取不同的數(shù)據(jù)結(jié)構(gòu)不同的算法實(shí)現(xiàn)。總體算法思想為按功能分塊，依照預(yù)想功能實(shí)現(xiàn)順序拼裝。具體思想請(qǐng)見(jiàn)流程圖。四、 流程圖開(kāi)始功能流程圖請(qǐng)用戶輸入將要生成隨機(jī)數(shù)的上下限，按照上下限生成30000個(gè)隨機(jī)數(shù)并輸出隨機(jī)生成

2、隨機(jī)數(shù)并輸出請(qǐng)用戶選擇想要使用的排序方法計(jì)算其使用的排序時(shí)間并輸出詢問(wèn)用戶是否繼續(xù)運(yùn)行程序否是輸出結(jié)束語(yǔ)句結(jié)束程序編寫(xiě)流程圖開(kāi)始定義全局變量a30000,aaaa3000,結(jié)構(gòu)體數(shù)組aa30000用來(lái)存放隨機(jī)數(shù)，choice，choice1編寫(xiě)各個(gè)子算法子函數(shù)，和時(shí)間選擇函數(shù)，既菜單選擇函數(shù)，部分需要聲明的函數(shù)在頭文件下聲明。各模塊依據(jù)功能流程圖組裝結(jié)束算法流程圖開(kāi)始局部變量l，h收集上下限，sjs（）將用戶選擇數(shù)值賦值于choice，將choice作為參數(shù)調(diào)用time（），用if語(yǔ)句判斷選擇將要調(diào)用的算法子函數(shù)main1（）menu（）choice1=1Choice1=2結(jié)束五、 算法設(shè)計(jì)分

3、析 程序總體采用模塊化設(shè)計(jì)，程序間通過(guò)傳參和調(diào)用進(jìn)行有機(jī)組合。這樣的總體布局將將各個(gè)功能隔離開(kāi)來(lái)，每個(gè)模塊負(fù)責(zé)每個(gè)模塊的功能，使得程序的布局簡(jiǎn)單明了。且子程序只有在被調(diào)用時(shí)才會(huì)運(yùn)行大大節(jié)約系統(tǒng)資源減少了運(yùn)算時(shí)間。同時(shí)由于功能的隔離使得程序的擴(kuò)展性大大提高，無(wú)論程序?qū)⒁魏胃膭?dòng)時(shí)，都會(huì)方便很多。六、 源代碼#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āi)始元素*/ k = s; /*開(kāi)始元素下標(biāo)*/ j = 2*k + 1; /*右子樹(shù)元素下標(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)整后，開(kāi)始元素也隨之調(diào)整*/ j = 2*k + 1; else /*沒(méi)有需要調(diào)整了，已經(jīng)是個(gè)堆了，退出循環(huán)。*/ break; *(x+k) = t; /*開(kāi)始元素放到它正確位置*/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í)間計(jì)算函數(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é)束您所用排序時(shí)間為：%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("謝謝使用，再見(jiàn)！");/*生成隨機(jī)數(shù)函數(shù)*/void sjs()int i=0,j,b,h,l;prin

13、tf("請(qǐng)輸入你所期望的將要生成隨機(jī)數(shù)的取值范圍：n");printf("最小值（不能為負(fù)數(shù)）：");scanf("%d",&l);printf("最大值（無(wú)上限）：");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請(qǐng)選擇你所希望使用的排序方法：nn1。直接插入排序n2。冒泡排序n3。選擇排序n4。快速排序n5。堆排序n6。歸并排序n");scanf("%d",&choice);timer(choice);printf("nn排序完畢，請(qǐng)選擇下一步您要完成的工作：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í)間計(jì)算函數(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é)束您所用排序時(shí)間為：%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("謝謝使用，再見(jiàn)！"); void main1()printf("nn請(qǐng)選擇你所希望使用的排序方法：nn1。直接插入排序n2。冒泡排序n3。選擇排序n4。快速排序n5。堆排序n6。歸并排序n");scanf("%d",&choice);time(choice);printf("