數(shù)據(jù)結(jié)構(gòu)課程設(shè)計92184

1、課 程 設(shè) 計 說 明 書課程名稱： 數(shù)據(jù)結(jié)構(gòu)和算法 設(shè)計題目： 多種排序 院 系： 計算機(jī)科學(xué)與信息工程學(xué)院 學(xué)生姓名： 學(xué) 號： 專業(yè)班級： 計科嵌入式（12-1） 指導(dǎo)教師： 年 月 日課 程 設(shè) 計 任 務(wù) 書設(shè)計題目表達(dá)式計算程序設(shè)計學(xué)生姓名所在院系計科專業(yè)、年級、班12計科（嵌入式）設(shè)計要求：1) 采用如下七種方法實現(xiàn)上述問題求解：插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序。2) 統(tǒng)計每一種排序方法的性能（以上機(jī)運行程序所花費的時間為準(zhǔn)進(jìn)行對比），找出其中兩種較快的方法。并將數(shù)據(jù)序列和不同的查找算法的性能結(jié)果記錄入txt文件。學(xué)生應(yīng)完成的工作：1. 利用隨機(jī)

2、函數(shù)產(chǎn)生N個隨機(jī)整數(shù)（10000以上）。2. 對這些數(shù)字進(jìn)行排序。3. 采用插入、希爾、起泡、快速、選擇、歸并、堆排序方法解決問題。4. 對不同的排序算法進(jìn)行性能比較并記錄。參考文獻(xiàn)閱讀： 1. 數(shù)據(jù)結(jié)構(gòu)(C語言版) 嚴(yán)蔚敏 清華大學(xué)出版社 2. C語言程序設(shè)計 丁峻嶺 中國鐵道出版社 3. C程序設(shè)計 譚浩強(qiáng) 清華大學(xué)出版社工作計劃：任務(wù)下達(dá)日期： 年 月 日 任務(wù)完成日期： 年 月 日指導(dǎo)教師（簽名）： 學(xué)生（簽名）： 多種排序摘 要： 排序是算法中最基礎(chǔ)的問題之一，經(jīng)典的排序算法是前人不斷總結(jié)得到的，基于比較的方法是比較直觀的方式，主要存在插入法排序、堆排序、希爾排序、歸并排序、快速排序

3、，每一種排序算法都有自己的優(yōu)缺點，比如插入法排序適用于那些長度短的排序，要是長的話，有些愛莫能助啦，堆排序主要是依據(jù)了二叉堆的特性，但是創(chuàng)建堆的過程也是一個復(fù)雜的問題，希爾排序的過程是一個不斷精確的過程，但是目前也只是一個經(jīng)驗方式。歸并排序是一個遞歸的問題，采用分治的思想實現(xiàn)，但是這種算法需要額外的存儲空間，快速排序雖然是實踐中比較常用的算法，但是對于有序的數(shù)組采用快速排序就是災(zāi)難。比較型算法的時間復(fù)雜度最優(yōu)也只能到達(dá)O(NlogN)。關(guān)鍵詞：歸并排序快排排序選擇排序冒泡排序插入排序堆排序希爾排序內(nèi)部排序目 錄1. 設(shè)計背景41.1問題描述41.2 問題分析42.設(shè)計方案42.1 算法設(shè)計4

4、2.2 功能模塊分析63.主要算法流程圖154. 結(jié)果與結(jié)論164.1正確結(jié)果164.2錯誤信息185. 算法復(fù)雜度以及穩(wěn)定性分析186. 收獲與致謝197. 參考文獻(xiàn)198. 附件201. 設(shè)計背景1.1問題描述 利用隨機(jī)函數(shù)產(chǎn)生N個隨機(jī)整數(shù)（10000以上），對這些數(shù)進(jìn)行多種方法進(jìn)行排序。包括：插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序。1.2 問題分析經(jīng)典的排序算法是前人不斷總結(jié)得到的，基于比較的方法是比較直觀的方式，主要存在插入法排序、堆排序、希爾排序、歸并排序、快速排序，每一種排序算法都有自己的優(yōu)缺點。2. 設(shè)計方案2.1 算法設(shè)計（1） 選擇排序 在待排序的

5、一組數(shù)據(jù)元素中，選出最小的一個數(shù)據(jù)元素與第一個位置的數(shù)據(jù)元素交換；然后在剩下的數(shù)據(jù)元素當(dāng)中再找最小的與第二個位置的數(shù)據(jù)元素交換，循環(huán)到只剩下最后一個數(shù)據(jù)元素為止。 （2） 冒泡排序 相鄰的兩個元素進(jìn)行比較，將小的調(diào)到前面，大的調(diào)到后面。 （3） 插入排序 待排序的記錄放在數(shù)組R0n-1中排序過程中某一時刻，R被劃分成兩個子區(qū)間R0,i-1 (有序和)Rin-1(無序)。直接插入的基本操作是將當(dāng)前無序區(qū)的一個記錄Ri插入到有序區(qū)R0i-1中適當(dāng)?shù)奈恢?（4） 快速排序 在待排序的數(shù)組的n個元素中取一個元素(一般取第一個)，將其移動到這樣的位置：在其之前的元素的值都小于它，在其之后的元素都大于它，

6、這樣是一趟快速排序；然后對數(shù)組的兩個部分進(jìn)行同樣的操作，直到每部分只有一個記錄為止；總之，每趟使表的第一個元素放在適當(dāng)位置，將表兩分，再對兩子表進(jìn)行同樣的遞歸劃分，直至劃分的子表長度為1。（5）堆排序堆排序中 heap 算法的時間復(fù)雜度與堆所對應(yīng)的完全二叉樹的樹高度 log2n 相關(guān)。而 heapsort 中對 heap 的調(diào)用數(shù)量級為n，所以堆排序的整個時間復(fù)雜度為O(nlog2n) 。并且堆排序是不穩(wěn)定的。堆排序利用了大根堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最小)這一特征，使得在當(dāng)前無序區(qū)中選取最大(或最小)關(guān)鍵字的記錄變得簡單。（6）歸并排序 將兩個或兩個以上的有序表組成一個新的有序表

7、。 （7） 希爾排序?qū)o序數(shù)組分割為若干個子序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，對各個子序列進(jìn)行插入排序；然后再選擇一個更小的增量，再將數(shù)組分割為多個子序列進(jìn)行排序.最后選擇增量為1，即使用直接插入排序，使最終數(shù)組成為有序。增量的選擇：在每趟的排序過程都有一個增量，至少滿足一個規(guī)則 增量關(guān)系 d1 d2 d3 . dt = 1 (t趟排序)；根據(jù)增量序列的選取其時間復(fù)雜度也會有變化，這個不少論文進(jìn)行了研究，在此處就不再深究；本文采用首選增量為n/2,以此遞推，每次增量為原先的1/2，直到增量為1。2.2 功能模塊分析1. 數(shù)據(jù)輸入：采取隨機(jī)函數(shù)實現(xiàn)輸入數(shù)據(jù)表。int inp

8、ut_num()printf(您要給多少個數(shù)排序？ntt);scanf(%d,&data_num);srand(NULL);printf(隨機(jī)產(chǎn)生%d個數(shù):ntt,data_num);for(int i=1;i=1;i-)printf(%d%s,data_arrayi,i!=1? :n);其中增加了輸出空格與換行區(qū)別。3. 主界面實現(xiàn)：printf(DATE:May twenty 2014n); printf(All Copyright Reserved 2014-2015 Wang Guangchun n); printf(ADDRESS: 604 AYITrnnn); printf( n)

9、; printf(各種排序比較 n); printf(默認(rèn)從大到小輸出，可以選擇9進(jìn)行切換n); printf( n); printf( * * n); printf( * * * n); printf( * * n); printf( * 520 * n); printf( * 歡迎 * n); printf( * 使用 * n); printf( * * n); printf( * n); printf(歡迎再次使用!nrn); printf(*n); printf(* . . . . . *n); printf(* . . . . . . *n); printf(* . . . . .

10、. *n); printf(* . . . . . . *n); printf(* . . . . *n); printf(*n);4. 人機(jī)交互界面：printf(n n);printf(請輸入指令 n);printf(* n);printf($ 1.快速排序 $ n);printf($ 2.歸并排序 $ n);printf($ 3.堆排序 $ n);printf($ 4.希爾排序 $ n);printf($ 5.插入排序 $ n);printf($ 6.選擇排序 $ n);printf($ 7.冒泡排序 $ n);printf($ 8.重新隨機(jī)輸入 $ n);printf($ 9.選擇排序

11、方式 $ n);printf(* n);printf( 0.退出 n);printf( n);printf(請選擇：n); printf(請輸入指令 n); printf(* n); printf($ 1.從小到大 $ n); printf($ 0.從大到小 $ n); printf(* n); printf( 87.退出 n); printf( n); printf(請選擇：n);5. 排序方法的實現(xiàn)：（1）選擇排序void chose_sort(int a,int n)int min,temp;for(int i=0;in;i+)min=i;for(int j=i;jaj)min=j;te

12、mp=amin; amin=ai;ai=temp;（2） 希爾排序void ShellInsert(int *a,int d,int n)for (int i=d;i= 0&ajtemp)/從后向前，找到比其小的數(shù)的位置aj+d=aj;/向后挪動j-=d;if(j!=i-d)/存在比其小的數(shù)aj+d=temp;void ShellSort(int* a,int n)int d=n/2;/初始增量設(shè)為數(shù)組長度的一半while(d=1)ShellInsert(a,d,n);d=d/2;/每次增量變?yōu)樯洗蔚亩种唬?） 歸并排序：void _merge(int a,int first,int mi

13、d,int last,int temp)int i=first,j=mid+1,m=mid,n=last,k=0;while(i=m&j=n)if(ai=aj)tempk+=ai+;elsetempk+=aj+;while(i=m)tempk+=ai+;while(j=n)tempk+=aj+;for(i=0;ik;i+)afirst+i=tempi;void MergeSort(int a,int first,int last,int temp) if(firstlast) int mid=(first+last)/2; MergeSort(a,first,mid,temp); MergeS

14、ort(a,mid+1,last,temp); _merge(a,first,mid,last,temp); bool MergeSort(int a,int n) int *p=new intn; if(p=NULL) return false; else MergeSort(a,0,n-1,p); delete p; return true; （4） 堆排序：void HeapAdjust(int *a,int i,int size)/調(diào)整堆 int lchild=2*i;/i的左孩子節(jié)點序號 int rchild=2*i+1;/i的右孩子節(jié)點序號 int max=i;/臨時變量 if(i

15、=size/2)/如果i是葉節(jié)點就不用進(jìn)行調(diào)整 if(lchildamax) max=lchild; if(rchildamax) max=rchild; if(max!=i) swap(ai,amax); HeapAdjust(a,max,size);/避免調(diào)整之后以max為父節(jié)點的子樹不是堆 void BuildHeap(int *a,int size)/建立堆 int i; for(i=size/2;i=1;i-)/非葉節(jié)點最大序號值為size/2 HeapAdjust(a,i,size);void HeapSort(int *a,int size)/堆排序 int j=1; Build

16、Heap(a,size); for(int i=size;i=1;i-) swap(a1,ai); /交換堆頂和最后一個元素，即每次將剩余元素中的最大者放到最后面 /BuildHeap(a,i-1); /將余下元素重新建立為大頂堆 HeapAdjust(a,1,i-1); /重新調(diào)整堆頂節(jié)點成為大頂堆 （5） 冒泡排序：void maopao()int temp;for(int i=1;i=data_num;i+)for(int j=i+1;jdata_arrayj)temp=data_arrayi;data_arrayi=data_arrayj;data_arrayj=temp;（6） 插入

17、排序：void charu()int i,j;int temp; printf(插入排序:n);for(i=1;i0 & tempdata_arrayj-1;j-)data_arrayj=data_arrayj-1;data_arrayj=temp;if(!t) outnew0();else outnew1();（7） 快速排序：void kuaisu1()/快速排序1 printf(快速排序:n); sort(data_array+1,data_array+data_num+1); if(!t) outnew0();else outnew1();3.主要算法流程圖 主程序產(chǎn)生1組隨機(jī)數(shù)將隨機(jī)

18、數(shù)保存在數(shù)組中希爾排序堆排序冒泡排序選擇排序插入排序歸并排序快速排序選擇排序方式輸出無序數(shù)組排序后的結(jié)果選擇操作方式4. 結(jié)果與結(jié)論4.1 正確結(jié)果1. 主界面 人機(jī)交互2. 輸入界面3. 選擇排序方式4. 輸出結(jié)果5. 退出界面4.2錯誤信息5. 算法復(fù)雜度以及穩(wěn)定性分析下圖反映了不同算法排序的時間復(fù)雜度的級別及其空間復(fù)雜度和穩(wěn)定性。算法名稱平均時間輔助空間穩(wěn)定性冒泡排序O(n2)O(1)是選擇排序O(n2)O(1)否插入排序O(n2)O(1)是歸并排序O(nlog2n)O(n)是快速排序O(nlog2n)O(n)否堆排序O(nlog2n)O(1)否希爾排序O(1)否下圖表明了各種算法在不同

19、數(shù)據(jù)規(guī)模下，完成排序所消耗的時間（毫秒為單位），從表中可以顯然看出O(n2)的排序算法比O(nlog2n)的算法 時間多出幾百上千倍，而且隨著數(shù)據(jù)數(shù)據(jù)規(guī)模增大時間比也會隨著增大；因為排序的數(shù)據(jù)采用隨機(jī)數(shù)，順序?qū)⒈淮騺y，快速排序算法優(yōu)于其他排序算法。算法名稱1萬2萬3萬4萬5萬6萬7萬8萬9萬10萬冒泡排序14425497122062186134017491486739488880111939139071選擇排序19981617903254506271669645126361610219643插入排序17871716282882445864468822116491454717914歸并排序369

20、12151822262833快速排序25811141821252932堆排序371216192326303437希爾排序3811152424293540416. 收獲與致謝通過這次課程設(shè)計作業(yè)我著實感受了一次編程的樂趣，從中學(xué)到了不少知識， 雖然都說“程序數(shù)據(jù)結(jié)構(gòu)算法”，但我們在學(xué)習(xí)運用數(shù)據(jù)結(jié)構(gòu)編程之前，并沒能深刻體會到這一點，直到這次課設(shè)實踐。 我們感受最深的一點是：以前用C編程，只是注重如何編寫函數(shù)能夠完成所需要的功能，似乎沒有明確的戰(zhàn)術(shù)，只是憑單純的意識和簡單的語句來堆砌出一段程序。但現(xiàn)在編程感覺完全不同了。在編寫一個程序之前，自己能夠綜合考慮各種因素，首先選取自己需要的數(shù)據(jù)結(jié)構(gòu)，然后選

21、定一種或幾種存儲結(jié)構(gòu)來具體的決定后面的函數(shù)的主要風(fēng)格。最后在編寫每一個函數(shù)之前，可以仔細(xì)斟酌比對，挑選出最適合當(dāng)前狀況的算法。這樣，即使在完整的還沒有寫出來之前，自己心中已經(jīng)有了明確的原圖了。這樣無形中就提高了自己編寫的程序的質(zhì)量。我們還體會到深刻理解數(shù)據(jù)結(jié)構(gòu)的重要性。只有真正理解定義數(shù)據(jù)類型的好處，才能用好這樣一種數(shù)據(jù)結(jié)構(gòu)。了解典型數(shù)據(jù)結(jié)構(gòu)的性質(zhì)是非常有用的，它往往是編寫程序的關(guān)鍵。這次實驗中我們也出現(xiàn)過一些錯誤。但我們經(jīng)過反復(fù)調(diào)試后，發(fā)現(xiàn)并做了修改，從而完成了此次課程設(shè)計。 在這次的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計中，我此次的題目是各種排序，排序?qū)嶋H上是編程設(shè)計中應(yīng)用比較廣泛的知識，通過本次設(shè)計，我對一些

22、基本的內(nèi)部排序有了很好的理解和掌握，并且通過此次課程設(shè)計中的程序運行結(jié)果很好的理解了排序各種算法的穩(wěn)定性和時間復(fù)雜度，既鞏固了課堂上學(xué)到的排序理論，又為自己的編程增強(qiáng)了實踐?？傊?，在這次的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計中，收獲還是蠻多的。也讓自己對數(shù)據(jù)結(jié)構(gòu)這門課程有了更好的認(rèn)識，相信在越來越多的嘗試之后，自己會不斷進(jìn)步不斷提高的。7. 參考文獻(xiàn)1.數(shù)據(jù)結(jié)構(gòu)(C語言版) 嚴(yán)蔚敏 清華大學(xué)出版社2.C語言程序設(shè)計 丁峻嶺 中國鐵道出版社3.C程序設(shè)計 譚浩強(qiáng) 清華大學(xué)出版社8. 附件程序源代碼：#include#include#include#include#include#include#include#in

23、clude#include#include#include#include#includeusing namespace std;const int N=1000010;int data_num,data_arrayN,data_arrayyN;int oldN,aN,t;/數(shù)據(jù)輸入int input_num()printf(您要給多少個數(shù)排序？ntt);scanf(%d,&data_num);srand(NULL);printf(隨機(jī)產(chǎn)生%d個數(shù):ntt,data_num);for(int i=1;i=1;i-)printf(%d%s,data_arrayi,i!=1? :n);/排序后逆序

24、數(shù)據(jù)輸出 從小到大 1 data_numint outnew1()printf(排序后的結(jié)果為:);for(int i=1;i=0;i-)printf(%d%s,data_arrayyi,i!=0? :n);/排序后逆序數(shù)據(jù)輸出 從小到大 0 data_num-1int outnew3()printf(排序后的結(jié)果為:);for(int i=0;idata_num;i+) printf(%d%s,data_arrayyi,i!=data_num-1? :n);/插入排序void charu()int i,j;int temp; printf(插入排序:n);for(i=1;i0 & tempd

25、ata_arrayj-1;j-)data_arrayj=data_arrayj-1;data_arrayj=temp;if(!t) outnew0();else outnew1();/冒泡排序void maopao()int temp;for(int i=1;i=data_num;i+)for(int j=i+1;jdata_arrayj)temp=data_arrayi;data_arrayi=data_arrayj;data_arrayj=temp;/選擇排序void chose_sort(int a,int n)int min,temp;for(int i=0;in;i+)min=i;f

26、or(int j=i;jaj)min=j;temp=amin; amin=ai;ai=temp;/堆排序void HeapAdjust(int *a,int i,int size)/調(diào)整堆 int lchild=2*i;/i的左孩子節(jié)點序號 int rchild=2*i+1;/i的右孩子節(jié)點序號 int max=i;/臨時變量 if(i=size/2)/如果i是葉節(jié)點就不用進(jìn)行調(diào)整 if(lchildamax) max=lchild; if(rchildamax) max=rchild; if(max!=i) swap(ai,amax); HeapAdjust(a,max,size);/避免調(diào)

27、整之后以max為父節(jié)點的子樹不是堆 void BuildHeap(int *a,int size)/建立堆 int i; for(i=size/2;i=1;i-)/非葉節(jié)點最大序號值為size/2 HeapAdjust(a,i,size);void HeapSort(int *a,int size)/堆排序 int j=1; BuildHeap(a,size); for(int i=size;i=1;i-) swap(a1,ai); /交換堆頂和最后一個元素，即每次將剩余元素中的最大者放到最后面 /BuildHeap(a,i-1); /將余下元素重新建立為大頂堆 HeapAdjust(a,1,

28、i-1); /重新調(diào)整堆頂節(jié)點成為大頂堆 /快速排序可以選擇用algorithm里的sort排序?qū)崿F(xiàn)void kuaisu1()/快速排序1 printf(快速排序:n); sort(data_array+1,data_array+data_num+1); if(!t) outnew0();else outnew1();void kuaisu2()/快速排序2 sort(data_array+1,data_array+data_num+1); if(!t) outnew0();else outnew1();/希爾排序void ShellInsert(int *a,int d,int n)for

29、 (int i=d;i= 0&ajtemp)/從后向前，找到比其小的數(shù)的位置aj+d=aj;/向后挪動j-=d;if(j!=i-d)/存在比其小的數(shù)aj+d=temp;void ShellSort(int* a,int n)int d=n/2;/初始增量設(shè)為數(shù)組長度的一半while(d=1)ShellInsert(a,d,n);d=d/2;/每次增量變?yōu)樯洗蔚亩种?歸并排序void _merge(int a,int first,int mid,int last,int temp)int i=first,j=mid+1,m=mid,n=last,k=0;while(i=m&j=n)if(ai

30、=aj)tempk+=ai+;elsetempk+=aj+;while(i=m)tempk+=ai+;while(j=n)tempk+=aj+;for(i=0;ik;i+)afirst+i=tempi;void MergeSort(int a,int first,int last,int temp) if(firstlast) int mid=(first+last)/2; MergeSort(a,first,mid,temp); MergeSort(a,mid+1,last,temp); _merge(a,first,mid,last,temp); bool MergeSort(int a,

31、int n) int *p=new intn; if(p=NULL) return false; else MergeSort(a,0,n-1,p); delete p; return true; /輸出void print() printf(歡迎再次使用!nrn); printf(*n); printf(* . . . . . *n); printf(* . . . . . . *n); printf(* . . . . . . *n); printf(* . . . . . . *n); printf(* . . . . *n); printf(*n);/主函數(shù)，顯示菜單并進(jìn)行算法選擇in

32、t main() printf(DATE:May twenty 2014n); printf(All Copyright Reserved 2014-2015 Wang Guangchun n); printf(ADDRESS: 604 AYITrnnn); printf( n); printf(各種排序比較 n); printf(默認(rèn)從大到小輸出，可以選擇9進(jìn)行切換n); printf( n); printf( * * n); printf( * * * n); printf( * * n); printf( * 520 * n); printf( * 歡迎 * n); printf( *

33、使用 * n); printf( * * n); printf( * n);int n;/變量定義用于菜單選擇input_num();/調(diào)用輸入函數(shù)，請求用戶輸入數(shù)據(jù)while(true)printf(n n);printf(請輸入指令 n);printf(* n);printf($ 1.快速排序 $ n);printf($ 2.歸并排序 $ n);printf($ 3.堆排序 $ n);printf($ 4.希爾排序 $ n);printf($ 5.插入排序 $ n);printf($ 6.選擇排序 $ n);printf($ 7.冒泡排序 $ n);printf($ 8.重新隨機(jī)輸入 $ n);printf($ 9.選擇排序方式 $ n);printf(* n);printf( 0.退出 n);printf( n);printf(請選擇：n);scanf(%d,&n);switch(n) case 1:/快速排序 kuaisu1();break; case 2:/歸并排序 printf(歸并排序：n); for(int j=0;jdata_num;j+) data_arrayyj=data_arrayj+1; MergeSort(data_arrayy,data_num); if(t=1) outnew3(); else outnew2(); break; case 3