數(shù)據(jù)結(jié)構(gòu)-課件-8

1、第章 排序本章中主要介紹下列內(nèi)容： 插入排序 交換排序 選擇排序 基數(shù)排序退出18.1 基本概念8.2 插入排序8.3 交換排序8.4 選擇排序8.5 歸并排序8.6 基數(shù)排序28.1 基本概念 關(guān)鍵字 是數(shù)據(jù)元素中的某個(gè)數(shù)據(jù)項(xiàng)。如果某個(gè)數(shù)據(jù)項(xiàng)可以唯一地確定一個(gè)數(shù)據(jù)元素，就將其稱為主關(guān)鍵字；否則，稱為次關(guān)鍵字。 排序 是把一組無(wú)序地?cái)?shù)據(jù)元素按照關(guān)鍵字值遞增（或遞減）地重新排列。如果排序依據(jù)的是主關(guān)鍵字，排序的結(jié)果將是唯一的， 排序算法的穩(wěn)定性 如果在待排序的記錄序列中有多個(gè)數(shù)據(jù)元素的關(guān)鍵字值相同，經(jīng)過(guò)排序后，這些數(shù)據(jù)元素的相對(duì)次序保持不變，則稱這種排序算法是穩(wěn)定的，否則稱之為不穩(wěn)定的。3 內(nèi)部

2、排序與外部排序 根據(jù)在排序過(guò)程中待排序的所有數(shù)據(jù)元素是否全部被放置在內(nèi)存中，可將排序方法分為內(nèi)部排序和外部排序兩大類。內(nèi)部排序是指在排序的整個(gè)過(guò)程中，待排序的所有數(shù)據(jù)元素全部被放置在內(nèi)存中；外部排序是指由于待排序的數(shù)據(jù)元素個(gè)數(shù)太多，不能同時(shí)放置在內(nèi)存，而需要將一部分?jǐn)?shù)據(jù)元素放置在內(nèi)存，另一部分?jǐn)?shù)據(jù)元素放置在外設(shè)上，整個(gè)排序過(guò)程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。本章只討論常用的內(nèi)部排序方法。 排序的基本方法 內(nèi)部排序主要有5種方法：插入、交換、選擇、歸并和基數(shù)。 趟 在排序過(guò)程中，基本動(dòng)作執(zhí)行一次。4 排序算法的效率 評(píng)價(jià)排序算法的效率主要有兩點(diǎn)：一是在數(shù)據(jù)量規(guī)模一定的條件下，算法

3、執(zhí)行所消耗的平均時(shí)間，對(duì)于排序操作，時(shí)間主要消耗在關(guān)鍵字之間的比較和數(shù)據(jù)元素的移動(dòng)上，因此我們可以認(rèn)為高效率的排序算法應(yīng)該是盡可能少的比較次數(shù)和盡可能少的數(shù)據(jù)元素移動(dòng)次數(shù)；二是執(zhí)行算法所需要的輔助存儲(chǔ)空間，輔助存儲(chǔ)空間是指在數(shù)據(jù)量規(guī)模一定的條件下，除了存放待排序數(shù)據(jù)元素占用的存儲(chǔ)空間之外，執(zhí)行算法所需要的其他存儲(chǔ)空間，理想的空間效率是算法執(zhí)行期間所需要的輔助空間與待排序的數(shù)據(jù)量無(wú)關(guān)。5 待排序記錄序列的存儲(chǔ)結(jié)構(gòu) 待排序記錄序列可以用順序存儲(chǔ)結(jié)構(gòu)和和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。在本章的討論中（除基數(shù)排序外），我們將待排序的記錄序列用順序存儲(chǔ)結(jié)構(gòu)表示，即用一維數(shù)組實(shí)現(xiàn)。其定義如下所示：#define MAX

4、_NUM 80/待排序記錄序列中的最大數(shù)據(jù)元素個(gè)數(shù)typedef struct elemtype /待排序的數(shù)據(jù)元素類型 keytype key;/數(shù)據(jù)元素的關(guān)鍵字 anytype otheritem;/數(shù)據(jù)元素中的其他成份DataTypeMAX_NUM+1;68.2 插入排序 插入排序的主要思路是不斷地將待排序的數(shù)值插入到有序段中，使有序段逐漸擴(kuò)大，直至所有數(shù)值都進(jìn)入有序段中位置。 8.2.1 直接插入排序1. 直接插入排序的基本思想 7 直接插入排序是一種比較簡(jiǎn)單的排序方法。它的基本思想是依次將記錄序列中的每一個(gè)記錄插入到有序段中，使有序段的長(zhǎng)度不斷地?cái)U(kuò)大。其具體的排序過(guò)程可以描述如下：首

5、先將待排序記錄序列中的第一個(gè)記錄作為一個(gè)有序段，將記錄序列中的第二個(gè)記錄插入到上述有序段中形成由兩個(gè)記錄組成的有序段，再將記錄序列中的第三個(gè)記錄插入到這個(gè)有序段中，形成由三個(gè)記錄組成的有序段，依此類推，每一趟都是將一個(gè)記錄插入到前面的有序段中，假設(shè)當(dāng)前欲處理第i個(gè)記錄，則應(yīng)該將這個(gè)記錄插入到由前i-1個(gè)記錄組成的有序段中，從而形成一個(gè)由i個(gè)記錄組成的按關(guān)鍵字值排列的有序序列，直到所有記錄都插入到有序段中。一共需要經(jīng)過(guò)n-1趟就可以將初始序列的n個(gè)記錄重新排列成按關(guān)鍵字值大小排列的有序序列。82. 直接插入排序算法 將第i個(gè)記錄插入到由前面i-1個(gè)記錄構(gòu)成的有序段中主要有兩個(gè)步驟： 將待插入記錄

6、ai 保存在a0中，即a0=ai; 搜索插入位置：j=i-1; /j最初指示i的前一個(gè)位置while (a0.key aj.key) aj+1=aj; /后移關(guān)鍵字值大于a0.key的記錄 j=j-1; /將j指向前一個(gè)記錄，為下次比較做準(zhǔn)備aj+1=a0; /將a0放置在第j+1個(gè)位置上9完整的插入排序算法為：void insertsort (DataType a, int n) for (i=2; i=n; i+) /需要n-1趟 a0=ai; /將ai賦予監(jiān)視哨j=i-1;while (a0.keyaj.key) /搜索插入位置 aj+1=aj; j=j-1; aj+1=a0;/ 將原a

7、i中的記錄放入第j+1個(gè)位置10 直接插入排序算法簡(jiǎn)單、容易實(shí)現(xiàn)，只需要一個(gè)記錄大小的輔助空間用于存放待插入的記錄（在C語(yǔ)言中，我們利用了數(shù)組中的0單元）和兩個(gè)int型變量。當(dāng)待排序記錄較少時(shí)，排序速度較快，但是，當(dāng)待排序的記錄數(shù)量較大時(shí)，大量的比較和移動(dòng)操作將使直接插入排序算法的效率降低；然而，當(dāng)待排序的數(shù)據(jù)元素基本有序時(shí)，直接插入排序過(guò)程中的移動(dòng)次數(shù)大大減少，從而效率會(huì)有所提高。 插入排序是一種穩(wěn)定的排序方法。11 8.2.2 希爾排序1. 希爾排序的基本思想 希爾排序方法又稱為縮小增量排序，其基本思想是將待排序的記錄劃分成幾組，從而減少參與直接插入排序的數(shù)據(jù)量，當(dāng)經(jīng)過(guò)幾次分組排序后，記錄

8、的排列已經(jīng)基本有序，這個(gè)時(shí)候再對(duì)所有的記錄實(shí)施直接插入排序。12 具體步驟可以描述如下：假設(shè)待排序的記錄為n個(gè)，先取整數(shù)dn，例如，取d=n/2 （n/2 表示不大于n/2的最大整數(shù)），將所有距離為d的記錄構(gòu)成一組，從而將整個(gè)待排序記錄序列分割成為d個(gè)子序列，如圖8-2所示，對(duì)每個(gè)分組分別進(jìn)行直接插入排序，然后再縮小間隔d，例如，取d=d/2，重復(fù)上述的分組，再對(duì)每個(gè)分組分別進(jìn)行直接插入排序，直到最后取d=1，即將所有記錄放在一組進(jìn)行一次直接插入排序，最終將所有記錄重新排列成按關(guān)鍵字有序的序列。133. 希爾排序算法 (1) 分別讓每個(gè)記錄參與相應(yīng)分組中的排序 若分為d組，前d個(gè)記錄就應(yīng)該分別

9、構(gòu)成由一個(gè)記錄組成的有序段，從d+1個(gè)記錄開(kāi)始，逐一將每個(gè)記錄ai插入到相應(yīng)組中的有序段中，其算法可以這樣實(shí)現(xiàn)： for (i=d+1; i0 & a0.key=1;d=d/2) for(i=1+d;i0&a0.keyaj+1），則將其交換，最終達(dá)到有序化。其處理過(guò)程為：18 （1）將整個(gè)待排序的記錄序列劃分成有序區(qū)和無(wú)序區(qū)，初始狀態(tài)有序區(qū)為空，無(wú)序區(qū)包括所有待排序的記錄。 （2）對(duì)無(wú)序區(qū)從前向后依次將相鄰記錄的關(guān)鍵字進(jìn)行比較，若逆序?qū)⑵浣粨Q，從而使得關(guān)鍵字值小的記錄向上“飄浮”（左移），關(guān)鍵字值大的記錄好像石塊，向下“墮落”（右移）。 每經(jīng)過(guò)一趟冒泡排序，都使無(wú)序區(qū)中關(guān)鍵字值最大的記錄進(jìn)入有

10、序區(qū)，對(duì)于由n個(gè)記錄組成的記錄序列，最多經(jīng)過(guò)n-1趟冒泡排序，就可以將這n個(gè)記錄重新按關(guān)鍵字順序排列。193. 冒泡排序算法 原始的冒泡排序算法 對(duì)由n個(gè)記錄組成的記錄序列，最多經(jīng)過(guò)（n-1）趟冒泡排序，就可以使記錄序列成為有序序列，第一趟定位第n個(gè)記錄，此時(shí)有序區(qū)只有一個(gè)記錄；第二趟定位第n-1個(gè)記錄，此時(shí)有序區(qū)有兩個(gè)記錄；以此類推，算法框架為： for（i=n；i1；i-） 定位第i個(gè)記錄； 20 若定位第i個(gè)記錄，需要從前向后對(duì)無(wú)序區(qū)中的相鄰記錄進(jìn)行關(guān)鍵字的比較，它可以用如下所示的語(yǔ)句實(shí)現(xiàn)。for（j=1；ja.j+1.key） temp=aj；aj=aj+1；aj+1=temp； 21

11、下面給出完成的冒泡排序算法：void BubbleSort1 (DataType a,int n) for (i=n；i1；i-） for (j=1;ja.j+1.key） temp=aj；aj=aj+1；aj+1=temp； 22 改進(jìn)的冒泡排序算法 在冒泡排序過(guò)程中，一旦發(fā)現(xiàn)某一趟沒(méi)有進(jìn)行交換操作，就表明此時(shí)待排序記錄序列已經(jīng)成為有序序列，冒泡排序再進(jìn)行下去已經(jīng)沒(méi)有必要，應(yīng)立即結(jié)束排序過(guò)程。23改進(jìn)的冒泡排序算法：void BubbleSort2 (DataType a,int n)for (i=n;i1;i-) exchange=0；for (j=1;ja.j+1.key) temp=a

12、j；aj=aj+1；aj+1=temp； exchange=1； if (exchange=0) break；24 進(jìn)一步地改進(jìn)冒泡排序算法 在【算法8-4】給出的冒泡排序算法的基礎(chǔ)上，如果我們同時(shí)記錄第i趟冒泡排序中最后一次發(fā)生交換操作的位置m（m1;i-) exchange=0； m=last; /初始將最后進(jìn)行記錄交換的位置設(shè)置成i-1for (j=1;ja.j+1.key） temp=aj；aj=aj+1；aj+1=temp； exchange=1； last=j； /記錄每一次發(fā)生記錄交換的位置 if （exchange=0）break；26 冒泡排序比較簡(jiǎn)單，當(dāng)初始序列基本有序時(shí)，

13、冒泡排序有較高的效率，反之效率較低；其次冒泡排序只需要一個(gè)記錄的輔助空間，用來(lái)作為記錄交換的中間暫存單元；冒泡排序是一種穩(wěn)定的排序方法。27 8.3.2 快速排序 1. 快速排序的基本思想 快速排序又稱為分區(qū)交換排序。其基本思想是：首先將待排序記錄序列中的所有記錄作為當(dāng)前待排序區(qū)域，從中任選取一個(gè)記錄（比如，第一個(gè)記錄），并以該記錄的關(guān)鍵字值為基準(zhǔn)，從位于待排序記錄序列左右兩端開(kāi)始，逐漸向中間靠攏，交替與基準(zhǔn)記錄的關(guān)鍵字進(jìn)行比較、交換，每次比較，若遇左側(cè)記錄的關(guān)鍵字值大于基準(zhǔn)記錄的關(guān)鍵字，則將其與基準(zhǔn)記錄交換，使其移到基準(zhǔn)記錄的右側(cè)，若遇右側(cè)記錄的關(guān)鍵字值小于基準(zhǔn)值，則將其與基準(zhǔn)記錄交換，使其

14、移至基準(zhǔn)記錄的左側(cè)，28 最后讓基準(zhǔn)記錄到達(dá)它的最終位置，此時(shí)，基準(zhǔn)記錄將待排序記錄分成了左右兩個(gè)區(qū)域，位于基準(zhǔn)記錄左側(cè)的記錄都小于或等于基準(zhǔn)記錄的關(guān)鍵字，位于基準(zhǔn)記錄右側(cè)的所有記錄的關(guān)鍵字都大于或等于基準(zhǔn)記錄的關(guān)鍵字，這就是一趟快速排序；然后分別對(duì)左右兩個(gè)新的待排序區(qū)域，重復(fù)上述一趟快速排序的過(guò)程，其結(jié)果分別讓左右兩個(gè)區(qū)域中的基準(zhǔn)記錄都到達(dá)它們的最終位置，同時(shí)將待排序記錄序列分成更小的待排序區(qū)域，再次重復(fù)對(duì)每個(gè)區(qū)域進(jìn)行一趟快束排序，直到每個(gè)區(qū)域只有一個(gè)記錄為止，此時(shí)所有的記錄都到達(dá)了它的最終位置，即整個(gè)待排序記錄按關(guān)鍵值有序排列，至此排序結(jié)束。29 對(duì)待排序記錄序列進(jìn)行一趟快速排序的過(guò)程描述

15、如下： (1) 初始化：取第一個(gè)記錄作為基準(zhǔn)，其關(guān)鍵字值為19，設(shè)置兩個(gè)指針i，j分別用來(lái)指示將要與基準(zhǔn)記錄進(jìn)行比較的左側(cè)記錄位置和右側(cè)記錄位置。最開(kāi)始從右側(cè)開(kāi)始比較，當(dāng)發(fā)生交換操作后，轉(zhuǎn)去再?gòu)淖髠?cè)比較； (2) 用基準(zhǔn)記錄與右側(cè)記錄進(jìn)行比較：即與指針j指向的記錄進(jìn)行比較，如果右側(cè)記錄的關(guān)鍵字值大，則繼續(xù)與右側(cè)前一個(gè)記錄進(jìn)行比較，即j減1后，再用基準(zhǔn)元素與j指向的記錄比較，若右側(cè)的記錄小（逆序），則將基準(zhǔn)記錄與j指向的記錄進(jìn)行交換；30 (3) 用基準(zhǔn)元素與左側(cè)記錄進(jìn)行比較：即與指針i指向的記錄進(jìn)行比較，如果左側(cè)記錄的關(guān)鍵字值小，則繼續(xù)與左側(cè)后一個(gè)記錄進(jìn)行比較，即i加1后，再用基準(zhǔn)記錄與i指向

16、的記錄比較，若左側(cè)的記錄大（逆序），則將基準(zhǔn)記錄與i指向的記錄交換，； (4) 右側(cè)比較與左側(cè)比較交替重復(fù)進(jìn)行，直到指針i與j指向同一位置，即指向基準(zhǔn)記錄最終的位置。 一趟快速排序之后，再分別對(duì)左右兩個(gè)區(qū)域進(jìn)行快速排序，以此類推，直到每個(gè)分區(qū)域都只有一個(gè)記錄為止。下面是對(duì)關(guān)鍵字值為（19,6,47,26,18,26,7,13）的記錄序列進(jìn)行快速排序的各趟狀態(tài)313. 快速排序算法 快速排序是一個(gè)遞歸的過(guò)程，只要能夠?qū)崿F(xiàn)一趟快速排序的算法，就可以利用遞歸的方法對(duì)一趟快速排序后的左右分區(qū)域分別進(jìn)行快速排序。下面是一趟快速排序的算法分析： (1) 初始化： 將i 和j分別指向待排序區(qū)域的最左側(cè)記錄和

17、最右側(cè)記錄的位置。 i=first; j=end; 將基準(zhǔn)記錄暫存在temp中。 temp=ai;32 (2) 對(duì)當(dāng)前待排序區(qū)域從右側(cè)將要進(jìn)行比較的記錄（j指向的記錄）開(kāi)始向左側(cè)進(jìn)行掃描，直到找到第一個(gè)關(guān)鍵字值小于基準(zhǔn)記錄關(guān)鍵字值的記錄： while (ij & temp.key=aj) j-; (3) 如果i!=j，則將aj中的記錄移至ai，并將i+：ai=aj; i+; (4) 對(duì)當(dāng)前待排序區(qū)域從左側(cè)將要進(jìn)行比較的記錄（i指向的記錄）開(kāi)始向右側(cè)進(jìn)行掃描，直到找到第一個(gè)關(guān)鍵字值大于基準(zhǔn)記錄關(guān)鍵字的記錄： while (ij & ai=temp.key) i+;33 (5) 如果i!=j，則將

18、ai中的記錄移至aj，并將j+： aj=ai; j+; (6) 如果此時(shí)仍ij，則重復(fù)上述（2）、（3）、（4）、（5）操作，否則，表明找到了基準(zhǔn)記錄的最終位置，并將基準(zhǔn)記錄移到它的最終位置上：while （ij） 執(zhí)行(2)、(3)、(4)、(5) 步驟ai=temp; 下面是快速排序的完整算法。34void quicksort (DataType a,int first,int end ) i=first; j=end; temp=ai; /初始化 while(ij) while (ij & temp.key= aj.key) j-； ai=aj； 35 while (ij & ai.ke

19、y=temp.key) i+； aj=ai； ai=temp； if (firsti-1) quicksort(a, first, i-1)； /對(duì)左側(cè)分區(qū)域進(jìn)行快速排序 if (i+1end) quicksort(a, i+1, end)； /對(duì)右側(cè)分區(qū)域進(jìn)行快速排序36 快速排序?qū)嵸|(zhì)上是對(duì)冒泡排序的一種改進(jìn)，它的效率與冒泡排序相比有很大地提高。在冒泡排序過(guò)程中是對(duì)相鄰兩個(gè)記錄進(jìn)行關(guān)鍵字比較和互換的，這樣每次交換記錄后，只能改變一對(duì)逆序記錄，而快速排序則從待排序記錄的兩端開(kāi)始進(jìn)行比較和交換，并逐漸向中間靠攏，每經(jīng)過(guò)一次交換，有可能改變幾對(duì)逆序記錄，從而加快了排序速度。到目前為止快速排序是平均

20、速度最大的一種排序方法，但當(dāng)原始記錄排列基本有序或基本逆序時(shí)，每一趟的基準(zhǔn)記錄有可能只將其余記錄分成一部分，這樣就降低了時(shí)間效率，所以快速排序適用于原始記錄排列雜亂無(wú)章的情況。 快速排序是一種不穩(wěn)定的排序，在遞歸調(diào)用時(shí)需要占據(jù)一定的存儲(chǔ)空間用來(lái)保存每一層遞歸調(diào)用時(shí)的必要信息。378.4 選擇排序 選擇排序是指在排序過(guò)程序中，依次從待排序的記錄序列中選擇出關(guān)鍵字值最小的記錄、關(guān)鍵字值次小的記錄、，并分別將它們定位到序列左側(cè)的第1個(gè)位置、第二個(gè)位置、，最后剩下一個(gè)關(guān)鍵字值最大的記錄位于序列的最后一個(gè)位置，從而使待排序的記錄序列成為按關(guān)鍵字值由小到大排列的的有序序列。38 8.4.1 簡(jiǎn)單選擇排序1

21、. 簡(jiǎn)單選擇排序的基本思想 簡(jiǎn)單選擇排序的基本思想是：每一趟在n-i+1(i=1,2,3,.,n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i個(gè)記錄。它的具體實(shí)現(xiàn)過(guò)程為： (1) 將整個(gè)記錄序列劃分為有序區(qū)域和無(wú)序區(qū)域，有序區(qū)域位于最左端，無(wú)序區(qū)域位于右端，初始狀態(tài)有序區(qū)域?yàn)榭眨瑹o(wú)序區(qū)域含有待排序的所有n個(gè)記錄。39 (2) 設(shè)置一個(gè)整型變量index，用于記錄在一趟的比較過(guò)程中，當(dāng)前關(guān)鍵字值最小的記錄位置。開(kāi)始將它設(shè)定為當(dāng)前無(wú)序區(qū)域的第一個(gè)位置，即假設(shè)這個(gè)位置的關(guān)鍵字最小，然后用它與無(wú)序區(qū)域中其他記錄進(jìn)行比較，若發(fā)現(xiàn)有比它的關(guān)鍵字還小的記錄，就將index改為這個(gè)新的最小記錄位置，隨

22、后再用aindex.key 與后面的記錄進(jìn)行比較，并根據(jù)比較結(jié)果，隨時(shí)修改index的值，一趟結(jié)束后index中保留的就是本趟選擇的關(guān)鍵字最小的記錄位置。 (3) 將index位置的記錄交換到無(wú)序區(qū)域的第一個(gè)位置，使得有序區(qū)域擴(kuò)展了一個(gè)記錄，而無(wú)序區(qū)域減少了一個(gè)記錄。 不斷重復(fù) (2)、(3)，直到無(wú)序區(qū)域剩下一個(gè)記錄為止。此時(shí)所有的記錄已經(jīng)按關(guān)鍵字從小到大的順序排列就位。403. 簡(jiǎn)單選擇排序算法簡(jiǎn)單選擇排序的整體結(jié)構(gòu)應(yīng)該為：for (i=1;in;i) 第i趟簡(jiǎn)單選擇排序；41 下面我們進(jìn)一步分析一下“第i 趟簡(jiǎn)單選擇排序”的算法實(shí)現(xiàn)。 （1）初始化：假設(shè)無(wú)序區(qū)域中的第一個(gè)記錄為關(guān)鍵字值最

23、小的元素，即將index=i; （2）搜索無(wú)序區(qū)域中關(guān)鍵字值最小的記錄位置：for (j=i+1;j =n;j+)if (aj.keya.index.ke) index=j; （3）將無(wú)序區(qū)域中關(guān)鍵字最小的記錄與無(wú)序區(qū)域的第一個(gè)記錄進(jìn)行交換，使得有序區(qū)域由原來(lái)的i-1個(gè)記錄擴(kuò)展到i個(gè)記錄。42 完整算法：void selecsort ( DataType a, int n) for( i=1; in; i+) /對(duì)n個(gè)記錄進(jìn)行n-1趟的簡(jiǎn)單選擇排序 index=i; /初始化第i趟簡(jiǎn)單選擇排序的最小記錄指針 for (j=i+1;j=n;j+) /搜索關(guān)鍵字最小的記錄位置 if (aj.key

24、ai.key) index=j; if (index!=i) temp=ai; ai=aindex; aindex=temp; 43 簡(jiǎn)單選擇排序算法簡(jiǎn)單，但是速度較慢，并且是一種不穩(wěn)定的排序方法.，但在排序過(guò)程中只需要一個(gè)用來(lái)交換記錄的暫存單元。44 8.4.2 堆排序1. 堆排序的基本思想 堆排序是另一種基于選擇的排序方法。下面我們先介紹一下什么是堆？然后再介紹如何利用堆進(jìn)行排序。 堆定義：由n個(gè)元素組成的序列k1，k2，kn-1，kn，當(dāng)且僅當(dāng)滿足如下關(guān)系時(shí)，稱之為堆。45例如序列（47，35，27，26，18，7，13，19）滿足： 若將堆看成是一棵以k1為根的完全二叉樹(shù)，則這棵完全二

25、叉樹(shù)中的每個(gè)非終端結(jié)點(diǎn)的值均不大于（或不小于）其左、右孩子結(jié)點(diǎn)的值。由此可以看出，若一棵完全二叉樹(shù)是堆，則根結(jié)點(diǎn)一定是這n個(gè)結(jié)點(diǎn)中的最小者或最大者。下面給出兩個(gè)堆的示例。46圖 8-1147 下面我們討論一下如何利用堆進(jìn)行排序？ 從堆的定義可以看出，若將堆用一棵完全二叉樹(shù)表示，則根結(jié)點(diǎn)是當(dāng)前堆中所有結(jié)點(diǎn)的最小者（或最大者）。堆排序的基本思想是：首先將待排序的記錄序列構(gòu)造一個(gè)堆，此時(shí)，選出了堆中所有記錄的最小者或最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次?。ɑ虼未螅┑挠涗?，以此類推，直到堆中只有一個(gè)記錄為止，每個(gè)記錄出堆的順序就是一個(gè)有序序列。48 3. 堆排序算法 假

26、設(shè)當(dāng)前要進(jìn)行篩選的結(jié)點(diǎn)編號(hào)為k，堆中最后一個(gè)結(jié)點(diǎn)的編號(hào)為m，且ak+1至am之間的結(jié)點(diǎn)都已經(jīng)滿足堆的條件，則調(diào)整過(guò)程可以描述為： (1) 設(shè)置兩個(gè)指針i和j： i指向當(dāng)前（要篩選）的結(jié)點(diǎn)：i=k; j指向當(dāng)前結(jié)點(diǎn)的左孩子結(jié)點(diǎn)：j=2*i; (2) 比較當(dāng)前結(jié)點(diǎn)的左右孩子的關(guān)鍵字值，并用j指向關(guān)鍵字值較大的孩子結(jié)點(diǎn)。 if (jm & aj.keyaj.key) break; /結(jié)束篩選操作 else temp=ai; ai=aj; aj=temp; /交換結(jié)點(diǎn)內(nèi)容 i=j;j=2*i; /準(zhǔn)備繼續(xù)篩選 可以將交換改進(jìn)為：if (ai.keyaj.key) break; else ai=aj;

27、i=j; j=2*i; 50堆排序的篩選算法：void sift (DataType a,int k,int m) i=k;；j=2*i；temp=ai； while (j=m) / if ( j m & aj.key aj .key) break； else ai=aj ；i=j；j=2*i； ai = temp；51堆排序完整的算法。void heapsort (DataType a, int n) h=n/2 ; /最后一個(gè)非終端結(jié)點(diǎn)的編號(hào) for ( i=h ; i=1; i-) /初建堆。從最后一個(gè)非終端結(jié)點(diǎn)至根結(jié)點(diǎn) sift ( a, i, n ) ; for ( i=n ; i1

28、 ; i- ) /重復(fù)執(zhí)行移走堆頂結(jié)點(diǎn)及重建堆的操作 temp=a1 ; a1=ai; ai=temp ; sift ( a , 1 , i-1 ); 52 在堆排序中，除建初堆以外，其余調(diào)整堆的過(guò)程最多需要比較樹(shù)深次，因此，與簡(jiǎn)單選擇排序相比時(shí)間效率提高了很多；另外，不管原始記錄如何排列，堆排序的比較次數(shù)變化不大，所以說(shuō)，堆排序?qū)υ加涗浀呐帕袪顟B(tài)并不敏感。 在堆排序算法中只需要一個(gè)暫存被篩選記錄內(nèi)容的單元和兩個(gè)簡(jiǎn)單變量h和i，所以堆排序是一種速度快且省空間的排序方法。堆排序是一種不穩(wěn)定的。538.5 歸并排序 8.5.1 歸并排序的基本思想 歸并排序是一種另一類排序方法。所謂歸并是指將兩個(gè)

29、或兩個(gè)以上的有序表合并成一個(gè)新的有序表。歸并排序的基本思想是將一個(gè)具有n個(gè)待排序記錄的序列看成是n個(gè)長(zhǎng)度為1的有序列，然后進(jìn)行兩兩歸并，得到n/2 個(gè)長(zhǎng)度為2的有序序列，再進(jìn)行兩兩歸并，得到n/4 個(gè)長(zhǎng)度為4的有序序列，如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。54 8.5.3 歸并排序算法 通常，我們將兩個(gè)有序段合并成一個(gè)有序段的過(guò) 程稱為2-路歸并。 1.2-路歸并算法 假設(shè)記錄序列被存儲(chǔ)在一維數(shù)組a中，且asam 和am+1at 已經(jīng)分別有序，現(xiàn)將它們合并為一個(gè)有序段，并存入數(shù)組a1中的a1sa1t之間。 合并過(guò)程： (1) 設(shè)置三個(gè)整型變量k、i、j，用來(lái)分別指向a1s.t中當(dāng)前應(yīng)

30、該放置新記錄的位置，asam和am+1at中當(dāng)前正在處理的記錄位置。初始值應(yīng)該為：i=s; j=m+1; k=s;55 (2) 比較兩個(gè)有序段中當(dāng)前記錄的關(guān)鍵字，將關(guān)鍵字較小的記錄放置a1k，并修改該記錄所屬有序段的指針及a1中的指針k。重復(fù)執(zhí)行此過(guò)程直到其中的一個(gè)有序段內(nèi)容全部移至a1中為止，此時(shí)需要將另一個(gè)有序段中的所有剩余記錄移至a1中。其算法實(shí)現(xiàn)如下： while (i=m &j=t) if (ai.key=aj.key) a1k+=ai+; else a1k+=aj+; if (i=m) while (i=m) a1k+=ai+; else while (j=t) a1k+=aj+;

31、 562-路歸并的完整算法：void merge (DataType a,DataType a1,int s,int m,int t)/asm和am+1at已經(jīng)分別有序，將它們歸并至a1sa1t中 k=s; i=s; j=m+1; while(i=m & j=t) if (ai.key=aj.key) a1k+=ai+; else a1k+=aj+; if (i=m) /將剩余記錄復(fù)制到數(shù)組a1中 while ( i=m) a1k+=ai+; if (j=t) while (j=t) a1k+=aj+;572. 歸并排序的遞歸算法 歸并排序方法可以用遞歸的形式描述，即首先將待排序的記錄序列分為

32、左右兩個(gè)部分，并分別將這兩個(gè)部分用歸并方法進(jìn)行排序，然后調(diào)用2-路歸并算法，再將這兩個(gè)有序段合并成一個(gè)含有全部記錄的有序段。58遞歸算法：void mergesort (DataType a,DataType a1,int s,int t) if (s=t) a1s=as; else m= (s+t)/2; mergesort ( a, a2, s, m); mergesort (a, a2, m+1, t); merge (a2, a1, s, m, t); 59 2-路歸并排序的遞歸算法從程序的書(shū)寫(xiě)形式上看比較簡(jiǎn)單，但是在算法執(zhí)行時(shí)，需要占用較多的輔助存儲(chǔ)空間，即除了在遞歸調(diào)用時(shí)需要保存一

33、些必要的信息，在歸并過(guò)程中還需要與存放原始記錄序列同樣數(shù)量的存儲(chǔ)空間，以便存放歸并結(jié)果，但與快速排序及堆排序相比，它是一種穩(wěn)定的排序方法。608.6 基數(shù)排序 8.6.1 基數(shù)排序的基本思想 基數(shù)排序是一種基于多關(guān)鍵字的排序方法。1. 多關(guān)鍵字排序 【舉例】 將表8-1所示的學(xué)生成績(jī)單按數(shù)學(xué)成績(jī)的等級(jí)由高到低排序，數(shù)學(xué)成績(jī)相同的學(xué)生再按英語(yǔ)成績(jī)的高低等級(jí)排序。6162排序結(jié)果如表8-2所示。63 與前面幾節(jié)所講述的排序不同，在這個(gè)排序中，每個(gè)學(xué)生記錄最終的位置由兩個(gè)關(guān)鍵字決定。第1關(guān)鍵字為數(shù)學(xué)成績(jī)k1，第二個(gè)關(guān)鍵字為英語(yǔ)成績(jī)k2，則排序后每一個(gè)學(xué)生成績(jī)記錄的位置由關(guān)鍵字k1 k2決定，我們將它

34、稱之為復(fù)合關(guān)鍵字，即多關(guān)鍵字排序是按照復(fù)合關(guān)鍵字的大小排序。 現(xiàn)在我們討論一下多關(guān)鍵字排序的方法。下面我們以學(xué)生成績(jī)單為例，給出通常采用的兩種方法。第一種方法是先按數(shù)學(xué)等級(jí)由高到低將學(xué)生記錄分成A、B、C、D、E五個(gè)子序列，然后再分別對(duì)每個(gè)子序列按英語(yǔ)成績(jī)由高到低排序，這樣就會(huì)得到一個(gè)優(yōu)先按數(shù)學(xué)等級(jí)排序，在數(shù)學(xué)等級(jí)相同的情況下，再按英語(yǔ)等級(jí)排序；第二種方法是先將學(xué)生記錄按英語(yǔ)等級(jí)由高到低分成A、B、C、D、E 五個(gè)組：64表 8-365 然后按從左向右，從上向下的順序?qū)⑺鼈兪占饋?lái)得到關(guān)鍵字序列：AA，EA，AB，BB，CB，DB，BC，CD 再按數(shù)學(xué)成績(jī)由高到低分成A、B、C、D、E五個(gè)組：

35、 表 8-466 再按由高到低的順序?qū)⑺鼈兪占饋?lái)，得到關(guān)鍵字序列：AA，AB，BB，BC，CB，CD，DB，EA 可以看出，這個(gè)關(guān)鍵字序列已經(jīng)是有序的了。 在上述兩種基于多關(guān)鍵字的排序方法中，第一種方法是先按高位關(guān)鍵字進(jìn)行排序，被稱之為“最高位優(yōu)先”法，簡(jiǎn)稱MSD法；第二種方法是先按低位關(guān)鍵字排序，被稱之為“最低位優(yōu)先”法，簡(jiǎn)稱為L(zhǎng)SD。從上面的例子可以看出：在MSD法中，先按高位關(guān)鍵字將待排序數(shù)據(jù)分成子序列，然后再對(duì)各子序列按下一個(gè)關(guān)鍵字排序；而使用LSD法進(jìn)行排序時(shí)，對(duì)每個(gè)關(guān)鍵字都是將整個(gè)序列按關(guān)鍵字分組，然后按順序收集，顯然LSD法，操作比較簡(jiǎn)單。67 2. 基數(shù)排序 基數(shù)排序是借助于多關(guān)鍵字排序思想進(jìn)行排序的一種排序方法。該方法將排序關(guān)鍵字K看作是由多個(gè)關(guān)鍵字組成的組合關(guān)鍵字，即K=k1k2kd。每個(gè)關(guān)鍵字ki表示關(guān)鍵字的一位，其中k1為最高位，kd為最低位，d為關(guān)鍵字的位數(shù)。例如，對(duì)于關(guān)鍵字序列（101，203 567，231，478，352），可以將每個(gè)關(guān)鍵K看成由三個(gè)單關(guān)鍵字組成，即K= k1k2k3，每個(gè)關(guān)鍵字的取值范圍為0ki9，所以每個(gè)關(guān)鍵字可取值的數(shù)目為10，通常將關(guān)鍵字取值的數(shù)目稱為基數(shù)，