第10章排序110.1概述21.排序（Sorting）

將數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序（遞增或遞減）的序列的過程稱為排序。2.

排序過程中的兩種基本操作（1）比較兩個(gè)關(guān)鍵字值的大小。（2）根據(jù)比較結(jié)果，移動(dòng)記錄的位置。3.對關(guān)鍵字排序的三個(gè)原則（1）關(guān)鍵字值為數(shù)值型的，則按鍵值大小為依據(jù)。（2）關(guān)鍵字值為ASCII碼，則按鍵值的內(nèi)碼編排順序?yàn)橐罁?jù)。（3）關(guān)鍵字值為漢字字符串類型，則大多以漢字拼音的字典次序?yàn)橐罁?jù)。34.排序方法的穩(wěn)定和不穩(wěn)定若對任意的數(shù)據(jù)元素序列，使用某個(gè)排序方法按關(guān)鍵字進(jìn)行排序，對原先具有相同鍵值元素間的位置關(guān)系，若排序前與排序后保持一致，稱此排序方法是穩(wěn)定的；反之，則稱為不穩(wěn)定的。例：對數(shù)據(jù)鍵值為：5，3，8，3，6，6，排序。若排序后的序列為：3，3，5，6，6，8其相同鍵值的元素位置依舊是3在3前，6在6前，與排序前保持一致，則這種排序法是穩(wěn)定的。若排序后的序列為：3，3，5，6，6，8則這種排序法是不穩(wěn)定的。45．待排序記錄的三種存儲(chǔ)方式（1）待排序記錄存放在地址連續(xù)的一組存儲(chǔ)單元上。（2）待排序記錄存放在靜態(tài)鏈表中。（3）待排序記錄存放在一組地址連續(xù)的存儲(chǔ)單元，同時(shí)另設(shè)一個(gè)指示各個(gè)記錄存儲(chǔ)位置的地址向量，在排序過程中不移動(dòng)記錄本身，而移動(dòng)地址向量中這些記錄的“地址”，在排序結(jié)束后，再按照地址向量中的值調(diào)整記錄的存儲(chǔ)位置。6．內(nèi)排序整個(gè)排序過程都在內(nèi)存進(jìn)行的排序稱為內(nèi)排序。57．外排序待排序的數(shù)據(jù)元素量大，以致內(nèi)存一次不能容納全部記錄，在排序過程中需要對外存進(jìn)行訪問的排序稱為外排序。本章只討論內(nèi)排序。610.2插入排序7取要插入的元素，直接插在一個(gè)有序序列的合適位置。1.直接插入排序012362410612345基本思想：

直接插入排序是一種最簡單的排序方法，它的基本操作是將一個(gè)記錄插到已排序好的有序表中，從而得到一個(gè)新的，記錄數(shù)增1的有序表。整個(gè)排序過程為n-1趟插入，即先將序列中第

1

個(gè)記錄看成是一個(gè)有序子序列，然后從第

2

個(gè)記錄開始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序。8排序過程：將第一個(gè)元素r[1]作為已排序有序序列；其他元素r[2],r[3],r[4],r[5],...r[n]作為未排序序列；循環(huán)：從未排序序列中依次取一個(gè)元素；（循環(huán)從i=2,3,4,5...）取一個(gè)元素后進(jìn)行判斷：如果所取元素小于當(dāng)前有序序列的序尾，則：（1）將所取元素賦值給r[0]，r[0]

當(dāng)作哨兵。（2）循環(huán)：在當(dāng)前有序序列中尋找自己的位置，進(jìn)行插入：從當(dāng)前有序序列的序尾開始，倒著往前，將哨兵與相應(yīng)元素逐個(gè)比較：哨兵比當(dāng)前元素小，當(dāng)前元素就往后移一個(gè)位置；再往前比，若哨兵比當(dāng)前元素還小，當(dāng)前元素再往后移一個(gè)位置...直到哨兵大于等于當(dāng)前元素，循環(huán)結(jié)束，將哨兵插入到當(dāng)前元素的后面。如果所取元素大于等于有序序列的序尾，則保持原存儲(chǔ)位置不變。9e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。1、直接插入排序012362410612345362424i10e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。1、直接插入排序0123624106123453624i11e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。1、直接插入排序0123624106123453624i2412e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。1、直接插入排序0123624106123453610i241013e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。1、直接插入排序0123624106123453610i2414e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。1、直接插入排序0123624106123453610i2415e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。1、直接插入排序0123624106123453610i241016e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。1、直接插入排序01236241061234536246i10617e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。1、直接插入排序01236241061234536246i1018e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。1、直接插入排序01236241061234536246i1019e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。1、直接插入排序01236241061234536246i1020e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。1、直接插入排序01236241061234536246i10621e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。1、直接插入排序0123624106345362412i106121222e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。1、直接插入排序0123624106345362412i1061223e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。1、直接插入排序0123624106345362412i1061224e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。1、直接插入排序0123624106345362412i106121225算法：voidInsertsort(){for(i=2;i<=L;i++)//依次插入r[2],r[3],……r[n]{if(r[i].key<r[i-1].key){r[0]=r[i];//置監(jiān)視哨

j=i-1;while(r[0].key<r[j].key)

//查找r[i]的位置{r[j+1]=r[j];//向后移動(dòng)記錄

j--;}r[j+1]=r[0];//插入r[i]} }}26例49386597761327i=238(3849)6597761327i=3

(384965)97761327i=4

(38496597)761327i=576(3849657697)1327i=613(133849657697)27()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序結(jié)果：

01234567

27效率分析：

空間效率：僅用了一個(gè)輔助單元，輔助空間為O（1）。

時(shí)間效率：向有序表中逐個(gè)插入記錄的操作，進(jìn)行了n-1趟，每趟操作分為比較關(guān)鍵碼和移動(dòng)記錄，而比較的次數(shù)和移動(dòng)記錄的次數(shù)取決于待排序列按關(guān)鍵碼的初始排列。

最好情況下：即待排序列已按關(guān)鍵字有序，每趟操作只需1次比較2次移動(dòng)。

總比較次數(shù)=n-1次

總移動(dòng)次數(shù)=2(n-1)次最壞情況下：即第j趟操作，插入記錄需要同前面的j個(gè)記錄進(jìn)行j次關(guān)鍵碼比較，移動(dòng)記錄的次數(shù)為j+2次。28

平均情況下：即第j趟操作，插入記錄大約同前面的j/2個(gè)記錄進(jìn)行關(guān)鍵碼比較，移動(dòng)記錄的次數(shù)為j/2+2次。29

直接插入排序的時(shí)間復(fù)雜度為O(n2)，輔助空間為O（1）。

直接插入排序是穩(wěn)定的排序方法。直接插入排序最適合待排序關(guān)鍵字基本有序的序列。302.二分插入排序基本思想：

直接插入算法雖然簡單，但當(dāng)記錄數(shù)量n很大時(shí)，比較次數(shù)將大大增加，對于有序表（限于順序存儲(chǔ)結(jié)構(gòu)），為了減少關(guān)鍵字的比較次數(shù)，可采用二分插入排序。二分插入排序的基本思想是：用二分查找法在有序表中找到正確的插入位置，然后移動(dòng)記錄，空出插入位置，再進(jìn)行插入。3132例：若有8個(gè)記錄已排序，插入新的關(guān)鍵字為653

1234567860

87170275503512897908

low=1①②③high=8

m=(low+high)/2=(1+8)/2=4（1）取關(guān)鍵字653，與序列中間位置①的關(guān)鍵字比較，653>275，在后半?yún)^(qū)繼續(xù)找；（2）再與后半?yún)^(qū)中間位置②的關(guān)鍵字比較，653>512，再繼續(xù)在后半?yún)^(qū)找；（3）再與后半?yún)^(qū)中間位置③的關(guān)鍵字比較，653<897，經(jīng)三次比較找到插入位置③，然后插入653。算法：33voidBInsSort(){for(i=2;i<=n;i++){r[0]=r[i];//將r[i]暫存到r[0]

while(low<=high)//在r[low...high]中折半查找，確定所取元素在有序序列中的大致插入位置。當(dāng)low>high時(shí)，循環(huán)結(jié)束，大致插入位置已確定。{m=(low+high)/2; //折半

if(r[0].key<r[m].key)high=m-1;//確定新high，插入點(diǎn)在低半?yún)^(qū)：即：原low，新high之間

elselow=m+1;//確定新low，插入點(diǎn)在高半?yún)^(qū)：即：新low，原h(huán)igh之間}

for(j=i-1;j>=high+1;--j)r[j+1]=r[j];//記錄后移，直到空出r[high+1]為止

r[high+1]=r[0];}//插入}34

二分插入排序輔助空間和直接插入相同，為O

(1)。從時(shí)間上比較，二分插入僅減少了比較次數(shù)，而記錄的移動(dòng)次數(shù)不變，時(shí)間復(fù)雜度仍為O(n2)。

二分插入排序是穩(wěn)定的排序方法。353.希爾排序(Shell’sSort)

希爾排序又稱“縮小增量排序”，它也是一種插入排序方法，但在時(shí)間上較前兩種排序方法有較大的改進(jìn)。基本思想：先將整個(gè)待排序記錄序列分割成若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序時(shí)”，再對全體記錄進(jìn)行一次直接插入排序。36

特點(diǎn)：

子序列不是簡單的逐段分割，而是將相隔某個(gè)“增量”的記錄組成一個(gè)子序列，所以關(guān)鍵字較小的記錄不是一步一步地前移，而是跳躍式前移，從而使得在進(jìn)行最后一趟增量為1的插入排序時(shí)，序列已基本有序，只要做少量比較和移動(dòng)即可完成排序，時(shí)間復(fù)雜度較低。排序過程：先取一個(gè)正整數(shù)d1<n，把所有相隔

d1的記錄放一組，組內(nèi)進(jìn)行直接插入排序；然后取

d2<d1，重復(fù)上述分組和排序操作；直至di=1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹埂?7取d3=1三趟：1344838

274955659776三趟排序：當(dāng)d3=1時(shí),不再分組進(jìn)行直接插入排序4132738484955657697例初始：4938659776132748554一趟排序：13

27

48

55

4

49

38

65

97

76二趟排序：13

4

48

38

27

49

55

65

97

76取d1=5一趟分組：49

38

65

97

76

13

27

48

55

4取d2=3二趟分組：13

27

48

55

4

49

38

65

97

7638例4938659776132748554#defineT3intd[]={5,3,1};ji49133827一趟排序：1327485544938659776jiji274jiji55jijiji二趟排序：1344838274955659776jiji6548ji9755ji764123456789101234567891012345678910ji659755764938算法：39voidShellsort(){gap=n/2;//初次增量取序列元素個(gè)數(shù)n的一半為步長

while(gap>0){for(i=gap+1;i<=n;i++){j=i-gap;

while(j>0){if(r[j]>r[j+gap])//對子序列作直接插入排序{x=r[j];

r[j]=r[j+gap];

r[j+gap]=x;j=j-gap;}elsej=0;}}gap=gap/2;//每次減半,直至步長為1

}}40效率分析：希爾排序可提高排序速度：分組后n值減小，n2更小。在大量實(shí)驗(yàn)基礎(chǔ)上可推出：當(dāng)n在某個(gè)特定范圍內(nèi)希爾排序所需的比較和移動(dòng)次數(shù)約為n1.3,所以其平均時(shí)間復(fù)雜度約為O(n1.3)。其輔助空間為O(1)。

關(guān)鍵字較小的記錄跳躍式前移，在進(jìn)行最后一趟增量為

1

的插入排

序時(shí)，序列已基本有序。希爾排序?yàn)椴环€(wěn)定排序。

增量序列取法：沒有除1以外的公因子。最后一個(gè)增量值必須為1。4110.3快速排序法421.冒泡排序基本思想：冒泡法也稱沉底法，每相鄰兩個(gè)記錄關(guān)鍵字比大小，大的記錄往下沉（即較小的往上浮）。每一趟把最后一個(gè)下沉的位置記下，下一趟只需檢查比較到此為止；到所有記錄都不發(fā)生下沉?xí)r，整個(gè)過程結(jié)束。43排序過程：將第一個(gè)記錄的關(guān)鍵字與第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序r[1].key>r[2].key，則交換；然后比較第二個(gè)記錄與第三個(gè)記錄；依次類推，直至用n-1次比較完成n個(gè)記錄的第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個(gè)記錄上。

對前n-1個(gè)記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個(gè)記錄位置。

重復(fù)上述過程，直到“在一趟排序過程中沒有可進(jìn)行記錄交換的操作”為止。44例4938659776132730初始關(guān)鍵字3849657613273097第一趟38496513273076第二趟384913273065第三趟3813273049第四趟13273038第五趟384976971397279730971376767627301365276530651313494930492738273830381234567845算法：voidBubblesort(){for(i=1;i<L;i++)

for(j=1;j<=L-i;j++)if(R[j].key>R[j+1].key)//大則交換{R[0].key=R[j].key;

R[j].key=R[j+1].key;R[j+1].key=R[0].key;}}46效率分析：

空間效率：僅用了一個(gè)輔助單元，空間復(fù)雜度為O（1）。

時(shí)間效率：總共要進(jìn)行n-1趟冒泡，對j個(gè)記錄的表進(jìn)行一趟冒泡需要j-1次關(guān)鍵字的比較。移動(dòng)次數(shù)：最好情況下：待排序列已有序，不需移動(dòng)。最壞情況下：每次比較后均要進(jìn)行三次移動(dòng)。移動(dòng)次數(shù)=時(shí)間復(fù)雜度為:O（n2）

冒泡排序是一種穩(wěn)定排序。472.快速排序基本思想：就排序時(shí)間而言，快速排序被認(rèn)為是一種最好的內(nèi)部排序方法。通過一趟快速排序?qū)⒋判虻挠涗浄指畛瑟?dú)立的兩部分，其中前一部分記錄的關(guān)鍵字均比樞軸記錄的關(guān)鍵字小；后一部分記錄的關(guān)鍵字均比樞軸記錄的關(guān)鍵字大，樞軸記錄得到了它在整個(gè)序列中的最終位置并被存放好，這個(gè)過程稱為一趟快速排序。第二趟再分別對分割成兩部分子序列，再進(jìn)行快速排序，這兩部分子序列中的樞軸記錄也得到了最終在序列中的位置而被存放好，并且它們又分別分割出獨(dú)立的兩個(gè)子序列……。顯然，這是一個(gè)遞歸的過程，不斷進(jìn)行下去，直到每個(gè)待排序的子序列中只有一個(gè)記錄時(shí)為止，整個(gè)排序過程結(jié)束。快速排序是對冒泡排序的一種改進(jìn)。如何把一個(gè)記錄組分成兩個(gè)部分？通常是以序列中第一個(gè)記錄的關(guān)鍵字值作為樞軸記錄。48排序過程：對r[s……t]中記錄進(jìn)行一趟快速排序，附設(shè)兩個(gè)指針i和j，設(shè)樞軸記錄rp=r[s]，x=rp.key初始時(shí)令i=s,j=t

首先從

j所指位置向前搜索第一個(gè)關(guān)鍵字小于

x的記錄，并和

rp

交換；

再從

i所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于

x的記錄，和

rp

交換；

重復(fù)上述兩步，直至i==j為止

再分別對兩個(gè)子序列進(jìn)行快速排序，直到每個(gè)子序列只含有一個(gè)記錄為止。49例初始關(guān)鍵字：4938659776132750ijxji完成一趟排序：(273813)49(76976550)分別進(jìn)行快速排序：(13)

27

(38)49(5065)76(97)快速排序結(jié)束：13

27

3849

506576974927ijijij4965ji1349ij4997ij50算法：int

Partition(int

i,intj)//i、j為形參，分別代表low和high{RecTypepivot=R[i];

while(i<j)//從表的兩端交替地向中間掃描{while(i<j&&R[j].key>=pivot.key)j--;if(i<j)R[i++]=R[j];while(i<j&&R[i].key<=pivot.key) i++;51

if(i<j)

R[j--]=R[i];}

R[i]=pivot;returni;}

voidQuickSort(int

low,inthigh)//遞歸形式的快排序{int

pivotpos,k;if(low<high){pivotpos=Partition(low,high);

//調(diào)用Partition(low,high)函數(shù)

QuickSort(low,pivotpos-1);//對低子表遞歸排序

QuickSort(pivotpos+1,high);//對高子表遞歸排序}}52算法評價(jià)時(shí)間復(fù)雜度

最好情況（每次總是選到中間值作樞軸）T(n)=O(nlog2n)—經(jīng)驗(yàn)證明快速排序?yàn)橥瑪?shù)量級下平均性能最好的。

最壞情況（每次總是選到最小或最大元素作樞軸）--退化為冒泡排序T(n)=O(n2)。空間復(fù)雜度：需棧空間以實(shí)現(xiàn)遞歸最壞情況：S(n)=O(n)一般情況：S(n)=O(log2n)快速排序?yàn)椴环€(wěn)定排序。5310.4選擇排序541.簡單選擇排序基本思想：（1）初始狀態(tài)：整個(gè)數(shù)組r劃分成兩個(gè)部分，即有序區(qū)（初始為空）和無序區(qū)。（2）基本操作：從無序區(qū)中選擇關(guān)鍵字值最小的記錄，將其與無序區(qū)的第一個(gè)記錄交換（實(shí)質(zhì)是添加到有序區(qū)尾部）。從初態(tài)（有序區(qū)為空）開始，重復(fù)步驟（2），直到終態(tài)（無序區(qū)為空）。

55排序過程首先通過n-1次關(guān)鍵字比較，從

n個(gè)記錄中找出關(guān)鍵字最小的記錄，將它與第一個(gè)記錄交換；

再通過

n-2次比較，從剩余的

n-1個(gè)記錄中找出關(guān)鍵字次小的記錄，將它與第二個(gè)記錄交換；

重復(fù)上述操作，共進(jìn)行

n-1趟

排序后，排序結(jié)束。56例初始：[49386597761327]kjjjjjjkki=11349一趟：13[386597764927]i=2kkjjjjj2738二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：132738496576[97]排序結(jié)束：1327384965769757算法：

voidSelectsort(){for(i=1;i<n;i++){k=i;for(j=i+1;j<=n;j++)if(R[j].key<R[k].key)

//選擇關(guān)鍵字值最小的記錄

k=j;if(k!=i){R[0]=R[i];

R[i]=R[k];

R[k]=R[0];

}

//交換記錄

} }58效率分析：簡單選擇排序比較次數(shù)與關(guān)鍵字初始排序無關(guān)。找第一個(gè)最小記錄需進(jìn)行n-1次比較，找第二個(gè)最小記錄需要比較n-2次，找第i個(gè)最小記錄需要進(jìn)行n-i次比較，總的比較次數(shù)為：（n-1）+（n-2）+……+（n-i）+……2+1=n(n-1)/2=n2/2

時(shí)間復(fù)雜度：O(n2)

輔助空間：O（1）

簡單選擇排序是不穩(wěn)定的排序方法。592.堆排序

堆排序法是利用堆樹（HeapTree）來進(jìn)行排序的方法，堆樹是一種特殊的二叉樹，其具備以下特征：（1）是一棵完全二叉樹。（2）每一個(gè)根結(jié)點(diǎn)的值均大于或等于它的兩個(gè)子結(jié)點(diǎn)的值。（3）樹根的值是堆樹中最大的。2430533685479116圖(a)堆樹---大堆855330472436916圖(b)非堆樹60

基本思想：（1）把用數(shù)組存儲(chǔ)的待排序數(shù)據(jù)，轉(zhuǎn)換成一棵完全二叉樹。（2）將完全二叉樹轉(zhuǎn)換成堆樹。（3）有了堆樹后，便可以排序。

例：輸入數(shù)據(jù)序列為：801368827754269分析其堆排序的過程。61（1）畫出完全二叉樹位置（i）12345678

一維數(shù)組中的數(shù)據(jù)801368827754269對于任一位置，若父結(jié)點(diǎn)的位置為i，則它的兩個(gè)子結(jié)點(diǎn)分別位于2i和2i+1。根據(jù)數(shù)組中的數(shù)據(jù)可畫出如圖所示的完全二叉樹。88427527613806962（2）建堆過程

1)

從數(shù)組中間開始調(diào)整。

2)找出此父結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)的較大者，再與父結(jié)點(diǎn)比較，若父結(jié)點(diǎn)小，則交換。然后以交換后的子結(jié)點(diǎn)作為新的父結(jié)點(diǎn)，重復(fù)此步驟直到?jīng)]有子結(jié)點(diǎn)。

3)

把步驟2)中原來的父結(jié)點(diǎn)的位置往前推一個(gè)位置，作為新的父結(jié)點(diǎn)。重復(fù)步驟2)，直到樹根為止。63884275276138069884262775138069134262775888069694262775888013694262775808813建堆樹的過程圖建堆過程如圖所示：64(3)實(shí)現(xiàn)堆排序：堆排序：將無序序列建成一個(gè)堆，得到關(guān)鍵字最大（或最小）的記錄；輸出堆頂?shù)淖畲螅ㄐ。┲岛螅故Ｓ嗟膎-1個(gè)元素重又建成一個(gè)堆，則可得到

n個(gè)元素的次大（小）值；重復(fù)執(zhí)行，得到一個(gè)有序序列。

實(shí)現(xiàn)堆排序要解決的一個(gè)問題：即輸出堆頂元素后，怎樣調(diào)整剩余的n-1個(gè)元素，使其按關(guān)鍵碼成為一個(gè)新堆。65

調(diào)整方法：

設(shè)有m個(gè)元素的堆，輸出堆頂元素后，剩下m-1個(gè)元素。將堆底元素送入堆頂，堆被破壞，其原因僅是根結(jié)點(diǎn)不滿足堆的性質(zhì)。將根結(jié)點(diǎn)與左、右子女中較大的進(jìn)行交換。若與左子女交換，則左子樹堆被破壞，且僅左子樹的根結(jié)點(diǎn)不滿足堆的性質(zhì)；若與右子女交換，則右子樹堆被破壞，且僅右子樹的根結(jié)點(diǎn)不滿足堆的性質(zhì)。繼續(xù)對不滿足堆性質(zhì)的子樹進(jìn)行上述交換操作，直到葉子結(jié)點(diǎn)，堆被建成。稱這個(gè)自根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的調(diào)整過程為篩選。此過程的輸出序列為從大到小。其過程如圖所示：666942627751380134262775698013426277569806942627758013繼續(xù)相同步驟，最后只剩下樹根，完成整個(gè)堆排序過程。

(a)輸出堆頂后，將堆底13送入堆頂(b)堆被破壞，根結(jié)點(diǎn)與左子女交換(c)左子樹不滿足堆，其根與左孩子交換(d)堆已建成

67例：輸入數(shù)據(jù)序列為：13，38，27，50，76，65，49，97

分析其堆排序的過程。1327384965765097這也是一個(gè)堆樹，堆頂元素（完全二叉樹的根）為序列中n個(gè)元素的最小值----小堆根據(jù)給定的數(shù)據(jù)序列建立堆樹為：68調(diào)整方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過程為篩選。

此過程的輸出序列為從小到大。69例13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13273849502765769713輸出：13276549502738769713輸出：132738704965502738769713輸出：1327387665502738499713輸出：132738495065762738499713輸出：132738499765762738495013輸出：13273849506597762738495013輸出：13273849509765762738495013輸出：132738495065717665972738495013輸出：1327384950659765762738495013輸出：132738495065769765762738495013輸出：132738495065769772算法：voidHeapAdjust(S_TBL*h，int

s，intm){//a[s…m]中的記錄關(guān)鍵碼除a[s]外均滿足堆的定義，本函數(shù)將對第s個(gè)結(jié)點(diǎn)為根的子樹篩選，使其成為大頂堆

ac=h->a[s]；for(j=2*s；j<=m；j=j*2)//沿關(guān)鍵碼較大的子女結(jié)點(diǎn)向下篩選{if(j<m&&h->a[j].key<h->a[j+1].key)j=j+1； //為關(guān)鍵碼較大的元素下標(biāo)

if(ac.key<h->a[j].key)baeak；//ac應(yīng)插入在位置s上

h->a[s]=h->a[j]；s=j；//使s結(jié)點(diǎn)滿足堆定義}

h->a[s]=ac； //插入}73voidHeapSoat(S_TBL*h){for(i