數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--各種內(nèi)部排序性能比較

1、<p><b>　　課程設(shè)計報告</b></p><p>　　課程設(shè)計題目： </p><p>　　各種內(nèi)部排序性能比較</p><p><b>　　摘 要</b></p><p>　　該程序是用C++語言實現(xiàn)的，在程序中隨機生成N個數(shù)據(jù)，對這些數(shù)進行多種方法的排序，所用

2、的這些排序方法都是在數(shù)據(jù)結(jié)構(gòu)課中學(xué)習(xí)過的比如：插入排序、快速排序、冒泡排序等，而且還要對各個排序做出相應(yīng)的比較。</p><p>　　該演示程序以用戶和計算機的對話方式執(zhí)行，每次測試完畢，列表顯示各種比較指標值。</p><p>　　最后對結(jié)果作出了簡單分析并將結(jié)果排序，包括對各組數(shù)據(jù)得出結(jié)果波動大小給予解析。</p><p>　　關(guān)鍵字：插入排序、快速排序、選擇排

3、序、冒泡排序、比較的個數(shù)、改變的個數(shù)、所用的時間。</p><p><b>　　目 錄</b></p><p>　　摘要····················

4、3;····························Ⅰ</p><p>　　目錄····

5、····································

6、3;········Ⅱ</p><p>　　問題描述·······················

7、3;··················1</p><p>　　題目內(nèi)容·············

8、3;························1</p><p>　　基本要求·······

9、3;······························1</p><p>　　測試數(shù)據(jù)·

10、3;····································1&

11、lt;/p><p>　　需求分析································&#

12、183;·········2</p><p>　　輸入輸出的形式和輸入值的范圍··················2</p><

13、;p>　　程序所能達到的功能····························2</p><p>　　概要設(shè)計·&

14、#183;····································

15、;····3</p><p>　　程序所需的抽象數(shù)據(jù)類型························3</p><

16、;p>　　系統(tǒng)功能模塊··································3&

17、lt;/p><p>　　外部功能模塊圖································

18、; 3</p><p>　　主函數(shù)功能模塊圖·······························

19、3</p><p>　　詳細設(shè)計································

20、···········4</p><p>　　4.1 整個程序的流程圖···················

21、3;··············4</p><p>　　4.2 插入排序及其主要代碼················

22、··············5</p><p>　　4.3 二路合并排序及其主要代碼················

23、··········6</p><p>　　4.4 冒泡排序及其主要代碼····················&#

24、183;·········7</p><p>　　4.5 快速排序及其主要代碼····················

25、3;·········8</p><p>　　4.6 選擇排序及其主要代碼·····················

26、·········9</p><p>　　5 調(diào)試分析······················

27、83;····················10</p><p>　　5.1 主界面 ··········

28、3;································11</p><p>　　5

29、.2 計算中的程序界面··································12<

30、;/p><p>　　5.3 排序結(jié)束后的界面·······························&#

31、183;··13</p><p>　　5.4 調(diào)試分析結(jié)果····························&

32、#183;·········14</p><p>　　6 總結(jié)······················

33、;·························15</p><p><b>　　1問題描述</b></p><p>

34、;<b>　　1.1題目內(nèi)容</b></p><p>　　本演示程序?qū)σ韵?種常用的內(nèi)部排序算法進行實測比較：起泡排序、直接插入排序、簡單選擇排序、快速排序、二路合并排序。</p><p>　　主要工作是設(shè)法在已知算法中的適當位置插入對關(guān)鍵字的比較次數(shù)和移動次數(shù)的計數(shù)操作。程序還可以考慮幾組數(shù)據(jù)的典型性，如：正序、逆序和不同程度的亂序。注意采用分塊調(diào)試的方法。<

35、/p><p><b>　　1.2基本要求</b></p><p>　　1． 待排序表的表長不小于100，其中數(shù)據(jù)要用的隨機數(shù)產(chǎn)生程序產(chǎn)生，至少要用5組不同的輸入數(shù)據(jù)體比較，比較的指標為：有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動次數(shù)（關(guān)鍵字交換計為3次的移動）。</p><p>　　2． 演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“提示信

36、息”下，用戶可由鍵盤輸入待排序表的表長和不同的測試數(shù)據(jù)的數(shù)組，每次測試完畢，列表顯示各種比較指標值。</p><p>　　3．最后對結(jié)果作出簡單分析，包括對各組數(shù)據(jù)得出結(jié)果波動大小給予解析。</p><p><b>　　1.3 測試數(shù)據(jù)</b></p><p>　　由函數(shù)rand隨機產(chǎn)生的數(shù)據(jù)。</p><p><

37、b>　　2 需求分析</b></p><p>　　2.1輸入輸出的形式和輸入值的范圍</p><p>　　由于程序中所需的數(shù)據(jù)都是有函數(shù)隨機生成的整形數(shù)，不需要用戶自己輸入，用戶只需要對演示程序中的一些提示做一些必要的選擇以便于程序的執(zhí)行。</p><p>　　程序輸出的是對五種排序做的一些比較，即輸出五種排序各排序過程中所比較的數(shù)據(jù)的個數(shù)，交換的

38、數(shù)據(jù)的次數(shù)，和排序完成所用的時間。六種排序依次在計算機終端上顯示，便于用戶觀察。</p><p>　　輸入值的范圍等價于程序中隨機生成的數(shù)據(jù)的個數(shù)，即待排序表的表長不小于100，至少要用5組不同的輸入數(shù)據(jù)體比較，比較的指標為：有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動次數(shù)（關(guān)鍵字交換計為3次的移動），在該程序中，隨機生成的數(shù)據(jù)個數(shù)被初始化為了10000，數(shù)據(jù)越大就越容易比較。</p><p>　

39、　2.2程序所能達到的功能</p><p>　　輸入N個隨機整數(shù)，對這些數(shù)進行多種方法進行排序，并對這些排序做比較，在屏幕上輸出每種排序方法所比較的次數(shù)，交換的次數(shù)，和用掉的時間。</p><p>　　任意性：系統(tǒng)首先生成10000個隨機整數(shù)，然后分別用不同的排序方法對其進行升序排序，給出每種方法的比較次數(shù)或所用時間</p><p>　　友好性：界面要友好，輸入有提

40、示，盡量展示人性化</p><p>　　可讀性：源程序代碼清晰、有層次</p><p>　　健壯性：用戶輸入非法數(shù)據(jù)時，系統(tǒng)要及時給出警告信息</p><p><b>　　3 概要設(shè)計</b></p><p>　　3.1程序所需的抽象數(shù)據(jù)類型</p><p>　　typedef struct St

41、udentData</p><p><b>　　{ </b></p><p>　　int num; //存放關(guān)鍵字，如零時變量，還有哨兵</p><p><b>　　}Data;</b></p><p>　　typedef struct LinkList</p><p>&l

42、t;b>　　{</b></p><p>　　int Length; //存放隨機數(shù)的個數(shù)</p><p>　　Data Record[MAXSIZE];//用數(shù)組存放所有的隨機數(shù)</p><p>　　}LinkList;</p><p>　　3.2 系統(tǒng)功能模塊</p><p>　　3.2.1 外部

43、功能模塊圖</p><p>　　圖 3.2.1 外部功能模塊圖</p><p>　　3.2.2 主函數(shù)功能模塊圖</p><p>　　圖 3.2.2 主函數(shù)功能模塊圖</p><p><b>　　4詳細設(shè)計</b></p><p>　　4.1 整個程序的流程圖</p><p&g

44、t;　　圖4.1.1 整個程序的流程圖</p><p>　　·4.2 插入排序及其主要代碼</p><p>　　直接插入排序（Straight Insertion Sort）是一種最簡單的排序方法，它的基本操作是將一個紀錄插入到已排好序的有序表中，從而得到一個新的、紀錄數(shù)增1的有序表。</p><p>　　例如，已知待排序的一組紀錄的初始排列如下所示：&l

45、t;/p><p>　　R(49)、R(38)、R(65)、R(97)、R(76)、R(13)、R(27)、R(49)…… （4-1）</p><p>　　假設(shè)在排序過程中，前4個記錄已按關(guān)鍵字遞增的次序重新排列，構(gòu)成一個含4個紀錄的有序序列</p><p>　　{ R(38)、R(49)、R(65)、R(97) }

46、 （4-2） 現(xiàn)要將式（4-1）中的第5個紀錄插入上述序列，以得到一個新的含5個紀錄的有序序列，則首先要在式（4-2）的序列中進行查找以確定R(76)、所應(yīng)插入的位置，然后進行插入。假設(shè)從R(97)、起向左進行順序查找，由于65<76<97，則R(76)應(yīng)插入在R(65)和R(97)之間，從而等到下列新的有序序列</p><p>　　{ R(38)、R(49)、R(65)、R(76)、

47、R(97) } （4-3）稱從式（4-2）到（4-3）的過程為一趟直接插入排序。一般情況下，第i趟直接插入排序的操作為：在含有i-1個紀錄的有序子序列r[1...i-1]中插入一個記錄r[i]后，變成含有i個記錄的有序子序列r[1...i]；并且，和順序查找類似，為了在查找插入位置的過程中避免數(shù)組下標出界，在r[0]處設(shè)置監(jiān)視哨。在自i-1起往前搜索的過程中，可以同時后移記錄。整個排序

48、過程為進行n-1趟插入，即：先將序列中的第1個記錄看成是一個有序的子序列，然后從第2個記錄起逐個進行插入，直至整個序列變成按關(guān)鍵字非遞減有序序列為止。代碼如下：</p><p>　　[初始關(guān)鍵字]： （49） 38 65 97 76 13 27 49</p><p>　　i = 2: (38) (38 49) 65 97 76 13

49、 27 49</p><p>　　i = 3: (38) (38 49 65) 97 76 13 27 49</p><p>　　i = 4: (38) (38 49 65 97) 76 13 27 49</p><p>　　i = 5: (76) (38 49 65

50、76 97) 13 27 49</p><p>　　i = 6: (13) (13 38 49 65 76 97) 27 49</p><p>　　i = 7: (27) (13 27 38 49 65 76 97) 49</p><p>　　i = 8: (49) (1

51、3 27 38 49 49 65 76 97)</p><p><b>　　監(jiān)視哨L.r[0]</b></p><p>　　4.3二路合并排序及其主要代碼</p><p>　　二路合并排序是另一類時間復(fù)雜度為O(nlog2n)的排序方法，它的基本思想是：將有n個元素的序列看成是n個長度為1的有序子序列，然后兩兩合并子

52、序列，得到【n/2】個長度為2或1的有序子序列；再兩兩合并，…，直到得到一個長度為n的有序子序列時結(jié)束，如圖所示。</p><p>　　template <class T></p><p>　　void Merge(T A[],int i1,int j1,int i2,int j2) </p><p>　　{ // i1,j1是子序列1的下、上界，

53、i1,j2是子序列2的下、上界</p><p>　　T *Temp=new T[j2-i1+1]; //分配能存放兩個子序列的臨時數(shù)組</p><p>　　int i=i1,j=i2,k=0; //i,j是兩個子序列的游動指針，k是Temp的游動指針</p><p>　　while (i<=j1&am

54、p;&j<=j2) //若兩個子序列都不空，則循環(huán)</p><p>　　if (A[i]<=A[j]) Temp[k++]=A[i++]; //將A[i]和A[j]中較小的存入Temp[k]</p><p>　　else Temp[k++]=A[j++];</p><p>　　while (i<=j1) T

55、emp[k++]=A[i++]; //若第一個子序列中還有剩余的就存入Temp</p><p>　　while (j<=j2) Temp[k++]=A[j++]; //若第二個子序列中還有剩余的就存入Temp</p><p>　　for (i=0; i<k; i++) A[i1++]=Temp[i]; //將臨時數(shù)組中的元素倒回A</p><

56、p>　　delete [] Temp; </p><p><b>　　}</b></p><p>　　template <class T></p><p>　　void MergeSort(T A[], int n)</p><p><b>　　{

57、</b></p><p>　　int i1,j1,i2,j2; //i1,j1是子序列1的下、上界，i2,j2是子序列2的下、上界</p><p>　　int size=1; //子序列中元素個數(shù)，初始化為1。</p><p>　　while (size<n){ </p><p

58、><b>　　i1=0; </b></p><p>　　while (i1+size<n){ //若i1+size<n，則說明存在兩個子序列，需再兩兩合并</p><p>　　i2=i1+size; //確定子序列2的下界</p><p>　　j1=i2-1; /

59、/確定子序列1的上界</p><p>　　if (i2+size-1>n-1) </p><p>　　j2=n-1; //若第2個子序列中不足size個元素，則置子序列2的上界j2=n-1</p><p>　　else j2=i2+size-1; //否則有size個，置j2=i2+size-1</p><p>　　Me

60、rge(A,i1,j1,i2,j2); //合并相鄰兩個子序列</p><p>　　i1=j2+1; //確定下一次合并第一個子序列的下界</p><p><b>　　} </b></p><p>　　size*=2; //元素個數(shù)擴大一倍</p>

61、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　程序只將A數(shù)組中相鄰的兩個子序列（A[i1],A[i1+1],.....,A[j1]）和(A[i2],A[i2+1],...,A[j2])合并為一個子序列，其中i1、ji是子序列1在數(shù)組A中的下標，表示子序列的下、上界（i2<j2）。由于兩

62、個子序列是相鄰的，即j1+1=i2，因此它們中的元素總數(shù)為j2-i1+1。為實現(xiàn)上述兩個子序列的合并，程序一開始就分配能存放兩個子序列的臨時數(shù)組（Temp[0],Temp[1],...,Temp[j2-i1]），用于保存合并的中間結(jié)果，本地合并結(jié)束后，再將臨時數(shù)組中的元素“倒回”A中。</p><p>　　4.4 冒泡排序及其主要算法</p><p>　　冒泡排序（bubble sort）

63、的過程很簡單。首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進行比較，若為逆序，則將兩個記錄交換之，然后比較第二個記錄和第三個記錄的關(guān)鍵字。依次類推，直至第n-1個記錄和第n個記錄的關(guān)鍵字進行比較為止。上述過程稱做第一趟冒泡排序，其結(jié)果使得關(guān)鍵字最大的記錄被安置到最后一個記錄的位置上。然后進行第二趟冒泡排序，對前n-1個記錄進行同樣操作，其結(jié)果是使關(guān)鍵字次大的記錄被安置到第n-1個記錄的位置上。一般地，第i趟冒泡排序是從L.r[1]到L.

64、[n-i+1]依次比較相鄰兩個記錄的關(guān)鍵字，并在“逆序”是交換相鄰記錄，其結(jié)果是這n-i+1個記錄中關(guān)鍵字最大的紀錄被交換到第n-i+1的位置上。整個冒泡排序過程需進行k（1<=k<n）趟，顯然，判別冒泡排序結(jié)束的條件應(yīng)該是“在一趟排序過程中沒有進行過交換記錄的操作”。</p><p>　　4.5 快速排序及其主要代碼</p><p>　　快速排序（Quick sort）是對冒

65、泡排序的一種改進。它的基本思想是，通過一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。</p><p>　　一趟快速排序的具體做法是：附設(shè)兩個指針low和high，它們的初值分別為low和high，設(shè)樞軸記錄的關(guān)鍵字為pivotkey，則首先從high所指位置起向前搜索找到第一個關(guān)鍵字小于pivotkey的記錄和樞軸

66、記錄互相交換，然后從low所指位置起向后搜索，找到第一個關(guān)鍵字大于pivotkey的記錄和樞軸記錄交換，重復(fù)這兩步直至low=high為止。其算法如下：</p><p>　　4.6 選擇排序及其主要代碼</p><p>　　選擇排序（Selection sort）的基本思想是：每一趟在n-i+1(i=1,2,…,n-1)個記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i個記錄。其中最簡單的是

67、簡單選擇排序。一趟簡單選擇排序的操作為：通過n-i次的關(guān)鍵字間的比較，從n-i+1個記錄中選出關(guān)鍵字最小的記錄，并和第i個記錄交換之。程序中選擇排序的代碼如下：</p><p>　　4.7 堆排序及其主要代碼</p><p>　　堆排序（Heap Sort）只需要一個記錄大小的輔助空間，每個待排序的記錄僅占有一個存儲空間。若在輸出堆頂?shù)淖钚≈抵螅沟檬Ｓ鄋-1個元素的序列重又建成一個堆，

68、則得到n個元素中的次小值。如此反復(fù)執(zhí)行，便能得到一個無序序列，這個過程稱之為堆排序。</p><p>　　由一個無序序列建成一個堆，首先以堆頂元素和其左右子樹根結(jié)點的值比較之，由于右子樹根結(jié)點的值小于左子樹根結(jié)點的值且小于根結(jié)點的值，則將29和97交換之；由于97替代了27后破壞了右子樹的“堆”，則需進行和上述相同的調(diào)整，直至葉子結(jié)點，調(diào)整后堆頂為n-1個元素中的最小值。重復(fù)上述過程，將堆頂元素27和堆中最后一個

69、元素97交換且調(diào)整，得到新堆。使記錄序列按關(guān)鍵字非遞減有序序列排列，則在堆排序的算法中先建一個“大頂堆”，即先選得一個關(guān)鍵字為最大的記錄并與序列中最后一個記錄交換，然后對序列中前n-1記錄進行篩選，重新將它調(diào)整為一個“大頂堆”，如此反復(fù)直至排序結(jié)束。堆排序的代碼如下：</p><p><b>　　5調(diào)試分析</b></p><p><b>　　5.1 主界面

70、</b></p><p>　　圖 5.1 程序主界面圖</p><p>　　5.2 計算中的程序界面</p><p>　　圖 5.2 計算中的程序界面</p><p>　　5.3 排序結(jié)束后的界面</p><p>　　圖 5.3 排序結(jié)束后的界面</p><p>　　5.4 調(diào)試分析

71、結(jié)果</p><p>　　插入排序：比較的次數(shù)為25086233，交換的次數(shù)為25066249，花費的時間為1282ms；希爾排序：比較的次數(shù)為3804518，交換的次數(shù)為3751672，花費的時間為203ms；快速排序：比較的次數(shù)為150261，交換的次數(shù)為62844，花費的時間為0ms；堆排序：比較的次數(shù)為235330，交換的次數(shù)為124185，花費的時間為15ms；冒泡排序：比較的次數(shù)為49995000，交

72、換的次數(shù)為27345138，花費的時間為4360ms；選擇排序：比較的次數(shù)為50005000，交換的次數(shù)為9991，花費的時間為2765。</p><p>　　算法效率是依據(jù)算法執(zhí)行的時間來看的，從上面的數(shù)據(jù)來看，雖然插入排序的算法簡潔，容易實現(xiàn)，但是從它執(zhí)行的時間1282ms來看它的效率并不是很高，而且比較次數(shù)和交換次數(shù)都比較多，在這六種排序中效率是很底的；希爾排序的時間復(fù)雜度較直接排序低，在六種內(nèi)部排序中效率

73、居中；分析冒泡排序的效率，容易看出，若初始序列為“正序”序列，則只進行一趟排序，在排序過程中進行n-1次關(guān)鍵字的比較，反之，則需進行n-1趟排序，總的時間復(fù)雜度為O（n*n），在該程序中，冒泡排序所花費的時間為4360，是所有排序中花費最多的，可見效率是很底的?？焖倥判蚴菍γ芭菖判虻囊环N改進，它所用的時間幾乎為0，交換的比較的次數(shù)都比較少；堆排序僅次于快速排序，花費的時間只有15ms。由以上討論可知，從時間上看，快速排序的平均性能都優(yōu)于

74、其他4種排序。</p><p><b>　　6 總 結(jié)</b></p><p>　　這次課程設(shè)計運用到了大學(xué)c++語言和大二所學(xué)習(xí)到的數(shù)據(jù)結(jié)構(gòu)知識點，課設(shè)題目要求不僅要求對課本知識有較深刻的了解，同時要求程序設(shè)計者有較強的思維和動手能力。這次課設(shè)使我了解我編程思想和編程技巧，也認識了軟件生命周期的各個環(huán)境，包括構(gòu)思、設(shè)計、編寫、調(diào)試、發(fā)布、文檔化、維護和修訂。編程的風(fēng)

75、格也很重要，同學(xué)只關(guān)心程序運行的結(jié)果，而對程序代碼的結(jié)構(gòu)的良好絲毫不在意。這是非常不可取的，如果我們希望將來從事編程工作，在這一點上該引起足夠的重視。這是嚴謹?shù)膽B(tài)度，很重要！</p><p>　　在寫程序的過程中遇到的麻煩不是很多，由于課本上都把最基本的算法寫的很清楚，我們只需要去理解，把分散的知識聚攏來，用學(xué)過的知識把一個一個的排序恰當?shù)倪B接起來就能把程序的主要部分寫好，再加一修改就可以了，而且在這一學(xué)期的學(xué)習(xí)

76、生活中，我們已經(jīng)把大多數(shù)的排序都寫好了，所以這對于我們來說還是比較輕松的一件事，但是在寫程序的過程中還是會遇到一些麻煩，那就需要我們的小心謹慎和積極探索的精神了，爭取把程序?qū)懙母昝馈?lt;/p><p>　　做課程設(shè)計不僅讓我修補了以前學(xué)習(xí)的漏洞，也讓我知道一個道理：編程需要興趣和實際動手。這應(yīng)該可以借鑒在老師的教學(xué)工作上。創(chuàng)新思維至關(guān)重要，這不僅能讓我們寫出精簡的代碼，也有助于開發(fā)出高效的程序。</p>