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

1、<p><b>　　課程設(shè)計(jì)說(shuō)明書</b></p><p>　題目?jī)?nèi)部排序算法的比較</p><p>　系(部)計(jì)算機(jī)科學(xué)與技術(shù)系</p><p>　專業(yè)(班級(jí))軟件八班</p><p>　姓名</p><p>　學(xué)號(hào)</p><p>　指導(dǎo)教師</p>

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

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

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

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

6、/p><p><b>　　工作計(jì)劃：</b></p><p>　　指導(dǎo)教師簽名：　　　　　　　　　日期:　　</p><p>　　教研室主任簽名：　　　　　　　 日期：　　　　　　　　</p><p>　　系主任簽名：　　　　　　　　　 日期：　　　　　　 </p><p><b>　

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

8、3.1 程序的主要模塊5</p><p>　　2.3.2進(jìn)入排序過(guò)程5</p><p>　　2.3.3程序流程6</p><p>　　第二章 算法與數(shù)據(jù)設(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>　　參考文獻(xiàn)10</b></p><p><b>　　附錄代碼A11</b></p><p><b>　　摘要</b></p><p>　　本次課程設(shè)計(jì)是在《數(shù)據(jù)結(jié)構(gòu)》基礎(chǔ)上設(shè)計(jì)的，它的目的是幫助同學(xué)更深入的了解《數(shù)據(jù)結(jié)構(gòu)》這門課程，使同學(xué)達(dá)到熟練掌握的程度。課程設(shè)計(jì)其中一個(gè)內(nèi)容

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

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

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

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

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

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

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

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

19、數(shù)據(jù)為止。冒泡排序是一次的比較找出最?。ㄗ畲螅┲?，然后將其放置序列的最后一個(gè)位置，再將剩下的從第一個(gè)位置開始至n-i的位置進(jìn)行重復(fù)的操作。</p><p><b>　　3.4快速排序</b></p><p>　　首先在r[1..n]中，第一趟，確定一個(gè)軸r[1]，并把軸上的關(guān)鍵字復(fù)制給r[0]。先從最高位開始比較,若r[1]>=r[high]，則high——；若

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

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

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

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

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

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

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

27、;<b>　　參考文獻(xiàn)</b></p><p>　　譚浩強(qiáng)著，《C語(yǔ)言設(shè)計(jì)題解與上機(jī)指導(dǎo)》，清華大學(xué)出版社，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();// 獲取時(shí)間</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í)/計(jì)數(shù)器的值做為隨機(jī)種子</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移動(dòng)次數(shù)\t比較次數(shù)\t耗時(shí)（單位毫秒）\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>　　//"引用"使得實(shí)參的值在調(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++;//記錄移動(dòng)次數(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);// 對(duì)左邊進(jìn)行遞回</p><p>　　quicksort(number, j+1, right,quicksortMoves,quicksortCompare);// 對(duì)右邊進(jìn)行遞回</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; /* 每趟排序前,標(biāo)志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í)間函數(shù)（精確到毫秒）///////////</p><p>　　int printfTime()</p><p><b>　　{</b></p><p>　　SYSTEMTIME sys;</p><p>　　GetLocalTime( &sys );</p><p>