內(nèi)部排序課程設計---內(nèi)部排序算法的比較

1、<p><b>　　課程設計說明書</b></p><p>　題目內(nèi)部排序算法的比較</p><p>　系(部)計算機科學與技術系</p><p>　專業(yè)(班級)軟件八班</p><p>　姓名</p><p>　學號</p><p>　指導教師</p>

2、;<p>　起止日期</p><p><b>　　課程設計任務書</b></p><p>　　課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法</p><p>　　設計題目：內(nèi)部排序算法的比較</p><p>　　已知技術參數(shù)和設計要求：</p><p><b>　　問題描述：</b>

3、</p><p>　　通過隨機數(shù)據(jù)比較各內(nèi)部排序算法的關鍵字比較次數(shù)和關鍵字移動的次數(shù)，以取得直觀感受。</p><p><b>　　基本要求：</b></p><p>　　1待排序表的表長不小于100；至少要用5組不同的輸入數(shù)據(jù)作比較；排序算法不少于5種。</p><p>　　2 待排序的元素的關鍵字為整數(shù)。</

4、p><p>　　3 比較的指標為有關鍵字參加的比較次數(shù)和關鍵字的移動次數(shù)(關鍵字交換以3次計)。</p><p>　　4演示程序以人機對話的形式進行。每次測試完畢顯示各種比較指標的列表，以便比較各種排序的優(yōu)劣。</p><p>　　5 最后要對結(jié)果作簡單的分析。</p><p><b>　　測試數(shù)據(jù)：</b></p&g

5、t;<p>　　用偽隨機數(shù)產(chǎn)生程序產(chǎn)生。</p><p><b>　　選作內(nèi)容：</b></p><p>　　對不同的表長做試驗分析兩個指標相對于表長變化關系。</p><p><b>　　設計工作量：</b></p><p><b>　　40課時</b><

6、/p><p><b>　　工作計劃：</b></p><p>　　指導教師簽名：　　　　　　　　　日期:　　</p><p>　　教研室主任簽名：　　　　　　　 日期：　　　　　　　　</p><p>　　系主任簽名：　　　　　　　　　 日期：　　　　　　 </p><p><b>　

7、　目錄</b></p><p><b>　　摘要4</b></p><p>　　第一章 系統(tǒng)總體設計5</p><p>　　2.1 原始數(shù)據(jù)5</p><p>　　2.2 輸出數(shù)據(jù)5</p><p>　　2.3 系統(tǒng)架構(gòu)設計5</p><p>　　2.

8、3.1 程序的主要模塊5</p><p>　　2.3.2進入排序過程5</p><p>　　2.3.3程序流程6</p><p>　　第二章 算法與數(shù)據(jù)設計7</p><p><b>　　3.1選擇排序7</b></p><p><b>　　3.2插入排序7</b>

9、;</p><p><b>　　3.3冒泡排序7</b></p><p><b>　　3.4快速排序7</b></p><p><b>　　3.5希爾排序8</b></p><p><b>　　第三章 總結(jié)9</b></p><

10、p><b>　　參考文獻10</b></p><p><b>　　附錄代碼A11</b></p><p><b>　　摘要</b></p><p>　　本次課程設計是在《數(shù)據(jù)結(jié)構(gòu)》基礎上設計的，它的目的是幫助同學更深入的了解《數(shù)據(jù)結(jié)構(gòu)》這門課程，使同學達到熟練掌握的程度。課程設計其中一個內(nèi)容

11、是內(nèi)部排序算法的比較，它要求通過隨機數(shù)據(jù)比較各內(nèi)部排序算法的關鍵字比較次數(shù)和關鍵字移動的次數(shù)，以取得直觀感受。并且待排序表的表長不小于100；至少要用5組不同的輸入數(shù)據(jù)作比較；排序算法不少于5種；比較的指標為有關鍵字參加的比較次數(shù)和關鍵字的移動次數(shù)演示程序以人機對話的形式進行。每次測試完畢顯示各種比較指標的列表，以便比較各種排序的優(yōu)劣。用到的序的種類有：直接選擇排序，冒泡排序，折半插入排序、快速排序、歸并排序。通過這幾種方法的比較：快速

12、排序、歸并排序的效率較高，但適合用于數(shù)據(jù)多的情況；插入排序的時間復雜度同于直接選擇排序、冒泡排序，但它大大降低比較次數(shù)，所有它的效率高于直接選擇排序，冒泡排序。</p><p>　　關鍵字：選擇排序；冒泡排序；插入排序；快速排序；希爾排序</p><p>　　第一章 系統(tǒng)總體設計</p><p><b>　　2.1 原始數(shù)據(jù)</b></p

13、><p>　　用戶輸入關鍵字的個數(shù)，數(shù)據(jù)由隨機序列生成器和特殊序列生成器生成 。</p><p><b>　　2.2 輸出數(shù)據(jù)</b></p><p>　　產(chǎn)生的序列分別用選擇排序、插入排序、冒泡排序、快速排序、希爾排序等這些排序方法 進行排序，輸出關鍵字的排序時間 、比較次數(shù)、移動次數(shù)。</p><p>　　2.3 系統(tǒng)架

14、構(gòu)設計</p><p>　　2.3.1 程序的主要模塊</p><p>　　程序的主要模塊主要模塊排序算法演示模塊</p><p>　　2.3.2進入排序過程</p><p>　　a.選擇排序，根據(jù)簡單選擇排序的算法，輸出排序時間、比較次數(shù)、移動次數(shù)</p><p>　　b.插入排序，根據(jù)插入排序算法，輸出排序時間、比

15、較次數(shù)、移動次數(shù)</p><p>　　c.冒泡排序，根據(jù)冒泡排序的算法，輸出排序時間、比較次數(shù)、移動次數(shù)</p><p>　　d.快速排序，根據(jù)快速排序的算法，輸出排序時間、比較次數(shù)、移動次數(shù)</p><p>　　e.希爾排序，根據(jù)歸并排序的算法，輸出排序時間、比較次數(shù)、移動次數(shù)</p><p><b>　　2.3.3程序流程<

16、;/b></p><p>　　第二章 算法與數(shù)據(jù)設計</p><p><b>　　3.1選擇排序</b></p><p>　　簡單選擇排序的每一趟都是從待排的數(shù)據(jù)元素中選出一個最?。ㄗ畲螅┑囊粋€元素，順序的放在已經(jīng)排好的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排序完畢。</p><p><b>　　3.2插入

17、排序</b></p><p>　　這是一種最簡單的排序方法，它的基本操作時將一個記錄插入到一個已經(jīng)排好序的有序表中，從而得到一個新的記錄數(shù)增1的有序表。其效率：從空間的角度來看待，它只需要一個輔助的空間，從時間上來看的話，排序的基本操作是比較兩個關鍵字的大小和移動（本程序中將移動和交換看成一樣）記錄。在整個排序的過程中，當待排序列中的關鍵字非遞減有序的話，那么比較次數(shù)最小n-1，且不需要移動，當待排序

18、列逆序時，比較次數(shù)達到最大（n+2）（n-1）/2，記錄的移動的次數(shù)也達到最大值（n+4）（n-1）/2。取平均值得時候直接插入排序的時間復雜度O(n²)。排序是穩(wěn)定的。</p><p><b>　　3.3冒泡排序</b></p><p>　　這種排序的比較基本思想就是兩兩比較待排序的數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個數(shù)據(jù)元素的次序相反時候，就進行交換，知道沒有反序的

19、數(shù)據(jù)為止。冒泡排序是一次的比較找出最?。ㄗ畲螅┲担缓髮⑵浞胖眯蛄械淖詈笠粋€位置，再將剩下的從第一個位置開始至n-i的位置進行重復的操作。</p><p><b>　　3.4快速排序</b></p><p>　　首先在r[1..n]中，第一趟，確定一個軸r[1]，并把軸上的關鍵字復制給r[0]。先從最高位開始比較,若r[1]>=r[high]，則high——；若

20、r[1]<r[high],r[low]=r[high],在高位找到第一個比r[1]小的的值后.再從低位開始比較，若r[low]<=r[1],則low++，若r[low]>r[1],r[high]=r[low],在低位找到第一個比r[1]大的數(shù)，依次重復上敘兩個比較動作，直到全部比較完成，將r[i]放到"中間"某個位置上使得r[1]左邊所有的關鍵字小于r[1]右邊所有記的關鍵字，并保留該位置，使得數(shù)組

21、分成了兩組。再采用遞歸，直至每組只有一個數(shù)據(jù)，即已排好了序。</p><p><b>　　算法分析</b></p><p>　　就平均速度而言，快速排序是已知內(nèi)部排序方法中最好的一種排序方法，其時間復雜度為O(nlog(n))。但是，在最壞情況下（基本有序時）快速排序所需的比較次數(shù)和冒泡排序的比較次相同，其時間復雜度為O（n^2）。快速排序需要一個棧作輔助空間，用來實

22、現(xiàn)遞歸處理左、右子兩組。在最壞情況下，遞歸深度為n，因此所需棧的空間大小為O(n)數(shù)量級。快速排序是不穩(wěn)定的。</p><p><b>　　3.5希爾排序</b></p><p>　　屬于一種插入排序類的方法，先將整個待排序記錄分成若干個子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對整體記錄進行一次直接插入排序。實質(zhì)上就是一個將序列分塊化，然后再對

23、各個塊進行排序，化整為零的操作，最后待序列差不多有序的時候進行一次化零為整操作，實現(xiàn)最后一次的插入排序。</p><p><b>　　第三章 總結(jié)</b></p><p>　　我做的課程設計是內(nèi)部排序的比較，之所以選擇這個題目是因為老師說這個實用性比較強。并且，對于排序我是懂的少之又少，也希望通過這次實訓能夠?qū)⑺莆蘸?。這次實訓的理論基礎是建立在最后一段時間的學習《數(shù)

24、據(jù)結(jié)構(gòu)》中的內(nèi)部排序算法上，通過對各個內(nèi)部排序的算法的分析，比較它們所要花費的時間，移動次數(shù)、比較次數(shù)等等。</p><p>　　確實，這次的課程設計讓我對排序有了很深刻的了解。首先，幾乎是一籌莫展，因為，在上理論課將排序的時候沒認真聽。所以，不得不把書關于排序的一字一字的仔細看，仔細理解。然后就開始編寫代碼。先是把各個排序的代碼寫出來，我所用的排序有希爾排序、快速排序、冒泡排序、插入排序、選擇排序。</p

25、><p>　　當然，在寫代碼的過程中也遇到了些許問題。比如說寫那個隨機取數(shù)的函數(shù)的時候不知道怎么寫，后來自己百度了一下，然后也詢問了老師、同學最后才把它寫出來。另外，我覺得還有一個難點就是計算每個排序用的時間。因為，要用到一個時間函數(shù)嘛，然后之前又沒有接觸過，所以，在寫代碼的時候，在那里就卡殼了。后來還是問了同學，老師的指點才弄明白。</p><p>　　總的來說，覺得這次的課程設計還是偏容易

26、的，我也有很大的收獲。加強了自己的動手操作能力，也讓自己學會獨立思考，同時增加了自己的知識。最重要的是，對排序有了更為深刻的了解。當然，通過這次的課程設計也發(fā)現(xiàn)了自己很多的不足。深深地意識到了自己的操作能力還有待加強。在平時，應該多編寫一些程序，同時，也應該擴大自己的知識面，多去鉆研，多動腦、動手。。</p><p>　　最后，對傳授自己數(shù)據(jù)結(jié)構(gòu)知識的曾俊勇老師說一聲謝謝！</p><p>

27、;<b>　　參考文獻</b></p><p>　　譚浩強著，《C語言設計題解與上機指導》，清華大學出版社，2001.3</p><p><b>　　附錄代碼A</b></p><p>　　#include <stdio.h></p><p>　　#include <stdlib.

28、h></p><p>　　#include <windows.h></p><p>　　#include <time.h></p><p>　　#define MAX 20000</p><p>　　#define SWAP(x,y) {int t; t = x; x = y; y = t;} // 交換函數(shù)&l

29、t;/p><p>　　void selsort(int[],int &,int &); // 選擇排序</p><p>　　void insort(int[],int &,int &);// 插入排序</p><p>　　void bubsort(int[],int &,int &);/

30、/ 冒泡排序</p><p>　　void quicksort(int[],int,int,int &,int &);// 快速排序</p><p>　　int printfTime();// 獲取時間</p><p>　　void shellsort(int [],int &,int &);// 希爾排序

31、</p><p>　　int main()</p><p><b>　　{</b></p><p>　　system("color 4f");//定義界面顏色</p><p>　　int quicksortMoves=0,quicksortCompare=0,insortCompare=0,insor

32、tMoves=0,selsortCompare=0,selsortMoves=0,bubsortCompare=0,bubsortMoves=0,shellsortCompare=0,shellsortMoves=0;</p><p>　　int number1[MAX] = {0};</p><p>　　int number2[MAX] = {0};</p><p&g

33、t;　　int number3[MAX] = {0};</p><p>　　int number4[MAX] = {0};</p><p>　　int number5[MAX] = {0};</p><p>　　int i,selsortTime1,selsortTime2,insortTime1,insortTime2,bubsortTime1,bubsortTi

34、me2,quicksortTime1,quicksortTime2,mergeTime1,mergeTime2,shellsortTime1,shellsortTime2;</p><p>　　srand(time(NULL));//使用系統(tǒng)定時/計數(shù)器的值做為隨機種子</p><p>　　for(i = 0; i < MAX; i++)</p><p>&l

35、t;b>　　{</b></p><p>　　number1[i] = rand()%100; //0~100之間的整數(shù)</p><p>　　number2[i] = number1[i];</p><p>　　number3[i] = number1[i];</p><p>　　number4[i]

36、= number1[i];</p><p>　　number5[i] = number1[i];</p><p><b>　　}</b></p><p>　　selsortTime1=printfTime();</p><p>　　selsort(number1,selsortMoves,selsortCompare);

37、</p><p>　　selsortTime2=printfTime();</p><p>　　insortTime1=printfTime();</p><p>　　insort(number2,insortMoves,insortCompare);</p><p>　　insortTime2=printfTime();</p>

38、<p>　　bubsortTime1=printfTime();</p><p>　　bubsort(number3,bubsortMoves,bubsortCompare);</p><p>　　bubsortTime2=printfTime();</p><p>　　quicksortTime1=printfTime();</p>&

39、lt;p>　　quicksort(number4,0, MAX-1, quicksortMoves,quicksortCompare);</p><p>　　quicksortTime2=printfTime();</p><p>　　shellsortTime1=printfTime();</p><p>　　shellsort(number5,shells

40、ortMoves,shellsortCompare);</p><p>　　shellsortTime2=printfTime();</p><p>　　printf("\n\n\t\t\t\t五種排序算法的比較\n\n");</p><p>　　printf("\n\t算法名稱\t移動次數(shù)\t比較次數(shù)\t耗時（單位毫秒）\n\n&qu

41、ot;);</p><p>　　printf("\n\t選擇排序\t%d %d %d 毫秒\n\n",selsortMoves,selsortCompare,selsortTime2-selsortTime1);</p><p>　　printf("\n\t插入排序\t%d %d %d 毫秒\n\n&q

42、uot;,insortMoves,insortCompare,insortTime2-insortTime1);</p><p>　　printf("\n\t冒泡排序\t%d %d %d 毫秒\n\n",bubsortMoves,bubsortCompare,bubsortTime2-bubsortTime1);</p><p>　　print

43、f("\n\t快速排序\t%d %d %d 毫秒\n\n",quicksortMoves,quicksortCompare,quicksortTime2-quicksortTime1);</p><p>　　printf("\n\t希爾排序\t%d %d %d 毫秒\n\n",shellsortMove

44、s,shellsortCompare,shellsortTime2-shellsortTime1);</p><p>　　printf("\n\t");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　/////

45、/////////////////////選擇排序/////////////////////////</p><p>　　void selsort(int number[],int &selsortMoves,int &selsortCompare)</p><p>　　//"引用"使得實參的值在調(diào)用函數(shù)與被調(diào)用函數(shù)都改變，有指針的作用</p>

46、;<p><b>　　{</b></p><p>　　int i, j, m,t;</p><p>　　for(i = 0; i < MAX-1; i++) </p><p><b>　　{</b></p><p><b>　　m = i;</b></

47、p><p>　　for(j = i+1; j < MAX; j++)</p><p><b>　　{</b></p><p>　　if(number[j] < number[m])</p><p><b>　　{</b></p><p><b>　　m =

48、j;</b></p><p><b>　　}</b></p><p>　　selsortCompare++;</p><p><b>　　}</b></p><p>　　if( i != m)</p><p><b>　　{</b></

49、p><p>　　SWAP(number[i], number[m]);</p><p>　　selsortMoves++;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p&g

50、t;<p>　　////////////////////////////插入排序/////////////////////</p><p>　　void insort(int number[],int &insortMoves,int &insortCompare)</p><p><b>　　{</b></p><p

51、>　　int i, j,temp,t;</p><p>　　for(j = 1; j < MAX; j++) </p><p><b>　　{</b></p><p>　　temp = number[j];</p><p>　　i = j - 1;</p><p>　　while(te

52、mp < number[i]) </p><p><b>　　{</b></p><p>　　number[i+1] = number[i];</p><p>　　insortMoves++;//記錄移動次數(shù)</p><p>　　insortCompare++;//記錄比較次數(shù)</p><p&g

53、t;<b>　　i--;</b></p><p>　　if(i == -1)</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　insortCompare++;</p><p>　　number

54、[i+1] = temp;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　///////////////////////冒泡排序//////////////////////////////////</p><p>　　void bubsort(i

55、nt number[],int &bubsortMoves,int &bubsortCompare)</p><p><b>　　{</b></p><p>　　int i, j, flag = 1,t;</p><p>　　for(i = 0 ;i < MAX-1 && flag == 1; i++) &

56、lt;/p><p><b>　　{</b></p><p><b>　　flag = 0;</b></p><p>　　for(j = 0; j < MAX-i-1; j++) </p><p><b>　　{</b></p><p>　　if(num

57、ber[j+1] < number[j]) </p><p><b>　　{</b></p><p>　　SWAP(number[j+1], number[j]);</p><p>　　bubsortMoves++;</p><p><b>　　flag = 1;</b></p>

58、<p><b>　　}</b></p><p>　　bubsortCompare++;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p&g

59、t;　　////////////////////////快速排序////////////////////////////</p><p>　　void quicksort(int number[], int left, int right,int &quicksortMoves,int &quicksortCompare) </p><p><b>　　{<

60、/b></p><p>　　int i, j, s;</p><p>　　if(left < right) </p><p><b>　　{</b></p><p>　　s = number[(left+right)/2];</p><p>　　i = left - 1;</p&

61、gt;<p>　　j = right + 1;</p><p><b>　　while(1) </b></p><p><b>　　{</b></p><p>　　while(number[++i] < s) ;// 向右找</p><p>　　while(number[--j]

62、 > s) ;// 向左找</p><p>　　if(i >= j)break;</p><p>　　SWAP(number[i], number[j]);</p><p>　　quicksortMoves++;</p><p><b>　　}</b></p><p>　　quicks

63、ortCompare++;</p><p>　　quicksort(number, left, i-1,quicksortMoves,quicksortCompare);// 對左邊進行遞回</p><p>　　quicksort(number, j+1, right,quicksortMoves,quicksortCompare);// 對右邊進行遞回</p><p&

64、gt;<b>　　}</b></p><p><b>　　}</b></p><p>　　//////////////////////////////希爾排序法//////////////////</p><p>　　void shellsort(int number[],int &shellsortMoves,

65、int &shellsortCompare)</p><p><b>　　{</b></p><p>　　int i,j,t,flag,gap=MAX,temp;</p><p>　　while(gap>1)</p><p><b>　　{</b></p><p&g

66、t;　　gap=gap/2;</p><p><b>　　do{</b></p><p>　　flag=0; /* 每趟排序前,標志flag置0 */ </p><p>　　for(i=0;i<=MAX-1-gap;i++)</p><p><b>　　{</b&g

67、t;</p><p>　　j=i+gap;/*以number[i]、number[j]分別表示gap/2以前、以后的元素*/</p><p>　　if(number[i]>number[j])</p><p><b>　　{</b></p><p>　　temp=number[i];</p>&

68、lt;p>　　number[i]=number[j];</p><p>　　number[j]=temp;</p><p><b>　　flag=1;</b></p><p>　　shellsortMoves++;</p><p><b>　　}</b></p><p>

69、;　　shellsortCompare++;</p><p><b>　　}</b></p><p>　　}while(flag!=0);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　///////

70、//////////時間函數(shù)（精確到毫秒）///////////</p><p>　　int printfTime()</p><p><b>　　{</b></p><p>　　SYSTEMTIME sys;</p><p>　　GetLocalTime( &sys );</p><p>