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

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

3、成為一個(gè)表長為3的有序序列,依次類推,最后讓Kn插入上述表長為n-1的有序序列,得到一個(gè)表長為n的有序序列.冒泡排序如果有n個(gè)數(shù)，則要進(jìn)行n-1趟比較。在第1趟比較中要進(jìn)行n-1次兩兩比較，在第j趟比較中要進(jìn)行n-j次兩兩比較簡單選擇排序 通過n-I次關(guān)鍵字間的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i個(gè)記錄交換之2概要設(shè)計(jì)2.1程序結(jié)構(gòu)框圖綜合排序系統(tǒng) 尋找最快排序簡單選擇排序氣泡排序插入排序開始產(chǎn)生隨機(jī)函數(shù) 2.2程序流程圖開始選擇選取數(shù)產(chǎn)生隨機(jī)函數(shù)插入排序起泡排序?qū)ふ易羁炫判蛲顺龊唵芜x擇排序輸出2.3頭文件 #include<stdio.h>#include&l

4、t;stdlib.h>#include<cstdlib>#include<time.h>2.5各種操作函數(shù)：（1）創(chuàng)建一個(gè)數(shù)組函數(shù)：（2）輸出數(shù)組函數(shù)：( 3 ) 簡單選擇排序（4）插入排序函數(shù)：（5）起泡排序函數(shù)：（6）時(shí)間函數(shù)：start = clock();end = clock();2.6主函數(shù)Void main()接受命令（選擇要執(zhí)行的操作）；處理命令；輸出結(jié)果；3 詳細(xì)設(shè)計(jì)#include<stdio.h>#include<stdlib.h>#include<time.h>#define N 30001void ma

5、in() int i,j,n,k; int n1,t; int aN,bN,c3,d3; clock_t start,finish; int time1,time2,time3; 輸入設(shè)計(jì)printf("*數(shù)據(jù)結(jié)構(gòu)排序綜合*n"); printf("n輸入要產(chǎn)生的隨機(jī)數(shù)個(gè)數(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&quo

6、t;); printf("t插入排序n"); printf("-n"); start=clock(); for(i=1;i<n;i+) /依次插入數(shù)字到它前面已經(jīng)排好序的數(shù)字中去 t=bi; j=i-1; while(bj>t && j>=0) bj+1=bj; j-; if(j!=(i-1) /第i個(gè)數(shù)字比前面的都大，不需要重新插入 bj+1=t; for(i=n-1;i>=0;i-) printf("%d ",bi); finish=clock(); c0=finish-start; pri

7、ntf("n插入排序耗時(shí)%d毫秒！nnn",c0); /起泡排序 for(i=0;i<n;i+)bi=ai; printf("-n"); printf("t起泡排序n"); 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=fi

8、nish-start; printf("n起泡排序耗時(shí)%d毫秒！nnn",c1); /簡單選擇排序 for(i=0;i<n;i+) bi=ai; printf("-n"); printf("t簡單選擇排序n"); printf("-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-) pr

9、intf("%d ",bi); finish=clock(); c2=finish-start; printf("n簡單選擇排序耗時(shí)%d毫秒！nnn",c2); /尋找兩種最快方法 for(i=0;i<3;i+) di=ci; for(i=0;i<3;i+) for(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("

10、插入排序：%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("起泡排序：%d毫秒n",d1); if(d1=c2) printf("簡單選擇排序：%d毫秒n",d1); 4調(diào)試結(jié)果 數(shù)據(jù)由系統(tǒng)隨機(jī)產(chǎn)生，不需要輸入測試數(shù)據(jù)，產(chǎn)生數(shù)據(jù)元素的個(gè)數(shù)由用戶

11、輸入。4.1歡迎界面4.2產(chǎn)生隨機(jī)函數(shù)4.3 排序輸入50個(gè)隨機(jī)數(shù)個(gè)排序方法的結(jié)果排序時(shí)間結(jié)果6課程設(shè)計(jì)總結(jié)通過這次課程設(shè)計(jì)的學(xué)習(xí)讓我學(xué)會(huì)了許多，加深了對(duì)數(shù)據(jù)結(jié)構(gòu)排序算法的認(rèn)識(shí)。在這次課程設(shè)計(jì)中，獨(dú)立完成了每種排序算法。排序算法選了三個(gè)，包括：插入排序、氣泡排序、簡單選擇排序。同時(shí)也實(shí)現(xiàn)了隨機(jī)數(shù)的生成。雖然在算法完成的過程中從網(wǎng)上參考了一些資料，但對(duì)這次課程設(shè)計(jì)的成果還是非常滿意的。 這次的課程設(shè)計(jì)還有很多不足之處。有些排序方法沒有些，像堆排序了，快序排序了。還有就是最后尋找兩種最壞的方法時(shí)花了很多時(shí)間，想了幾種方法，開始用結(jié)構(gòu)體，但發(fā)現(xiàn)太麻煩了，所以改用了上述方法。由于時(shí)間限制，只在課程設(shè)計(jì)快結(jié)束時(shí)完成了產(chǎn)生隨機(jī)文件這部分，我想以后有時(shí)間再來完成它。 同時(shí)在完成這個(gè)課程設(shè)計(jì)后，我也學(xué)到了很多知識(shí)，并能訓(xùn)練的掌握他們了。首先學(xué)會(huì)了隨機(jī)數(shù)的產(chǎn)生。熟練的撐握了C語言的文件讀寫操作。撐握了每種排序算法的基本思想，并從同學(xué)那里學(xué)會(huì)了編寫程序的一般步驟：思考