數(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)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("