單獨(dú)實(shí)現(xiàn)各種排序 課程設(shè)計(jì)報(bào)告

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)報(bào)告</p><p><b>　　課程設(shè)計(jì)題目</b></p><p>　　單獨(dú)實(shí)現(xiàn)各種排序 </p><p>　　2013 年 5 月 4 日</p><p><b>　　目錄</b></p><p><b>　　?

2、 目錄1</b></p><p><b>　　? 需求分析3</b></p><p><b>　　? 概要設(shè)計(jì)4</b></p><p>　　? 直接插入排序的設(shè)計(jì)思路4</p><p>　　? 折半插入排序的設(shè)計(jì)思路4</p><p>　　? 希爾排序

3、的設(shè)計(jì)思路5</p><p>　　? 冒泡排序設(shè)計(jì)思路5</p><p>　　? 快速排序設(shè)計(jì)思路5</p><p>　　? 直接選擇排序的設(shè)計(jì)思路6</p><p>　　? 堆排序的設(shè)計(jì)思路6</p><p>　　? 歸并排序的設(shè)計(jì)思路8</p><p>　　? 基數(shù)排序的設(shè)計(jì)思路

4、9</p><p><b>　　? 詳細(xì)設(shè)計(jì)11</b></p><p>　　? 直接插入排序11</p><p>　　? 折半插入排序12</p><p><b>　　? 希爾排序13</b></p><p><b>　　? 冒泡排序15</b&

5、gt;</p><p><b>　　? 快速排序16</b></p><p>　　? 直接選擇排序17</p><p><b>　　? 堆排序18</b></p><p><b>　　? 歸并排序20</b></p><p><b>　

6、　? 基數(shù)排序22</b></p><p><b>　　? 調(diào)試分析25</b></p><p>　　? 直接插入排序25</p><p>　　? 折半插入排序26</p><p><b>　　? 希爾排序27</b></p><p><b>

7、　　? 冒泡排序27</b></p><p><b>　　? 快速排序28</b></p><p>　　? 直接選擇排序28</p><p><b>　　? 堆排序29</b></p><p><b>　　? 歸并排序29</b></p>&

8、lt;p><b>　　? 基數(shù)排序30</b></p><p>　　? 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)總結(jié)31</p><p>　　? 課程設(shè)計(jì)的收獲31</p><p>　　? 遇到的問(wèn)題及解決思路32</p><p>　　? 對(duì)數(shù)據(jù)結(jié)構(gòu)課程的思考32</p><p><b>　　?

9、 參考文獻(xiàn)33</b></p><p><b>　　需求分析</b></p><p>　　排序時(shí)計(jì)算機(jī)程序設(shè)計(jì)中一種重要的操作，它的功能將包含多個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。</p><p>　　由于待排序的元素?cái)?shù)量不同，使得排序過(guò)程中的時(shí)空開(kāi)銷也不同。沒(méi)有一種排序算法可以適合任何一種場(chǎng)合，每種排序算法都

10、有適合的特殊環(huán)境，只有在這種特殊環(huán)境中才能發(fā)揮這種排序算法的優(yōu)勢(shì)。</p><p>　　排序在很多的場(chǎng)合都會(huì)用到，一個(gè)優(yōu)秀的排序算法可以使程序的運(yùn)行效率提高，節(jié)約時(shí)空資源。</p><p>　　其中對(duì)整數(shù)或者是實(shí)數(shù)的排序用得最多，大多數(shù)情況下都是要求對(duì)一組無(wú)序的數(shù)據(jù)按照數(shù)據(jù)值的大小以增序或者以降序排列數(shù)據(jù)。</p><p>　　例如對(duì)一組學(xué)生的成績(jī)從高到低排序，以確

11、定學(xué)生的名次。又如要求對(duì)員工的工資排序，以方便管理。在現(xiàn)實(shí)生活中要用到排序的地方不勝枚舉，雖然很多高級(jí)程序設(shè)計(jì)語(yǔ)言都封裝了排序的算法，用來(lái)也方便，程序員也容易掌握和運(yùn)用，但是這些封裝好了的排序算法將會(huì)一成不變的按照設(shè)計(jì)者當(dāng)初設(shè)計(jì)時(shí)設(shè)計(jì)的步驟工作，無(wú)法在實(shí)際情況中進(jìn)行優(yōu)化，也就不以利于提高程序的總體效率，所以根據(jù)實(shí)際的情況編寫(xiě)實(shí)際的排序算法才是可行的。</p><p>　　本次課程設(shè)計(jì)單獨(dú)實(shí)現(xiàn)直接插入排序、折半插入

12、排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序、基數(shù)排序。</p><p><b>　　概要設(shè)計(jì)</b></p><p>　　直接插入排序的設(shè)計(jì)思路</p><p>　　直接插入排序是一種最簡(jiǎn)單的排序方法，他的基本操作是將一個(gè)數(shù)據(jù)元素直接插入到已排好序的一組數(shù)據(jù)中，從而得到一個(gè)新的元素?cái)?shù)加一的有序表。</p>

13、<p>　　由于數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)采用的是數(shù)組，所以插入一個(gè)元素就涉及到查找待插入元素的位置，移動(dòng)其他元素，而數(shù)組頭一個(gè)結(jié)點(diǎn)設(shè)為哨兵結(jié)點(diǎn)。</p><p>　　如圖1所示：在序列1，3，5，8中插入4</p><p><b>　　圖1</b></p><p>　　這樣就有完成了一次插入，重復(fù)這種操作直到整個(gè)數(shù)組有序?yàn)橹埂?lt;/p>

14、<p>　　折半插入排序的設(shè)計(jì)思路</p><p>　　折半插入排序是在直接插入排序的基礎(chǔ)上減少了比較和移動(dòng)的次數(shù)從而提高算法的效率，因?yàn)榇迦霐?shù)據(jù)前面的所有數(shù)據(jù)已經(jīng)有序了。</p><p>　　先用兩個(gè)指針low和high通過(guò)折半查找的方法確定待插入數(shù)據(jù)的位置，最后low所指向的位置即為待插入數(shù)據(jù)的位置，先將把待查入數(shù)據(jù)放到0號(hào)單元然后low以后的單元依次后移一位然后將0號(hào)

15、單元的數(shù)據(jù)插入到low指向的單元中，重復(fù)這個(gè)操作直到整個(gè)數(shù)組有序。</p><p><b>　　希爾排序的設(shè)計(jì)思路</b></p><p>　　希爾排序的設(shè)計(jì)思想是：先將整個(gè)待排序數(shù)列分割成若干子序列，對(duì)子序列分別進(jìn)行直接插入排序，待整個(gè)序列基本有序時(shí)再對(duì)整個(gè)數(shù)列進(jìn)行一次直接插入排序。</p><p><b>　　冒泡排序設(shè)計(jì)思路&l

16、t;/b></p><p>　　冒泡排序很簡(jiǎn)單，首先將第一個(gè)數(shù)據(jù)的關(guān)鍵字和第二個(gè)數(shù)據(jù)的關(guān)鍵字比較，若為逆序，則將兩個(gè)數(shù)據(jù)交換，然后比較第二個(gè)和第三個(gè)數(shù)據(jù)的關(guān)鍵字，以此類推，直到第n-1個(gè)數(shù)據(jù)和第n個(gè)數(shù)據(jù)進(jìn)行比較。然后重復(fù)上述操作，第i次循環(huán)只進(jìn)行到第n-i個(gè)為止，因?yàn)閚-i以后的數(shù)據(jù)已經(jīng)有序了。</p><p><b>　　快速排序設(shè)計(jì)思路</b></p&

17、gt;<p>　　快速排序是對(duì)冒泡排序的一種改進(jìn)。它的基本思想是：通過(guò)一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，其中一部分關(guān)鍵字均比另一部分關(guān)鍵字小，然后分別對(duì)這兩部分繼續(xù)排序直到整個(gè)有序。</p><p><b>　　如圖2所示：</b></p><p>　　第一次找到3的位置3和6交換，1和4交換；</p><p>　　第二次找

18、到1的位置1和2交換，6的位置不變；</p><p>　　第三次找到4的位置4和5交換，至此整個(gè)序列有序。</p><p><b>　　圖2</b></p><p>　　直接選擇排序的設(shè)計(jì)思路</p><p>　　一趟直接選擇排序的操作為：通過(guò)n-i次關(guān)鍵字間的比較，從n-i+1個(gè)數(shù)據(jù)中選出關(guān)鍵字最小的數(shù)據(jù)，并和第i個(gè)數(shù)

19、據(jù)交換，重復(fù)n-1次就得到了一個(gè)有序的序列。</p><p><b>　　堆排序的設(shè)計(jì)思路</b></p><p>　　堆排序只需要一個(gè)數(shù)組就可以了，每個(gè)數(shù)據(jù)占一個(gè)存儲(chǔ)空間。堆的定義如下：對(duì)n個(gè)元素的序列{K1，K2，……，Kn}當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)稱之為堆：</p><p>　　Ki<=K2i&&Ki<=K2i+

20、1 或者 K2i<=Ki&&K2i+1<=Ki</p><p>　　前者稱為最小堆，后者稱為最大堆。</p><p>　　如圖3所示：對(duì)序列8 ， 1 ， 7 ， 4， 5 ，3建堆</p><p>　　如圖4.1-4.5所示排序過(guò)程：最終為1，3，4，5，7，8</p><p>　　圖3圖4.1

21、</p><p>　　圖4.2 圖4.3</p><p><b>　　圖4.4圖4.5</b></p><p><b>　　歸并排序的設(shè)計(jì)思路</b></p><p>　　假設(shè)初始序列為n個(gè)數(shù)據(jù)元素，則可以看成是n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度

22、為1，然后兩兩歸并，得到n/2個(gè)長(zhǎng)度為2或者為1的有序子序列，然后再兩兩歸并……直到得到一個(gè)長(zhǎng)度為n的有序序列為止。</p><p>　　這種排序稱為2路歸并排序。2路歸并排序的核心操作就是將兩個(gè)有序序列歸并為一個(gè)有序序列。</p><p><b>　　如圖5所示：</b></p><p><b>　　圖5</b><

23、/p><p>　　原始序列為4，1，5，3，2。</p><p>　　第一趟排序后將4，1合并，5，3合并后為1，4，3，5，2</p><p>　　第二趟合并后將1，4和3，5合并后為1，3，4，5，2</p><p>　　第三趟合并后將1，3，4，5和2合并為1，2，3，4，5。</p><p><b>　　

24、基數(shù)排序的設(shè)計(jì)思路</b></p><p>　　基數(shù)排序是借助“分配”和“收集”兩種操作對(duì)單邏輯關(guān)鍵字進(jìn)行排序。</p><p>　　例如關(guān)鍵字k是數(shù)字且在0到999之間，則可以把每個(gè)十進(jìn)制數(shù)字看成一個(gè)關(guān)鍵字，k由3個(gè)關(guān)鍵字（k1，k2，k3）組成，分別對(duì)應(yīng)k的百位，十位，個(gè)位數(shù)字。所以如果有一個(gè)這樣的數(shù)字序列，從低位關(guān)鍵字起按關(guān)鍵字的不同值將數(shù)據(jù)元素分配到0~9標(biāo)記的隊(duì)列中然

25、后在收集，如此重復(fù)3次即可。</p><p>　　基數(shù)的“基”就是每個(gè)關(guān)鍵字的取值范圍，這里是10。</p><p>　　假設(shè)每個(gè)關(guān)鍵字ki在[0，2]之間，則有三個(gè)隊(duì)列。</p><p>　　有序列：002，202，011，210，001，101</p><p>　　則排序過(guò)程如圖6.1~6.3所示：</p><p>

26、;<b>　　圖6.1</b></p><p>　　第一趟排序之后的序列為：（以個(gè)位數(shù)字為關(guān)鍵字）</p><p>　　210，011，001，101，002，202</p><p><b>　　圖6.2</b></p><p>　　第二趟排序之后序列為：（以十位數(shù)字為關(guān)鍵字）</p>

27、<p>　　001，101，002，202，210，011</p><p><b>　　圖6.3</b></p><p>　　第三趟排序之后序列為：（以百位數(shù)字為關(guān)鍵字）</p><p>　　001，002，011，101，202，210</p><p><b>　　詳細(xì)設(shè)計(jì)</b>&l

28、t;/p><p><b>　　直接插入排序</b></p><p>　　int * array代表待排序的數(shù)組，length代表待排序數(shù)組的長(zhǎng)度，array[0]設(shè)為監(jiān)視哨。</p><p>　　void InsertSort(int * array , int length)</p><p><b>　　{<

29、;/b></p><p>　　for(int i = 2 ; i <= length ; i++)</p><p><b>　　{</b></p><p>　　if(array[i] < array[i-1])</p><p><b>　　{</b></p><

30、p>　　array[0] = array[i];</p><p>　　array[i] = array[i-1];</p><p><b>　　int j;</b></p><p>　　//查找合適的位置并移動(dòng)數(shù)據(jù)</p><p>　　for(j = i-2 ; array[0] < array[j] ; j

31、--)</p><p>　　array[j+1] = array[j];</p><p>　　//在合適的位置插入數(shù)據(jù)</p><p>　　array[j+1] = array[0];</p><p><b>　　}</b></p><p><b>　　}</b></p

32、><p><b>　　}</b></p><p><b>　　折半插入排序</b></p><p>　　int * array代表待排序的數(shù)組，length代表待排序數(shù)組的長(zhǎng)度</p><p>　　void BInsertSort(int * array , int length)</p>

33、<p><b>　　{</b></p><p>　　for(int i = 2 ; i <= length ; i++)</p><p><b>　　{</b></p><p>　　array[0] = array[i];</p><p>　　int low = 1 , high

34、= i-1;</p><p>　　//折半查找插入的合適的位置</p><p>　　while(low <= high)</p><p><b>　　{</b></p><p>　　int mid = (low+high)/2;</p><p>　　if(array[0] < arra

35、y[mid])</p><p>　　high = mid-1;</p><p><b>　　else</b></p><p>　　low = mid+1;</p><p><b>　　}</b></p><p>　　//將low到i-1的數(shù)據(jù)向后移動(dòng)一位</p>

36、<p>　　for(int j = i-1 ; j >= low ; j--)</p><p>　　array[j+1] = array[j];</p><p>　　//low的位置即array[0]的正確位置</p><p>　　array[low] = array[0];</p><p><b>　　}<

37、/b></p><p><b>　　}</b></p><p><b>　　希爾排序</b></p><p>　　int * array代表待排序的數(shù)組，length代表待排序數(shù)組的長(zhǎng)度，increment代表增量</p><p>　　void ShellInsert(int * array

38、, int length , int increment)</p><p><b>　　{</b></p><p>　　//間隔為增量的子序列使用直接插入排序</p><p>　　for(int i = increment+1 ; i <= length ; i++)</p><p><b>　　{&l

39、t;/b></p><p>　　if(array[i] < array[i-increment])</p><p><b>　　{</b></p><p>　　array[0] = array[i];</p><p><b>　　int j;</b></p><p&g

40、t;　　for(j = i-increment ; j > 0 && array[0] < array[j] ;</p><p>　　j -= increment)</p><p>　　array[j+increment] = array[j];</p><p>　　array[j+increment] = array[0];</p

41、><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　//希爾排序主函數(shù)</b></p><p>　　void ShellSort(int *arr

42、ay , int length)</p><p><b>　　{</b></p><p><b>　　//增量</b></p><p>　　int increment = length/2;</p><p>　　while(increment>=1)</p><p>&

43、lt;b>　　{</b></p><p>　　ShellInsert(array , length , increment);</p><p>　　//逐步減小增量直至為1</p><p>　　increment /= 2;</p><p><b>　　}</b></p><p>

44、;<b>　　}</b></p><p><b>　　冒泡排序</b></p><p>　　int * array代表待排序的數(shù)組，length代表待排序數(shù)組的長(zhǎng)度</p><p>　　void BubbleSort(int * array , int length)</p><p><b&g

45、t;　　{</b></p><p>　　for(int i = length , change = true; i > 1 && change ; i--)</p><p><b>　　{</b></p><p>　　change = false;</p><p>　　for(int j

46、 = 1 ; j < i ; j++)</p><p><b>　　{</b></p><p>　　if(array[j]>array[j+1])</p><p><b>　　{</b></p><p>　　change = true;</p><p>　　swa

47、p(array[j] , array[j+1]);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>&l

48、t;b>　　快速排序</b></p><p>　　int * array代表待排序的數(shù)組，length代表待排序數(shù)組的長(zhǎng)度，將p到r之間比array[r]小的數(shù)據(jù)已到array[r]前，比array[r]大的移到后面，并返回array[r]的正確位置。</p><p>　　int Partition(int * array , int p , int r)</p&g

49、t;<p><b>　　{</b></p><p>　　int x = array[r];</p><p>　　//下標(biāo)小于等于i的數(shù)據(jù)都比x小，否則比x大</p><p>　　int i = p-1;</p><p>　　for(int j = p ; j < r ; j++)</p>

50、<p><b>　　{</b></p><p>　　if(array[j] <= x)</p><p><b>　　{</b></p><p><b>　　i++;</b></p><p>　　swap(array[i] , array[j]);</p&

51、gt;<p><b>　　}</b></p><p><b>　　}</b></p><p>　　swap(array[i+1] , array[r]);</p><p>　　//返回第一個(gè)比x大的位置，即arrray[r]的合適位置</p><p>　　return i+1;<

52、/p><p><b>　　}</b></p><p><b>　　//快速排序主函數(shù)</b></p><p>　　void QuickSort(int * array , int p , int r)</p><p><b>　　{</b></p><p>

53、<b>　　if(p < r)</b></p><p><b>　　{</b></p><p>　　int q = Partition(array , p , r);</p><p>　　QuickSort(array , p , q-1);</p><p>　　QuickSort(array

54、 , q+1 , r);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　直接選擇排序</b></p><p>　　int * array代表待排序的數(shù)組，length代表待排序數(shù)組的長(zhǎng)度，找到從bgn到length之

55、間最小的數(shù)據(jù)的位置</p><p>　　int SelectMinKey(int * array , int length , int bgn)</p><p><b>　　{</b></p><p>　　int min = array[bgn] , j = bgn;</p><p>　　for(int i = bgn+

56、1 ; i <= length ; i++)</p><p><b>　　{</b></p><p>　　if(min > array[i])</p><p><b>　　{</b></p><p>　　min = array[i];</p><p><b&

57、gt;　　j = i;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　return j;</b></p><p><b>　　}</b></p><p&g

58、t;<b>　　//選擇排序主函數(shù)</b></p><p>　　void SelectSort(int * array , int length)</p><p><b>　　{</b></p><p>　　for(int i = 1 ; i < length ; i++)</p><p>&

59、lt;b>　　{</b></p><p>　　int j = SelectMinKey(array , length , i);</p><p>　　//將最小的數(shù)據(jù)交換到位置i</p><p>　　if(i != j) swap(array[i] , array[j]);</p><p><b>　　}</

60、b></p><p><b>　　}</b></p><p><b>　　堆排序</b></p><p>　　int * array代表待排序的數(shù)組，heapLength代表堆的長(zhǎng)度，i代表第i個(gè)結(jié)點(diǎn)，保持最大堆的性質(zhì)</p><p>　　void MaxHeapify(int * array

61、 , int heapLength , int i)</p><p><b>　　{</b></p><p>　　int l = i*2;</p><p>　　int r = i*2+1;</p><p>　　//父結(jié)點(diǎn)和左右兒子中最大值的位置</p><p>　　int largest;<

62、/p><p>　　if(l <= heapLength && array[l] > array[i])</p><p>　　largest = l;</p><p><b>　　else</b></p><p>　　largest = i;</p><p>　　if(r &

63、lt;= heapLength && array[largest] < array[r])</p><p>　　largest = r;</p><p>　　//將最大值放到父結(jié)點(diǎn)，并繼續(xù)往下調(diào)整</p><p>　　if(largest != i)</p><p><b>　　{</b></

64、p><p>　　swap(array[i] , array[largest]);</p><p>　　MaxHeapify(array , heapLength , largest);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>

65、;<b>　　//建堆</b></p><p>　　void BuildMaxHeap(int * array , int heapLength)</p><p><b>　　{</b></p><p>　　for(int i = heapLength/2 ; i >= 1 ; i--)</p><

66、;p>　　MaxHeapify(array , heapLength , i);</p><p><b>　　}</b></p><p><b>　　//堆排序主函數(shù)</b></p><p>　　void HeapSort(int * array , int length)</p><p>&

67、lt;b>　　{</b></p><p>　　BuildMaxHeap(array , length);</p><p>　　int heapLength = length;</p><p>　　for(int i = length ; i >= 2 ; i--)</p><p><b>　　{</b&

68、gt;</p><p>　　//將堆頂?shù)臄?shù)據(jù)和堆最后個(gè)數(shù)據(jù)交換，堆頂?shù)臄?shù)據(jù)最大</p><p>　　swap(array[1] , array[heapLength]);</p><p><b>　　//堆的大小減一</b></p><p>　　heapLength--;</p><p>　　//

69、調(diào)整堆使之始終滿足最大堆的性質(zhì)</p><p>　　MaxHeapify(array , heapLength ,1);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　歸并排序</b></p><

70、p>　　將有序的ary1[i...m]和ary1[m+1,n]合并為有序的ary2[i...n]</p><p>　　void Merge(int * ary1 , int * ary2 , int i , int m , int n)</p><p><b>　　{</b></p><p>　　int j , k;</p>

71、<p>　　for(j = m+1 , k = i ; i <= m && j <= n ; k++)</p><p><b>　　{</b></p><p>　　if(ary1[i] < ary1[j])</p><p>　　ary2[k] = ary1[i++];</p><

72、p><b>　　else</b></p><p>　　ary2[k] = ary1[j++];</p><p><b>　　}</b></p><p>　　if(i <= m)</p><p><b>　　{</b></p><p>　　fo

73、r(; i <= m ; i++)</p><p>　　ary2[k++] = ary1[i];</p><p><b>　　}</b></p><p>　　if(j <= n)</p><p><b>　　{</b></p><p>　　for(; j <

74、= n ; j++)</p><p>　　ary2[k++] = ary1[j];</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//將arySource[s...t]歸并為有序的aryResult[s...t]</p><p

75、>　　void MergeSort(int * arySource , int * aryResult , int s , int t)</p><p><b>　　{</b></p><p>　　if(s == t)</p><p><b>　　{</b></p><p>　　aryResu

76、lt[s] = arySource[s];</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　int m = (s+t)/2 , aryTmp[9];</p><

77、;p>　　//將arySource[s...m]歸并為有序的aryTmp[s...m]</p><p>　　MergeSort(arySource , aryTmp , s , m);</p><p>　　//將arySource[m+1...t]歸并為有序的aryTmp[m+1...t]</p><p>　　MergeSort(arySource , ary

78、Tmp , m+1 , t);</p><p>　　//將aryTmp[s...m]，aryTmp[m+1...t]歸并為有序的aryResult[s...t]</p><p>　　Merge(aryTmp , aryResult , s , m , t);</p><p><b>　　}</b></p><p><

79、;b>　　}</b></p><p><b>　　基數(shù)排序</b></p><p>　　元素的存儲(chǔ)結(jié)構(gòu)，為方便計(jì)算將關(guān)鍵值設(shè)為string類型</p><p>　　struct Data</p><p><b>　　{</b></p><p>　　strin

80、g key;//數(shù)據(jù)的關(guān)鍵字</p><p>　　int next;//下一個(gè)數(shù)據(jù)的位置</p><p>　　} array[12];</p><p>　　//每個(gè)隊(duì)列的頭指針和為指針</p><p>　　int front[10] , trail[10];</p><p><b>　　//創(chuàng)建靜態(tài)鏈表<

81、;/b></p><p>　　void CreateLinkList(string key , int index , int pre)</p><p><b>　　{</b></p><p>　　array[pre].next = index;</p><p>　　array[index].key = key;&

82、lt;/p><p>　　array[index].next = 0;</p><p><b>　　}</b></p><p>　　//獲得數(shù)據(jù)的第i位數(shù)（將字符變?yōu)檎麛?shù)）</p><p>　　int order(int i , string key)</p><p><b>　　{</

83、b></p><p>　　return key[i]-'0';</p><p><b>　　}</b></p><p>　　分配函數(shù)，按數(shù)據(jù)的第i位關(guān)鍵字將數(shù)據(jù)放入相應(yīng)的隊(duì)列中</p><p>　　void Distribute(int i)</p><p><b>

84、;　　{</b></p><p>　　memset(front , 0 , sizeof(front));</p><p>　　for(int p = array[0].next ; p ; p = array[p].next)</p><p><b>　　{</b></p><p>　　int j = or

85、der(i , array[p].key);</p><p>　　if(!front[j])</p><p><b>　　{</b></p><p>　　front[j] = trail[j] = p;</p><p><b>　　}</b></p><p><b>

86、;　　else</b></p><p><b>　　{</b></p><p>　　array[trail[j]].next = p;</p><p>　　trail[j] = p;</p><p><b>　　}</b></p><p><b>　　}

87、</b></p><p><b>　　}</b></p><p>　　收集函數(shù)，合并各個(gè)隊(duì)列中的數(shù)據(jù)，順序從0號(hào)隊(duì)列到9號(hào)隊(duì)列</p><p>　　void Collect()</p><p><b>　　{</b></p><p>　　int i = 0;<

88、;/p><p>　　//找到第一個(gè)非空的隊(duì)列</p><p>　　while(i < 10 && !front[i]) i++;</p><p>　　array[0].next = front[i];</p><p>　　int tmp = trail[i];</p><p>　　for(i++; i

89、 < 10 ; i++)</p><p><b>　　{</b></p><p><b>　　//合并非空隊(duì)列</b></p><p>　　if(front[i])</p><p><b>　　{</b></p><p>　　array[tmp].

90、next = front[i];</p><p>　　tmp = trail[i];</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　array[tmp].next = 0;</p><p><b>　　}<

91、/b></p><p><b>　　//基數(shù)排序主函數(shù)</b></p><p>　　void RadixSort(int keyNum)</p><p><b>　　{</b></p><p>　　//從個(gè)位一直到最高位進(jìn)行分配和收集</p><p>　　for(int

92、 i = keyNum-1 ; i >= 0 ; i--)</p><p><b>　　{</b></p><p>　　Distribute(i);</p><p>　　Collect();</p><p><b>　　}</b></p><p><b>　　

93、}</b></p><p><b>　　調(diào)試分析</b></p><p><b>　　直接插入排序</b></p><p>　　輸入數(shù)據(jù)：49，38，65，97，76，13，27，49</p><p>　　正確結(jié)果：13，27，38，49，49，65，76，97</p>&

94、lt;p>　　本算法時(shí)間復(fù)雜度為：O(n^2)</p><p><b>　　運(yùn)行結(jié)果：</b></p><p><b>　　折半插入排序</b></p><p>　　輸入數(shù)據(jù)：49，38，65，97，76，13，27，49</p><p>　　正確結(jié)果：13，27，38，49，49，65，76

95、，97</p><p>　　本算法時(shí)間復(fù)雜度：O(n^2)</p><p><b>　　運(yùn)行結(jié)果：</b></p><p><b>　　希爾排序</b></p><p>　　輸入數(shù)據(jù)：49，38，65，97，76，13，27，49，55，04</p><p>　　正確結(jié)果：4

96、，13，27，38，49，49，55，65，76，97</p><p>　　時(shí)間復(fù)雜度：O(n^(3/2))</p><p><b>　　運(yùn)行結(jié)果：</b></p><p><b>　　冒泡排序</b></p><p>　　輸入數(shù)據(jù)：49，38，65，97，76，13，27，49</p>

97、<p>　　正確結(jié)果：13，27，38，49，49，65，76，97</p><p>　　時(shí)間復(fù)雜度：O(n^2)</p><p><b>　　運(yùn)行結(jié)果：</b></p><p><b>　　快速排序</b></p><p>　　輸入數(shù)據(jù)：49，38，65，97，76，13，27，49

98、</p><p>　　正確結(jié)果：13，27，38，49，49，65，76，97</p><p>　　時(shí)間復(fù)雜度：O(nlogn)</p><p><b>　　運(yùn)行結(jié)果：</b></p><p><b>　　直接選擇排序</b></p><p>　　輸入數(shù)據(jù)：49，38，65，

99、97，76，13，27，49</p><p>　　正確結(jié)果：13，27，38，49，49，65，76，97</p><p>　　時(shí)間復(fù)雜度：O(n^2)</p><p><b>　　運(yùn)行結(jié)果：</b></p><p><b>　　堆排序</b></p><p>　　輸入數(shù)據(jù)：

100、4，1，3，2，16，9，10，14，8，7</p><p>　　正確結(jié)果：1，2，3，4，7，8，9，10，14，16</p><p>　　時(shí)間復(fù)雜度：O(nlogn)</p><p><b>　　運(yùn)行結(jié)果：</b></p><p><b>　　歸并排序</b></p><p&

101、gt;　　輸入數(shù)據(jù)：49 38 65 97 76 13 27</p><p>　　正確結(jié)果：13 27 38 49 65 76 97</p><p>　　時(shí)間復(fù)雜度：O(nlogn)</p><p><b>　　運(yùn)行結(jié)果：</b></p><p>　　調(diào)試問(wèn)題思考和算法改進(jìn)：</p><p>　　

102、由于在歸并排序主函數(shù)中用了3個(gè)數(shù)組arySource，aryResult，aryTmp，開(kāi)始的時(shí)候aryTmp定義成全局變量結(jié)果程序老是運(yùn)行錯(cuò)誤，最后在每次遞歸調(diào)的用排序主函數(shù)本身時(shí)重新定義aryTmp，這樣問(wèn)題就解決了，因?yàn)槿謅ryTmp在遞歸調(diào)用的時(shí)候會(huì)把前面的結(jié)果覆蓋掉。但是如果在數(shù)據(jù)量小的時(shí)候這樣做還是可行的，如果一旦數(shù)據(jù)量非常大了遞歸調(diào)用會(huì)非常的耗時(shí)，而且每次遞歸調(diào)用都要臨時(shí)開(kāi)一個(gè)數(shù)組aryTmp這樣非常浪費(fèi)空間，一個(gè)好的改

103、進(jìn)思路就是把這個(gè)遞歸的算法該為非遞歸的。</p><p><b>　　基數(shù)排序</b></p><p>　　輸入數(shù)據(jù)：278，109，063，930，589，184，505，269，008，083</p><p>　　正確結(jié)果：008，063，083，109，184，269，278，505，589，930</p><p>

104、;<b>　　時(shí)間復(fù)雜度：</b></p><p>　　對(duì)于n個(gè)數(shù)據(jù)元素（假設(shè)每個(gè)數(shù)據(jù)元素含d個(gè)關(guān)鍵字，每個(gè)關(guān)鍵字的取值范圍為rd個(gè)值）進(jìn)行基數(shù)排序的時(shí)間復(fù)雜度為</p><p>　　O(d(n+rd))，其中每一趟分配的時(shí)間復(fù)雜度為O(n)，每一趟收集的時(shí)間復(fù)雜度為O(rd)，整個(gè)排序需進(jìn)行d趟分配和收集。</p><p><b>

105、　　運(yùn)行結(jié)果：</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)總結(jié)</p><p><b>　　課程設(shè)計(jì)的收獲</b></p><p>　　通過(guò)本次課程設(shè)計(jì)，我再次復(fù)習(xí)并掌握了各種排序算法，深刻的理解了數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的重要地位。學(xué)會(huì)了通過(guò)各種方法解決學(xué)習(xí)中遇到的問(wèn)題，懂得了與人合作的真諦，合作才能提高效率才能共贏。</p&

106、gt;<p>　　通過(guò)這次課程設(shè)計(jì)我初步理解了C/C++語(yǔ)言中排序庫(kù)函數(shù)的實(shí)現(xiàn)方法，它并不是傳說(shuō)中的那么神秘，它也是封裝了最基本的排序算法，然后提供一個(gè)接口給程序員調(diào)用。</p><p>　　通過(guò)本次課程設(shè)計(jì)還讓我認(rèn)識(shí)到了，要想編寫(xiě)一個(gè)高效率的算法學(xué)好數(shù)據(jù)結(jié)構(gòu)真的很重要。</p><p>　　遇到的問(wèn)題及解決思路</p><p>　　在編寫(xiě)程序的時(shí)候總

107、是犯一些低級(jí)的錯(cuò)誤，比如將“==”寫(xiě)成了“=”，然后程序老是出錯(cuò)，可是自己認(rèn)真的想一下思路覺(jué)得沒(méi)有問(wèn)題，當(dāng)別人檢查的時(shí)候一眼就瞧出來(lái)了。像這種情況就只有把常量放在左邊，這樣在編譯的時(shí)候都通不過(guò)，可直接通過(guò)編譯器查出。</p><p>　　比如我在寫(xiě)歸并排序的時(shí)候，程序偽代碼上直接寫(xiě)的三個(gè)數(shù)組，但是沒(méi)有說(shuō)數(shù)組是定義的全局變量還是局部變量，而我初步看了偽代碼之后就按照自己的思路寫(xiě)，可是老是得不到結(jié)果，最后調(diào)試了半天才

108、發(fā)現(xiàn)在Merge函數(shù)里面ary1的值和ary2的值相等，此時(shí)我才恍然大悟，由于是遞歸調(diào)用，這樣的話最后傳的參數(shù)ary1和ary2的值就是aryTmp。此時(shí)只要把a(bǔ)ryTmp定義成局部變量就可以了。</p><p>　　對(duì)數(shù)據(jù)結(jié)構(gòu)課程的思考</p><p>　　數(shù)據(jù)結(jié)構(gòu)課程對(duì)計(jì)算機(jī)專業(yè)來(lái)說(shuō)是核心課程了，如果沒(méi)有學(xué)數(shù)據(jù)結(jié)構(gòu)那么在面對(duì)問(wèn)題時(shí)，就很難想到好的解決思路。但是數(shù)據(jù)結(jié)構(gòu)書(shū)上講的算法有時(shí)很

109、晦澀，難懂，有時(shí)一個(gè)重要的步驟一句偽代碼就解決了但是實(shí)際編程時(shí)卻不好解決。有時(shí)只講一個(gè)算法的實(shí)現(xiàn)卻不講它的應(yīng)用，讓人感覺(jué)學(xué)了沒(méi)啥用處。</p><p>　　不過(guò)總的來(lái)講學(xué)了數(shù)據(jù)結(jié)構(gòu)后，我的編程能力和閱讀他人代碼的能力有了很大的提高。我想數(shù)據(jù)結(jié)構(gòu)這門(mén)課程雖然結(jié)束了，但真正學(xué)習(xí)它才剛剛開(kāi)始……</p><p><b>　　參考文獻(xiàn)</b></p><p