1、排序綜合理學(xué)院課程設(shè)計說明書課 程 名 稱: 數(shù)據(jù)結(jié)構(gòu)與算法A設(shè)計實踐 課 程 代 碼: 6015059 題 目 二: 排序綜合 年級/專業(yè)/班: 2013/信科/2班 學(xué) 生 姓 名: 馮金慧 學(xué) 號: 3120130902209 開 始 時 間: 2015 年 12 月 28 日完 成 時 間: 2016 年 01 月 10 日課程設(shè)計成績：學(xué)習(xí)態(tài)度及平時成績（30）技術(shù)水平與實際能力（20）創(chuàng)新（5）說明書撰寫質(zhì)量（45）總 分（100）指導(dǎo)教師簽名： 年 月 日排序綜合數(shù)據(jù)結(jié)構(gòu)與算法A設(shè)計實踐任務(wù)書學(xué)院名稱： 理學(xué)院 課程代碼：_6015059_專業(yè)： 信科 年級： 2012 一、 設(shè)

2、計題目 排序綜合（限最多一人完成）二、主要內(nèi)容利用隨機函數(shù)產(chǎn)生N個隨機整數(shù)（20000以上），對這些數(shù)進行多種方法進行排序。三、具體要求及提交的材料1) 至少采用4種方法實現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。2) 統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。如果采用4種或4種以上的方法者，可適當加分。測試數(shù)據(jù)及測試結(jié)果請在上交的資料中寫明；必須上機調(diào)試通過按數(shù)據(jù)結(jié)構(gòu)課程設(shè)計大綱中的要求完成課程設(shè)計報告格式。設(shè)計結(jié)束后，每個學(xué)生必須上交的材料有

3、：1 課程設(shè)計報告打印稿一份 2課程設(shè)計的源代碼電子文檔一份四、主要技術(shù)路線提示 無五、進度安排共計兩周時間，建議進度安排如下：1 選題，應(yīng)該在上機實驗之前完成 2. 需求分析、概要設(shè)計可分配4學(xué)時完成2 詳細設(shè)計可分配4學(xué)時 4. 調(diào)試和分析可分配10學(xué)時。2學(xué)時的機動，可提前安排部分提前結(jié)束任務(wù)的學(xué)生答辯六、 推薦參考資料1. 馮博琴 等編著，軟件技術(shù)基礎(chǔ)（修改版），西安交通大學(xué)出版社，19972. 嚴蔚敏 等著，數(shù)據(jù)結(jié)構(gòu)，清華大學(xué)出版社，20033. 李蕓芳 等著，軟件技術(shù)基礎(chǔ)（第二版），清華大學(xué)出版社，20004. 徐孝凱 等著，數(shù)據(jù)結(jié)構(gòu)（C語言描述），清華大學(xué)出版社，20045. 指

4、導(dǎo)教師 簽名日期 年 月 日6. 系 主 任 審核日期 年 月 日目 錄摘 要12 系統(tǒng)分析32.1功能需求32.1.1總體要求41.4數(shù)據(jù)需求53、詳細設(shè)計與實現(xiàn)53.1設(shè)計思路53.2詳細編碼53.3實驗結(jié)果154系統(tǒng)測試和結(jié)果分析164.1設(shè)計測試數(shù)據(jù)164.2調(diào)試的詳細過程165、算法效率的分析235.1 耗費時間235.2性能分析235.3時間效率24總 結(jié)25參考文獻27附 錄28摘 要排序算法是數(shù)據(jù)結(jié)構(gòu)學(xué)科經(jīng)典的內(nèi)容，其中內(nèi)部排序現(xiàn)有的算法有很多種，其中包含冒泡排序，直接插入排序，簡單選擇排序，希爾排序，快速排序，堆排序等，各有其特點。對排序算法比較的分析可以遵循若干種不同的準則

5、，通常以排序過程所需要的算法步數(shù)作為度量，有時也以排序過程中所作的鍵比較次數(shù)作為度量。特別是當作一次鍵比較需要較長時間，例如，當鍵是較長的字符串時，常以鍵比較次數(shù)作為排序算法計算時間復(fù)雜性的度量。當排序時需要移動記錄，且記錄都很大時，還應(yīng)該考慮記錄的移動次數(shù)。究竟采用哪種度量方法比較合適要根據(jù)具體情況而定。在下面的討論中我們主要考慮用比較的次數(shù)作為復(fù)雜性的度量。排序（sorting）是計算機程序設(shè)計的一種重要操作，他的功能是將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列一個按關(guān)鍵字有序的序列。由于待排序的記錄數(shù)量不同，使得排序過程中涉及的儲存器不同，可將排序方法分為兩大類：一類是內(nèi)部排序，指的是

6、待排序記錄存放在計算機隨機儲存器中進行的排序過程；另一類是外部排序，指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序過程。 內(nèi)部排序又分為：插入排序、快速排序、選擇排序、歸并排序和基數(shù)排序。其中插入排序又分為：直接插入排序、其他插入排序和希爾排序；選擇排序分為：簡單選擇排序、樹形選擇排序和堆排序；基數(shù)排序又分為：多關(guān)鍵字的排序和鏈式基數(shù)排序。 本次課程設(shè)計就是運用VS2010環(huán)境編譯的程序，首先產(chǎn)生2000個隨機數(shù)，然后寫出幾種不同的排序方法分別對產(chǎn)生的隨機數(shù)進行排序并記錄下各種不同法師的排序所耗費的時間，從而找出排序速度比較快的兩種方法，并對不同

7、的排序的性能進行了統(tǒng)計與分析。關(guān)鍵詞：隨機數(shù)，排序，時間效率，時間復(fù)雜度，文件操作43排序綜合1 引 言 1. 1問題的提出首先，如何產(chǎn)生20000個隨機數(shù)；其次，對所產(chǎn)生的隨機數(shù)如何存入文件以方便不同的排序函數(shù)所調(diào)用；最后，如何處理運用各種排序方法對所產(chǎn)生的隨機數(shù)進行排序后的結(jié)果，并將分析其排序效率。1.2 C語言C語言既有高級語言的特點，又具有匯編語言的特點；既是一個成功的系統(tǒng)設(shè)計語言，有時一個使用的程序設(shè)計語言；既能用來編寫不依賴計算機硬件的應(yīng)用程序，又能用來編寫各種系統(tǒng)程序；是一種受歡迎、應(yīng)用廣泛的程序設(shè)計語言。1.3 C語言發(fā)展過程1973年，美國貝爾實驗室的D.M.RITCHIE在

8、B語言的基礎(chǔ)上最終設(shè)計出了一種新的語言，他取了BCPL的第二個字母作為這種語言的名字，這就是C語言。1977年Dennis M.Ritchie 發(fā)表了不依賴于具體機器系統(tǒng)的C語言編譯文本可移植的C語言編譯程序。1978年Brian W.Kernighian和Dennis M.Ritchie出版了名著The C Programming Language，從而使C語言成為目前世界上流行最廣泛的高級程序設(shè)計語言。1.4任務(wù)與分析任務(wù)是先產(chǎn)生出20000個隨機數(shù)，然后再實現(xiàn)分別采用快速排序、氣泡排序、直接插入排序、歸并排序、簡單選擇排序、堆排序?qū)偖a(chǎn)生的隨機數(shù)進行排序，并按照要求，需要記錄出不同方法排

9、序所花費的時間，所以需要編寫一個記錄時間的函數(shù)模塊，在排序開始時調(diào)用該函數(shù)記錄所耗費的時間。分析：首先，隨機數(shù)產(chǎn)生的較多時不太好方便操作，于是在寫隨機數(shù)模塊時可以先產(chǎn)生較少的隨機數(shù)進行調(diào)試和檢查。其次是這學(xué)期數(shù)據(jù)結(jié)構(gòu)這門課中學(xué)的排序方法比較多，結(jié)合這學(xué)期學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)這門課程，我選擇了快速排序、氣泡排序、直接插入排序、歸并排序、簡單選擇排序、堆排序這幾種排序方式。接著，對隨機數(shù)采用不同的方式進行排序，想到了將不同的排序方法依次分塊寫成函數(shù)，需要采用哪種方式排序時僅需要調(diào)用相應(yīng)的函數(shù)就行了。最后需要記錄下不同排序所耗費的時間，就需要再寫一個記錄耗時的函數(shù)了，這樣把一個大問題分成若干個小問題，解決

10、起來就簡單方便的多了。初步想法是利用隨機數(shù)函數(shù)產(chǎn)生20000個隨機數(shù)，將產(chǎn)生的20000個數(shù)放到一個一維數(shù)組中，并顯示20000個數(shù)；設(shè)置菜單選項，以選擇6種不同的排序方法中的一種進行排序；采用每種排序方法時統(tǒng)計該算法耗時，在屏幕和文件中輸出排序結(jié)果，之后回到菜單選擇界面，然而我又想到不同的排序方式所做出的排序結(jié)果不能相互干擾，于是最終我選擇將隨機數(shù)存入文件中，以免排序時混淆。在輸出排序結(jié)果時我想到不同的排序結(jié)果存入不同的文件中，這樣結(jié)果就簡單明了了。2 系統(tǒng)分析2.1功能需求 此課題是研究排序綜合問題，并用不同的方式對所產(chǎn)生的的2000個隨機數(shù)進行排序的問題。確定其主要的幾個模塊的功能：1、

11、產(chǎn)生隨機數(shù)2、對所產(chǎn)生的隨機數(shù)進行文件存儲3、用戶選擇模塊4、不同排序方式調(diào)用函數(shù)模塊5、文件存儲模塊6、計時模塊7、菜單模塊對課題研究的進一步分析，我明確了我需要做的具體步驟：首先需要成功產(chǎn)生隨機數(shù)，才能繼續(xù)下一步的運用各種不同的排序方式對隨機數(shù)進行排序。然后將幾種不同的排序方式各自分成一個子快，編寫出相應(yīng)的6個函數(shù)（快速排序、冒泡排序、直接插入排序、歸并排序、簡單選擇排序、堆排序），還有一個記錄時間的函數(shù)模塊，然后在主程序里面提示各個選項對相應(yīng)的功能，用戶輸入相應(yīng)的操作數(shù)，分別調(diào)用不同的函數(shù)，打印出相應(yīng)的排序結(jié)果和所耗費的時間。最后，根據(jù)調(diào)試的結(jié)果對各個不同的排序方式加以分析。因此，實際需

12、要設(shè)計的服務(wù)就是生成隨機數(shù)，以及不同排序方法的函數(shù)編寫，以及記錄時間的函數(shù)的編寫，為了直觀和方便，畫出流程圖如下圖1：排序綜合 生成隨機數(shù)直接插入排序冒泡排序快速排序歸并排序簡單選擇排序堆排序耗時函數(shù)退出圖1 程序總的流程圖流程圖很直觀的描述了整個程序服務(wù)過程。 2.1.1總體要求首先主函數(shù)中必須成功生成隨機數(shù)，在這里我采取了隨機種子來達到產(chǎn)生隨機數(shù)的要求、首先，用戶想要對隨機數(shù)采用不同的方式進行排序，并得到其相應(yīng)的耗時，就必須按照先序成功創(chuàng)建需要排序的對象即隨機數(shù)。其次，用戶要對隨機數(shù)進行排序，那就需要知道他想采用的排序方法是什么。這需要用戶手動輸入選擇序號。通過用戶輸入的信息，計算機就可以

13、進行相關(guān)的操作，根據(jù)用戶輸入的信息選擇相應(yīng)的排序方式對所產(chǎn)生的隨機數(shù)進行排序，輸出相應(yīng)的排序順序和排序耗時供用戶瀏覽了；我們就要用相應(yīng)的程序去實現(xiàn)這個過程,這才是我們最后的目的。1.4 數(shù)據(jù)需求隨機產(chǎn)生20000個數(shù)3、詳細設(shè)計與實現(xiàn) 3.1設(shè)計思路 要完成對隨機數(shù)的排序，有很多種方法可以實現(xiàn)。但是結(jié)合自己的知識掌握情況，我選擇了比較適合自己的算法，其他的算法還有很多，只是都不是很熟悉，我的思想大多都來源于書上，這學(xué)期數(shù)據(jù)結(jié)構(gòu)所學(xué)的排序方法比較多，我選擇的有快速排序、冒泡排序、直接插入排序、歸并排序、簡單選擇排序、堆排序。有了上面的分析，下一步自然就是完成分步它的程序了，不能用程序描述出來那在

14、好也沒有用的。3.2詳細編碼/包含頭文件#include "stdafx.h"#include<iostream>#include<fstream>#include<time.h>#include<stdlib.h>#include<iomanip>#include<string>#include <stdio.h> #include <malloc.h> #include <queue> #include <stack> using namespace

15、std; /定義的結(jié)構(gòu)體#define M 2000 /產(chǎn)生隨機數(shù)個數(shù)的定義const int MAXSIZE=20000;typedef structint key;RedType;typedef structRedType rMAXSIZE+1;int length;Sqlist;typedef Sqlist HeapType;clock_t start,finish;using namespace std; /自定義函數(shù)原型說明int SelectMin(int a,int i,int m)/簡單選擇排序void Merge (RedType SR,RedType TR,int i,in

16、t m,int n) /2-路歸并排序 int Partition(Sqlist &L, int low, int high)/快速排序void HeapAdjust(HeapType &H, int s, int m) /堆排序double duration(clock_t x,clock_t y)/算法耗時統(tǒng)計/隨機數(shù)的產(chǎn)生int i, j, aM;/定義i,j；待排序數(shù)組aM;char ch;/字符ch,用于記錄選項;srand(unsigned)time(NULL);/設(shè)置隨機種子;for (i = 1; i < M + 1; i+)ai = rand() % 5

17、000;/隨機生成待排序數(shù)組a;cout << "ttt/產(chǎn)生20000個隨機數(shù)/" << endl;system("pause");for (i = 1; i < M + 1; i+)/每個元素占6個字符，每行十個元素的格式輸出隨機生成的待排序數(shù)組a;cout << setw(6) << ai << " "if (i % 10 = 0) cout << endl;system("pause");經(jīng)過用戶的按鍵操作，很容易就可以創(chuàng)建出20

18、00個隨機數(shù)，并彈出菜單項，用戶輸入對應(yīng)的操作序號，計算機很快確定排序的方式并輸出排出的順序和所耗費的時間字樣給用戶，用戶就可以繼續(xù)輸入選項進行下一步操作；這樣，需要實現(xiàn)的第一個功能就很輕松的完成了。/簡單選擇排序簡單選擇排序：通過n-i次關(guān)鍵字間的比較，從n-i+1個記錄中選出關(guān)鍵字最小的記錄，并和第i個記錄交換之，直至整個序列非遞減。int SelectMin(int a,int i,int m)/簡單選擇排序 int p,n,t; t=ai; for(p=i+1;p<m;p+)if(ap<t)t=ap; for(n=i,p=i;p<m;n+,p+)if(an=t) br

19、eak;return n; /歸并排序假設(shè)初始序列含有n個記錄，則可看成是n個有序子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2個長度為2或1的有序子序列；在兩兩歸并,.,如此重復(fù)，直至得到一個長度為n的有序序列為止。void Merge(RedType SR, RedType TR, int i, int m, int n) /2-路歸并排序 /將有序的SRi.m和SRm+1.n歸并為有序的TRi.nint j, k;for (j = m + 1, k = i; i <= m&&j <= n; +k)if (SRi.key < SRj.key) TR

20、k = SRi+; /將SR中的記錄由小到大并入TRelse TRk = SRj+;if (i <= m)while (k <= n&&i <= m) TRk+ = SRi+; /將剩余的SRi.m復(fù)制到TRif (j <= n)while (k <= n&&j <= n) TRk+ = SRj+; /將剩余的SRj.n復(fù)制到TRvoid MSort(RedType SR, RedType TR1, int s, int t)int m;RedType * TR2;TR2 = new RedTypeM + 1;if (s =

21、t) TR1t = SRs;else m = (s + t) / 2; / 將SRs.t平分為SRs.m和SRm+1.tMSort(SR, TR2, s, m); / 遞歸地將SRs.m歸并為有序的TR2s.mMSort(SR, TR2, m + 1, t); / 將SRm+1.t歸并為有序的TR2m+1.tMerge(TR2, TR1, s, m, t); / 將TR2s.m和TR2m+1.t歸并到TR1s.tdeleteTR2;/冒泡排序 冒泡排序：首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進行比較，若為逆序，則將兩個記錄交換之，然后比較第二個記錄和第三個記錄的關(guān)鍵字；以此類推，直至第n

22、-1個記錄和第n個記錄的關(guān)鍵字進行過比較為止，結(jié)果使得關(guān)鍵字最大的記錄被安置到最后一個記錄的位置上；然后繼續(xù)進行直至整個序列有序。 /冒泡排序;int t;/定義整形數(shù)據(jù)tofstream output("冒泡排序.txt");/建立冒泡排序結(jié)果保存文件;start = clock();/開始起泡排序算法執(zhí)行時間計時for (j = 1; j < M + 1; j+)/執(zhí)行起泡排序算法for (int i = 1; i<M + 1 - j; i+)if (ai>ai + 1) t = ai; ai = ai + 1; ai + 1 = t;finish =

23、 clock();/終止冒泡排序算法執(zhí)行時間計時printf( "顯示冒泡排序結(jié)果:n"); for (i = 1; i < M + 1; i+)/每個元素占6個字符,以空格隔開，每100個元素換行保存排序后數(shù)組;output << setw(6) << ai << " "if (i % 100 = 0) printf("n");for (i = 1; i < M + 1; i+)/每個元素占6個字符,以空格隔開，每10個元素換行輸出排序后數(shù)組;cout << setw(6)

24、 << ai << " "if (i % 10 = 0) printf("n");printf(" 冒泡排序完成,結(jié)果已保存!n");cout << "冒泡排序消耗時間為: " << duration(start, finish) << "秒" << endl;/輸出起泡排序算法耗時(s);system("pause");goto loop;/返回程序主菜單; break;/ 直接插入排序直接插入排序：先

25、將序列中的第1個記錄看成是一個有序的子序列，然后從第2個記錄起逐個進行插入，直至整個序列變成關(guān)鍵字非遞減有序序列為止，整個排序過程進行n-1趟插入。int i,j; /直接插入排序;int i, j;Sqlist L;/聲明結(jié)構(gòu)體;L.length = 0;/初始化結(jié)構(gòu)體長度為0;ofstream output("直接插入排序.txt");/建立直接插入排序結(jié)果保存文件;for (i = 1; i < M + 1; i+)/初始化直接插入排序結(jié)構(gòu)體中的數(shù)據(jù);L.ri.key = ai;L.length+;start = clock();/開始直接插入排序算法執(zhí)行時間計

26、時;for (i = 2; i <= L.length; +i)/執(zhí)行插入排序算法;if (L.ri.key < L.ri - 1.key)L.r0 = L.ri;L.ri = L.ri - 1;for (j = i - 2; L.r0.key < L.rj.key; -j)L.rj + 1 = L.rj;L.rj + 1 = L.r0;finish = clock();/結(jié)束直接插入排序算法執(zhí)行時間計時;cout << "顯示直接插入排序的結(jié)果:" << endl;for (i = 1; i < M + 1; i+)/每個元

27、素占6個字符,以空格隔開，每100個元素換行保存排序后數(shù)組;output << setw(6) << L.ri.key << " "if (i % 100 = 0) printf("n");for (i = 1; i < M + 1; i+)/每個元素占6個字符,以空格隔開，每10個元素換行輸出排序后數(shù)組;cout << setw(6) << L.ri.key << " "if (i % 10 = 0) printf("n");print

28、f( " 直接插入排序完成,結(jié)果已保存!n");cout << "直接插入排序消耗時間為 " << duration(start, finish) << "秒" << endl;/輸出直接排序算法耗時(s);system("pause");goto loop;/返回程序主菜單; break; /快速排序 通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠郑渲幸徊糠钟涗浀年P(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。int Parti

29、tion(Sqlist &L, int low, int high) /快速排序int pivotkey;L.r0 = L.rlow; /用子表的第一個記錄作樞軸pivotkey = L.rlow.key; /樞軸記錄關(guān)鍵字while (low < high)while (low < high && L.rhigh.key >= pivotkey) -high;L.rlow = L.rhigh; /將比樞軸記錄小的記錄移到低端while (low < high && L.rlow.key <= pivotkey) +low;

30、L.rhigh = L.rlow; /將比樞軸大的記錄移到高端L.rlow = L.r0; /樞軸記錄到位return low; /返回樞軸位置void Qsort(Sqlist &L, int low, int high)int pivotloc;if (low < high) /長度大于1pivotloc = Partition(L, low, high); /將L.rlow.high一分為二Qsort(L, low, pivotloc - 1); / 對低子表遞歸排序，pivotloc是樞軸位置Qsort(L, pivotloc + 1, high); / 對高子表遞歸排序

31、 / 堆排序 首先由無序序列建成一個堆，輸出堆頂元素后，以堆中最后一個元素替代之，此時根節(jié)點的左右子樹均為堆，則僅需自上至下進行調(diào)整即可，直至所有元素按非遞減順序輸出。void HeapAdjust(HeapType &H, int s, int m) /堆排序 int j; RedType rc; rc = H.rs; for (j=2*s; j<=m; j*=2) if (j<m && H.rj.key<H.rj+1.key) +j; if (rc.key >= H.rj.key) break; H.rs = H.rj; s = j; H.r

32、s = rc; void HeapSort(HeapType &H) int i; RedType temp; for (i=H.length/2; i>0; -i) HeapAdjust ( H, i, H.length ); for (i=H.length; i>1; -i) temp=H.ri; H.ri=H.r1; H.r1=temp; HeapAdjust(H, 1, i-1); /計算時間的函數(shù)double duration(clock_t x, clock_t y) /算法耗時統(tǒng)計double dur;dur = (double)(y - x) / CLOCK

33、S_PER_SEC;return dur;到此為止，所有功能已經(jīng)分別實現(xiàn)了，通過執(zhí)行各個函數(shù)，就可以完成相應(yīng)的功能。現(xiàn)在唯一需要做的就是找個函數(shù)來將他們“集中起來”，用來組合在一起，才能讓它們互相配合，一起工作。這個任務(wù)當然是由main()來完成了：void main()printf("n");printf("t功 能： 排 序 綜 合nn");printf("t編 譯 環(huán) 境：V S 2 0 1 0nn");printf("t發(fā) 布 日 期：2 0 1 5 - 1 1 - 2 5nn");printf("

34、;n*程序開始！*n");int i, j, aM;/定義i,j；待排序數(shù)組aM;char ch;/字符ch,用于記錄選項;srand(unsigned)time(NULL);/設(shè)置隨機種子;for (i = 1; i < M + 1; i+)ai = rand() % 5000;/隨機生成待排序數(shù)組a;printf( "ttt/產(chǎn)生200個隨機數(shù)/n");system("pause");for (i = 1; i < M + 1; i+)/每個元素占6個字符，每行十個元素的格式輸出隨機生成的待排序數(shù)組a;cout <<

35、 setw(6) << ai << " "if (i % 10 = 0) printf("n");system("pause");loop:/排序算法主菜單; printf("ttt菜 單n");printf("t*n");printf( "tt請選擇你要使用的排序方法:n");printf("tt1.快速排序;ntt2.起泡排序;n tt3.直接插入排序;n tt4.歸并排序;n");printf( "tt5.簡單選擇排

36、序;ntt6.堆排序;ntt7.退出.n");printf("t*n");loop1:/排序過程;fflush(stdin);/清除文件緩沖區(qū)，文件以寫方式打開時將緩沖區(qū)內(nèi)容寫入文件;為了確保不影響后面的數(shù)據(jù)讀取;ch = getchar();/獲取選項,選擇相應(yīng)的排序算法;在main（）里，對各個相應(yīng)的操作指定了想象的選擇序號，使用戶簡單明了，形象直觀，首先必須成功生成2000個隨機數(shù)，現(xiàn)實中一樣。因為你需要排序的對象不明確，又如何能準確的確定相應(yīng)的查找方式呢，因為生成就是確定需要排序的對象，所以先確定了對象，然后通過一個友好的容易操作的界面面向用戶，這樣即使用

37、戶對計算機一竅不通，也能夠輕松的使用這個系統(tǒng)進行隨機數(shù)的各種排序了。為了使用戶能夠在進行了一項操作之后還能進行另外的操作，例如：快速排序之后還可以繼續(xù)選擇堆排序等等。所以讓程序一直執(zhí)行，直到用戶輸入退出的信息后才中止程序，這樣做程序顯得更人性化些！到此，整個程序也就完成了。3.3實驗結(jié)果 文件存儲排序部分結(jié)果如下圖：圖04系統(tǒng)測試和結(jié)果分析4.1設(shè)計測試數(shù)據(jù) 隨機生成2000個數(shù)(為了直觀一些我本次調(diào)試只是生成了200個隨機數(shù))4.2調(diào)試的詳細過程對于所有執(zhí)行過程，通過圖片最好說明問題了，程序開始如下圖所示：0. 運行程序初始界面： 圖 11.生成隨機數(shù)，按任意鍵即可，如下圖2：圖 22.點擊

38、任意鍵繼續(xù) ，彈出選擇菜單，并提示用戶選擇需要的服務(wù)如圖3：圖 34.選擇“1”服務(wù)時，如圖4/1-2所示：圖 4.1 圖4.25.這時用戶可繼續(xù)選擇進行操作，如果選“2”服務(wù)時，如圖5/1-2所示：圖5.1 圖5.26.輸入了“3”服務(wù)時，如圖6/1-2所示：圖6.1 圖 6.26.輸入了“4”服務(wù)時，如圖7/1-2所示：圖7.1 圖7.27.輸入了“5”服務(wù)時，如圖8/1-2所示：圖8.1圖8.2 8.輸入了“6”服務(wù)時，如圖9/1-2所示：圖9.1 圖 9.29.輸入了“7”服務(wù)時，如圖10所示：圖 10整個對隨機數(shù)的產(chǎn)生，快速排序、冒泡排序、直接插入排序、歸并排序、簡單選擇排序、堆排序

39、的操作過程就是這樣，很簡單。5、算法效率的分析 5.1 耗費時間 對20000個隨機數(shù)各種排序平均運行時間統(tǒng)計如下表：快速排序冒泡排序直接插入排序歸并排序簡單選擇堆排序0.001s0.009s0s0.059s0.021s0.001s5.2性能分析 (1)若n較小(如n50)，可采用直接插入或直接選擇排序。 當記錄規(guī)模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數(shù)少于直接插人，應(yīng)選直接選擇排序為宜。 (2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機的快速排序為宜； (3)若n較大，則應(yīng)采用時間復(fù)雜度為的排序方法：快速排

40、序、堆排序或歸并排序。 （4）堆排序適合于數(shù)據(jù)量非常大的場合（百萬數(shù)據(jù)）。堆排序不需要大量的遞歸或者多維的暫存數(shù)組。這對于數(shù)據(jù)量非常巨大的序列是合適的。比如超過數(shù)百萬條記錄，因為快速排序，歸并排序都使用遞歸來設(shè)計算法，在數(shù)據(jù)量非常大的時候，可能會發(fā)生堆棧溢出錯誤。堆排序會將所有的數(shù)據(jù)建成一個堆，最大的數(shù)據(jù)在堆頂，然后將堆頂數(shù)據(jù)和序列的最后一個數(shù)據(jù)交換。接下來再次重建堆，交換數(shù)據(jù)，依次下去，就可以排序所有的數(shù)據(jù)。5.3時間效率1. 插入排序的算法的時間復(fù)雜度為： 2. 希爾排序的算法的時間復(fù)雜度為n的1.2次冪 3. 冒泡排序的算法的時

41、間復(fù)雜度為：O（n2）。當數(shù)據(jù)為正序，將不會有交換，復(fù)雜度為O(n)。 4. 快速排序的算法時間復(fù)雜度為：O(nlogn),是所有內(nèi)部排序方法中最好的，大多數(shù)情況下總是最好的。 5. 簡單排序的算法的時間復(fù)雜度為O(n2)： 6. 堆排序的算法的時間復(fù)雜度為：O(nlogn) 總 結(jié)在一個學(xué)期后的基礎(chǔ)理論知識的學(xué)習(xí)后進入實踐的操作雖然仍就有些困難但也是另一種進步的好途徑。這次的課程設(shè)計主要是對基礎(chǔ)知識的靈活使用，這就讓我進一步提高了對數(shù)據(jù)結(jié)構(gòu)知識的鞏固。這次設(shè)計的完成，困難是少不了的，還有許多其他的難題讓我都曾不知所措，但通

42、過努力最終解決它們讓我體會到成就感，更重要的是我的能力在無形中得到了提升和優(yōu)化。這次課程設(shè)計的心得體會通過實習(xí)我的收獲如下:1、鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運用本課程所學(xué)知識的能力。2、培養(yǎng)了我選用參考書，查閱手冊及文獻資料的能力。培養(yǎng)獨立思考，深入研究，分析問題、解決問題的能力。3、通過實際編譯系統(tǒng)的分析設(shè)計、編程調(diào)試，掌握應(yīng)用軟件的分析方法和工程設(shè)計方法。4、通過課程設(shè)計，培養(yǎng)了我嚴肅認真的工作作風(fēng)，逐步建立正確的生產(chǎn)觀念、經(jīng)濟觀念和全局觀念。我通過課程設(shè)計建立系統(tǒng)設(shè)計的整體思想，鍛煉編寫程序、調(diào)試程序的能力，學(xué)習(xí)文檔編寫規(guī)范，培養(yǎng)獨立學(xué)習(xí)、吸取他人經(jīng)驗。同時，充分彌補了課堂教學(xué)

43、及普通實驗中知識深度與廣度有限的缺陷，更好地幫助從全局角度把握課程體系，并且可以將理論與實際聯(lián)系。在課程設(shè)計的過程中不僅僅是書本上的知識，這便促使我去查閱更多的課外資料來充實自己的內(nèi)容，同時學(xué)會在面對困難時要耐心得分析它細心得解決它以及通過合作更完美得深入了解剖析它以便得到提高。細心、耐心、團結(jié)、求知，是我這次課程設(shè)計最大的收獲。致 謝本次設(shè)計是在陳曉亮老師的悉心指導(dǎo)和熱心幫助下完成的。他給我的程序設(shè)計和論文提出了很多寶貴的意見，并給我作了仔細的修改。在他的鼓勵與耐心的指導(dǎo)下，我的設(shè)計和論文才能快速、保質(zhì)量完成。在和陳老師的接觸中，他給我以毫不保留的指導(dǎo)，促進了我對專業(yè)知識的鞏固和提高，讓我受

44、益匪淺。然后還要感謝大學(xué)的所有的老師，為我打下博大精深的專業(yè)知識的基礎(chǔ)，同時還要感謝所有的同學(xué)們，正是因為有了大家的相互學(xué)習(xí)相互交流，才讓我有了做題靈感，正是因為有了你們的支持和鼓勵，此次設(shè)計才會順利完成。在此，衷心的謝謝您們 總之，數(shù)據(jù)結(jié)構(gòu)課程設(shè)計讓我受益良多，我會好好珍惜像這種難得的機會，努力學(xué)習(xí)知識。也感謝幫助了我的老師、同學(xué)。參考文獻1 嚴蔚敏，吳偉民，數(shù)據(jù)結(jié)構(gòu)（C語言版）.北京：清華大學(xué)出版社，1997 2 譚浩強，C程序設(shè)計（第三版）.北京：清華大學(xué)出版社，20053 Jeri R.Hanly，Elliot B. Koffman，問題求解與程序設(shè)計C語言版（第四版）.北京：清華大學(xué)

45、出版社，2007-14 何欽銘，顏暉，C語言設(shè)計教程.北京:高等教育出版社，2008年5 吳文虎，程序設(shè)計基礎(chǔ).北京:清華大學(xué)出版社，2003附 錄/ 數(shù)據(jù)結(jié)構(gòu)3一元多項式的加減乘.cpp : 定義控制臺應(yīng)用程序的入口點。/=二叉樹的遍歷=/=執(zhí)行軟件VS2010=/=發(fā)布日期：2015-11-28=#include "stdafx.h"#include<iostream>#include<fstream>#include<time.h>#include<stdlib.h>#include<iomanip>#inc

46、lude<string>#include <stdio.h> #include <malloc.h> #include <queue> #include <stack> /=頭文件= #define M 200 /產(chǎn)生隨機數(shù)個數(shù)的定義const int MAXSIZE = 20000;typedef structint key;RedType;typedef structRedType rMAXSIZE + 1;int length;Sqlist;typedef Sqlist HeapType;clock_t start, finis

47、h;using namespace std;/=基本排序算法=/void Merge(RedType SR, RedType TR, int i, int m, int n);void MSort(RedType SR, RedType TR1, int s, int t);int SelectMin(int a, int i, int m);int Partition(Sqlist &L, int low, int high);void Qsort(Sqlist &L, int low, int high);void HeapAdjust(HeapType &H, i

48、nt s, int m);void HeapSort(HeapType &H);double duration(clock_t x, clock_t y);/=/void control(int a);void menu();/=具體排序函數(shù)=/快速選擇排序void quick_select_sort(int a);/冒泡排序void bubble_sort(int a);/插入排序void insert_sort(int a);/歸并排序void merge_sort(int a);/簡單選擇排序void simple_select_sort(int a);/堆排序void heap

49、_sort(int a);/=/void main()printf("n");printf("t功 能： 排 序 綜 合nn");printf("t編 譯 環(huán) 境：V S 2 0 1 0nn");printf("t發(fā) 布 日 期：2 0 1 5 - 1 1 - 2 5nn");printf("n*程序開始！*n");int i, arrM;/定義i,j；待排序數(shù)組arrM;srand(unsigned)time(NULL);/設(shè)置隨機種子;for (i = 1; i < M + 1; i+

50、)arri = rand() % 5000;/隨機生成待排序數(shù)組a;printf("ttt/產(chǎn)生200個隨機數(shù)/n");system("pause");for (i = 1; i < M + 1; i+)/每個元素占6個字符，每行十個元素的格式輸出隨機生成的待排序數(shù)組a;cout << setw(6) << arri << " "if (i % 10 = 0)printf("n");system("pause");fflush(stdin);/清除文件緩

51、沖區(qū)，文件以寫方式打開時將緩沖區(qū)內(nèi)容寫入文件;為了確保不影響后面的數(shù)據(jù)讀取;control(arr);void control(int a)menu();char ch;/字符ch,用于記錄選項;while (1)scanf_s("%c", &ch);/獲取選項,選擇相應(yīng)的排序算法;switch (ch)case '1':/快速選擇排序quick_select_sort(a);system("pause");getchar();menu();break;case '2':/冒泡排序;bubble_sort(a);system("pause");getchar();menu();break;case '3':/直接插入排序insert_sort(a);system("pause");getchar();menu();break;case '4':/歸并排序算法;merge_sort(a);system("pause");getchar();menu();break;case '5':/簡單選擇排序;