數(shù)據(jù)結構排序綜合設計報告含代碼

1、數(shù)據(jù)結構課程設計報告題目：排序綜合專業(yè)：計算機科學與技術班級：嵌入式1102班組員：11160501 丁 雷11160522 高明堯目錄1需求分析 32概要設計 33詳細設計 54調試結果 85課程設計總結 11參考書目 111需求分析1.1任務與分析任務：利用隨機函數(shù)產(chǎn)生N個隨機整數(shù)（20000以上），對這些數(shù)進行多種方法進行排序。要求：1）至少采用三種方法實現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結果保存在不同的 文件中。2）統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方

2、法。分析：本系統(tǒng)實現(xiàn)了幾種常用的排序方法，包括：插入排序、起泡排序、快速排序（遞歸、非遞歸）、堆排序。1.2功能模塊的劃分1.2.1輸入模塊利用隨機函數(shù)產(chǎn)生N個隨機整數(shù)（20000以上），個數(shù)由用戶自己輸入。1.2.2輸出模塊輸出排序前或排序后的數(shù)據(jù)元素到屏幕顯示，并且輸出按照選擇的算法排序后的數(shù)據(jù)元素 到文件中保存。1.2.3輸出結論比較不同排序時間長短，輸出兩種最快的排序方法。1.2.4排序模塊插入排序思路:設有一組關鍵字K1,K2,.,Kn，排序開始變認為K1是一個有序的序列，讓K2插入 到表長為1的有序序列，使之成為一個表長為2的有序序列，讓K3插入到表長為2的有序 序列，使之成為一個

3、表長為3的有序序列，依次類推，最后讓Kn插入上述表長為n-1的有序序 列，得到一個表長為n的有序序列.冒泡排序如果有n個數(shù)，則要進行n-1趟比較。在第1趟比較中要進行n-1次兩兩比較，在第j趟比 較中要進行n-j次兩兩比較簡單選擇排序通過n-I次關鍵字問的比較，從n-i+1個記錄中選出關鍵字最小的記錄，并和第i個記錄交換之2概要設計32.1程序結構框圖42.2程序流程圖2.3頭文件#include<stdio.h> #include<stdlib.h>#include<cstdlib>#include<time.h>2.5各種操作函數(shù)：(1) 創(chuàng)

4、建一個數(shù)組函數(shù)：(2) 輸出數(shù)組函數(shù)：(3) 簡單選擇排序(4) 插入排序函數(shù)：(5) 起泡排序函數(shù)：(6) 時間函數(shù)：start = clock();end = clock();2.6主函數(shù)Void main()接受命令(選擇要執(zhí)行的操作)；處理命令；輸出結果；3詳細設計#include<stdio.h>#include<stdlib.h>#include<time.h>#define N 30001void main()int i,j,n,k;int n1,t;int aN,bN,c3,d3;clock_t start,finish;int time1,

5、time2,time3;輸入設計printf("*數(shù)據(jù)結構排序綜合 *n")；printf("n輸入要產(chǎn)生的隨機數(shù)個數(shù)：");scanf("%d”,&n);srand(unsigned)time(NULL);for(i=0;i<n;i+)ai=rand();插入排序for(i=0;i<n;i+)bi=ai;printf("n");printf("t 插入排序 n");printf("n");/依次插入數(shù)字到它前面已經(jīng)排好序的數(shù)字中去start=clock();for

6、(i=1;i<n;i+)t=bi;j=i-1;while(bj>t && j>=0)bj+1=bj;j-;if(j!=(i-1) /第i個數(shù)字比前面的都大，不需要重新插入bj+1=t;for(i=n-1;i>=0;i-)printf("%d ",bi);finish=clock();c0=finish-start;printf("n 插入排序耗時 %d 毫秒！ nnn”,c0);起泡排序for(i=0;i<n;i+)bi=ai;printf("n");printf("t 起泡排序 n&qu

7、ot;);printf("n");start=clock();n1=n-1;while(n1>0)j=0;for(i=0;i<n;i+)if(bi>bi+1)(t=bi;bi=bi+1;bi+1=t;j=i；n1=j；printf("%d ”,t);finish=clock();c1=finish-start;printf("n 起泡排序耗時 %d 毫秒！ nnn”,c1);簡單選擇排序for(i=0;i<n;i+)bi=ai;printf("n");printf(-t簡單選擇排序n");printf

8、("n");start=clock();for(i=1;i<n;i+)(k=n-1;for(j=k-1;j>i-1;j-)(if(bj<bk)k=j;if(k!=i-1)(t=bi-1;bi-1=bk;bk=t;for(i=n-1;i>=0;i-)printf("%d ",bi);finish=clock();c2=finish-start;printf("n簡單選擇排序耗時%d毫秒！ nnn”,c2);尋找兩種最快方法for(i=0;i<3;i+)(di=ci; for(i=0;i<3;i+)11(for(

9、j=i+1;j<3;j+)(if(di>dj)(t=di;di=dj;dj=t;/ printf("%d”,c0);printf("排序這組數(shù)據(jù)最快的兩組排序法是：n");if(d0=c0)printf(“插入排序:%d 毫秒 n”,d0);if(d0=c1)printf("起泡排序：d 毫秒 n",d0);if(d0=c2)printf(-簡單選擇排序:%d毫秒n",d0);if(d0!=d1)(if(d1=c0)printf(“插入排序:%d 毫秒 n",d1);if(d1=c1)printf("起

10、泡排序：d 毫秒 n",d1);if(d1=c2)printf(-簡單選擇排序:%d毫秒n",d1);4調試結果數(shù)據(jù)由系統(tǒng)隨機產(chǎn)生，不需要輸入測試數(shù)據(jù)，產(chǎn)生數(shù)據(jù)元素的個數(shù)由用戶輸入。4.1歡迎界面W4#*林林林出巧林寺林據(jù)楚諭入要產(chǎn)生的隨機數(shù)個數(shù):4.2產(chǎn)生隨機函數(shù).HFpH-HF-HFFFF_*樓 J :皚吉勺"：E 窟?宗言-HFFFFFFFf-EHFF-f愉入要產(chǎn)生的隨機數(shù)個數(shù)：5001512B 23232 1375 22840 20677 E504 30485 27960 31641 31174 20549 13034 3331 6968 29345 77

11、47 76634323135S163112662631119983 1S106 17444 28151 9016 24691 29244325533007320338364285716104 1939 22107 3276 19212 19907 9896 27788 3605 24850 19905 29041 14623 14858 78 96 11115 16296 21567 2585616347240371386470S02048013666 110534194 :9137 7402 25601 20970277301015028978413513313101201945521219

12、13728 12011 24937 977S；2194421875213S910447 9227F 17467 25904619611819 19759 17308 17243 17082 4534 88751665961731893243531335425781 4880 6974 3941311102491324521518520 IS155023063 1737624458 8551 32115 91792525911UJ1129S227687142082960947972874213190 21834 3858 7200200162259454962227617548195492019

13、1612212229 8495 11307 38351406731432136352131204019137200682755329491 28775 26B56 32607 8259924519252193124S41279B318851965619190 18363 24494 20607 27071 22998 6460382533652557823916289032593 2143 8469 232113680213222484220820142093S129606 9915 22070 21955400493004298B58 25271 24135 91?327922326|318

14、 4314 1361 6312 29154 15397 27772 15169 18432 11595 14023 S764 10 19326 23450 11278 31305 19198 30751 2423? 15900 4022 21514 6096 28060 27603 2441 25028 5551 4621 10946 29 24409 29008 272S7 25901 9818 2546E 12250 28268 31436 9866 12203 13184 16199 14158 6548 32354 11529 18959305939036323738333291837

15、97S 642713610227141668298S0 16635246402361826294266552791216529 201367940193100232? 9能557774.3排序輸入50個隨機數(shù)個排序方法的結果插入排序32229 31644 31441 31234 30568 29876 29254 29152 27524 27354 26962 269 26 25514 25396 22896 21749 19820 18487 17969 17408 17350 16024 1569815445 15414 15359 14336 12915 12474 11377 1025

16、3 9204 8964 8721 78257755 6948 6882 6805 6743 6054 5907 3231 3219 2944 2370 908 546 232102陸入排序耗時1璀秒！起泡排序32229 31644 31441 31234 30568 29876 29254 291S2 27524 27354 26962 26 26 25514 25396 22896 21749 19820 18487 17969 17408 17350 1SO24 15698 15445 15414 15359 14386 12915 12474 11S77 10253 9204 8964

17、8721 7825 77S5 6948 6382 6805 6743 6054 5907 3231 3219 2944 2370 908 546 23 102起泡排序耗時114#!簡單選擇排序31644 32229 31441 31234 30568 29876 29162 29254 27524 27354 26962 26926 25514 25396 22896 21749 19820 18487 17969 1?408 17350 16024 15445 15698 15414 15359 14386 12915 12474 11377 10253 9204 8964 8721 782

18、5 7755 6948 6382 6805 6743 6054 3231 5907 3219 2944 2370 908 232 546102簡單選擇排序耗時3。皇秒！排序時間結果擔葉林料珅相電*擔0嗷據(jù)結構排序綜合 村4=4=*t葉林林廿擔*l=4=|o=4輸入要產(chǎn)生的隨機數(shù)個數(shù)：30000插入排序插入排序耗時1663毫秒！起泡排序起泡排序耗時5591毫秒!簡單選擇排序簡單選擇排序耗時1969毫秒！排序這組數(shù)據(jù)最也的兩組排序法是:插入排序；1663S秒簡單是拄排序:1969ft秒Press any key to C'Hiitinue6課程設計總結通過這次課程設計的學習讓我學會了許多，加深了對數(shù)據(jù)結構排序算法的認識。在這次課 程設計中，獨立完成了每種排序算法。排序算法選了三個，包括：插入排序、氣泡排序、簡單 選擇排序。同時也實現(xiàn)了隨機數(shù)的生成。雖然在算法完成的過程中從網(wǎng)上參考了一些資料，但 對這次課程設計的成果還是非常滿意的。這次的課程設計還有很多不足之處。有些排序方法沒有些，像堆排序了，快序排序了。還 有就是最后尋找兩種最壞的方法時花了很多時間，想了幾種方法，開始用結構體，但發(fā)現(xiàn)太麻 煩了，所以改用了上述方法。由于時間限制，只在課程設計快結束時完成了產(chǎn)生隨機文