【文章內(nèi)容簡介】 9章 排 序 堆排序 除了簡單選擇排序之外 ， 還有樹形選擇排序 (錦標(biāo)賽排序 )，1964年威洛姆斯 ()提出了進(jìn)一步改進(jìn)的排序方法 ， 即堆排序 (heap sort)。 堆是 n個(gè)元素的有限序列 { K1,K2,…,K n }，它當(dāng)且僅當(dāng)滿足如下關(guān)系： ??? ????n / 2 ),1 ,2 ,(ikkkk12ii2ii ?第 9章 排 序 這是一個(gè)上小、底大的堆。若是一個(gè)上大、底小的堆，只需把“ ≤”改為“ ≥”即可。堆是一種數(shù)據(jù)元素之間的邏輯關(guān)系，常用向量做存儲(chǔ)結(jié)構(gòu)。對于第六章中介紹的滿二叉樹，當(dāng)對它的結(jié)點(diǎn)由上而下，自左至右編號(hào)之后，編號(hào)為 i的結(jié)點(diǎn)是編號(hào)為 2i和 2i+1結(jié)點(diǎn)的雙親。反過來講，結(jié)點(diǎn) 2i是結(jié)點(diǎn) i的左孩子，結(jié)點(diǎn) 2i+1是結(jié)點(diǎn) i的右孩子。圖 中的存儲(chǔ)狀態(tài)。結(jié)點(diǎn)編號(hào)對應(yīng)向量中的下標(biāo)號(hào)。 第 9章 排 序 1214 1516 18 17( a )5 642 3112 14 15 16 18 171 2 3 4 5 6( b )數(shù)據(jù)下標(biāo)圖 堆與完全二叉樹 第 9章 排 序 用堆的概念分析向量中的數(shù)據(jù)，它顯然滿足 (上小、底大 )堆的關(guān)系。不難看出，滿足堆的邏輯關(guān)系的一組數(shù)據(jù)，可畫成二叉樹的形狀，并且它是一棵完全二叉樹樹形。因此，也可借助完全二叉樹來描述堆的概念。若完全二叉樹中任一非葉子結(jié)點(diǎn)的值小于等于 (或大于等于 )其左、右孩子結(jié)點(diǎn)的值，則從根結(jié)點(diǎn)開始按結(jié)點(diǎn)編號(hào)排列所得的結(jié)點(diǎn)序列就是一個(gè)堆。在圖 (a)、 (c)是堆， (b)、 (d)不是堆。 第 9章 排 序 1219 6538 27 73( a )24 56 3( b )34 812( c )32 85( d )圖 堆與非堆 第 9章 排 序 堆排序的思路是：把 n個(gè)記錄存于向量 r之中 ， 把它看成完全二叉樹 ， 此時(shí)關(guān)鍵字序列不一定滿足堆的關(guān)系 。 堆排序大體分兩步處理 。 (1) 初建堆 。 從堆的定義出發(fā) ， 當(dāng) i=1,2,… ,n/2時(shí)應(yīng)滿足 ki≤k2i和ki≤k2i+1。 所以先取 i=n/2(它一定是第 n個(gè)結(jié)點(diǎn)雙親的編號(hào) )將以 i結(jié)點(diǎn)為根的子樹調(diào)整為堆；然后令 i=i1， 再將以 i結(jié)點(diǎn)為根的子樹調(diào)整為堆 。 此時(shí)可能會(huì)反復(fù)調(diào)整某些結(jié)點(diǎn) ， 直到 i=1為止 ， 堆初步建成 。 (2) 堆排序。首先輸出堆頂元素 (一般是最小值 )，讓堆中最后一個(gè)元素上移到原堆頂位置，然后恢復(fù)堆，因?yàn)榻?jīng)過上移堆頂元素的操作后，往往破壞了堆關(guān)系，所以要恢復(fù)堆；重復(fù)執(zhí)行輸出堆頂元素、堆尾元素上移和恢復(fù)堆的步驟，直到全部元素輸出完為止。 第 9章 排 序 例 設(shè)有 n個(gè)記錄 (n=8)的關(guān)鍵字是 {46， 55， 13， 42， 94，17， 5， 80}， 試對它們進(jìn)行堆排序 。 第一步：初建堆。因?yàn)?n=8，所以從 i=4開始，見圖 。 4642 94 17(b)138055 5 4294 17( c )1380546554294 17(d)468055513465594 17( a )1358042圖 初建堆 (a) i=4，不調(diào)整； i=3，調(diào)整； (b) i=2，調(diào)整； (c) i=1，調(diào)整； (d) 形成堆 第 9章 排 序 調(diào)整成為堆是一個(gè)較復(fù)雜的過程，當(dāng) i值確定之后用 kz記下ki的值，用 kz分別與 k2i和 k2i+1比較，可理解為 kz值與結(jié)點(diǎn) i的左、右孩子的關(guān)鍵字比較。如果一開始 kz比 k2i和 k2i+1均小，則不進(jìn)行任何調(diào)整。例如 i=4時(shí)， k4k8(4280)，就不用調(diào)整，見圖(a)。如果結(jié)點(diǎn) i的某一個(gè)孩子的關(guān)鍵字小于 kz，則把這個(gè)孩子結(jié)點(diǎn)移上來。如果結(jié)點(diǎn) i的兩個(gè)孩子的關(guān)鍵字都小于 kz，那么將兩個(gè)孩子中較小的一個(gè)調(diào)整上來。在圖 (c)中， i=1時(shí)， kk3都小于 kz(42， 546)，則讓 k3(即 5)移上去。此時(shí)需要讓 kz與更下一層的左、右孩子的關(guān)鍵字進(jìn)行比較，直到某一層的左、右孩子的關(guān)鍵字不小于 kz，或左、右孩子不存在為止。此時(shí)將kz填入適當(dāng)位置，使之成為堆，在圖 (c)中，先把 5調(diào)整上來，然后把 13移到 5原來的位置上，最后將 kz(即 46)填到 13原來的位置上。 第 9章 排 序 第二步：堆排序。這是一個(gè)反復(fù)輸出堆頂元素，將堆尾元素移至堆頂，再調(diào)整恢復(fù)堆的過程?；謴?fù)堆的過程與初建堆中 i=1時(shí)所進(jìn)行的操作完全相同。請注意：每輸出一次堆頂元素，堆頂與堆尾元素就交換一次，同時(shí)堆尾的邏輯位置退 1，直到堆中剩下一個(gè)元素為止。排序過程如圖 。 第 9章 排 序 4294 17 46135580( 1 ) 輸出 5 ， 80 移 上 來4294 80 461755134294 80175546( 2 ) 輸出 13 ， 46 移 上 來4294 804655175594464280( 3 ) 輸出 17 ， 80 移 上 來559446804255 468094( 4 ) 輸出 42 ， 94 移 上 來55 948046( 5 ) 輸出 46 ， 80 移 上 來55 948080 9455( 6 ) 輸出 55 ， 94 移 上 來8094 8094( 7 ) 輸出 80 ， 94 移 上 來94( 8 ) 輸出 94圖 堆排序的操作過程 第 9章 排 序 堆排序算法實(shí)現(xiàn)：由上述可知 ， 有一種操作過程 (即調(diào)整恢復(fù)堆 )要被多次反復(fù)調(diào)用 ， 那就是當(dāng) i值確定之后 ， 以 ki為比較參照值 ， 與它的左 、 右孩子的關(guān)鍵字比較和調(diào)整 ， 使得以結(jié)點(diǎn) i為根的子樹成為堆 ， 因此把這個(gè)過程設(shè)計(jì)成一個(gè)函數(shù)heap。 另外 ， 當(dāng)然還需再設(shè)計(jì)一個(gè)主體算法 ， 在初建堆階段 ，讓 i從 n/2變化到 1， 循環(huán)調(diào)用函數(shù) heap；在堆排序階段 ， 每輸出一次堆頂元素同時(shí)將堆尾元素與堆頂對換之后 ， 就調(diào)用一次 heap函數(shù)來恢復(fù)堆 。 主體算法由函數(shù) heapsort實(shí)現(xiàn) 。 以編號(hào)為 i的結(jié)點(diǎn)為根，調(diào)整為堆的算法為 第 9章 排 序 算法 void heap(node r[?],int i, int m) /*i是根結(jié)點(diǎn)編號(hào)， m是最后一個(gè)結(jié)點(diǎn)編號(hào) */ {x=r[i]。j=2*i。 /*x保存根記錄內(nèi)容， j為左孩子編號(hào) */ while (j=m) {if (jm) if (r[j].key)r[j+1].key) j++。 /*當(dāng)結(jié)點(diǎn) i有左、右兩個(gè)孩子時(shí)， j取關(guān)鍵字較小的孩子結(jié)點(diǎn)編號(hào) */ if (r[j].key) {r[i]=r[j]。i=j。 j=2*i。} /*向下一層探測 */ else j=m+1。 /* 、右孩子的關(guān)鍵字，強(qiáng)制使 jm，以便結(jié)束循環(huán) */ } r[i]=x。 }/*heap*/ 第 9章 排 序 算法 void heapsort(struct node r[MAXSIZE],int n) /*n為文件的實(shí)際記錄數(shù) ,r[0]沒有使用 */ {for (i=n/2。i=1。i) heap(r,i,n)。 /*初建堆 */ for (v=n。v=2。v) {printf(%5d,r[1].key)。 /*輸出堆頂元素 */ x=r[1]。 r[1]=r[v]。 r[v]=x。 /*堆頂堆尾元素交換 */ heap(r,1,v1)。 /*本次比上次少處理一個(gè)記錄 */ } printf(%5d,r[1].key)。 }/*heapsort*/ 第 9章 排 序 在堆排序圖示中，堆越畫越小，實(shí)際上，在 r向量中堆頂元素輸出之后并未刪除，而是與堆尾元素對換。由圖 輸出的是一個(gè)由小到大的升序序列，而最后 r向量記錄的關(guān)鍵字從 r[1].key到 r[n].key是一個(gè)由大到小的降序序列。堆排序中heap算法的時(shí)間復(fù)雜度與堆所對應(yīng)的完全二叉樹的樹高度 lbn相關(guān)。而 heapsort中對 heap的調(diào)用數(shù)量級(jí)為 n，所以堆排序的整個(gè)時(shí)間復(fù)雜度為 O(nlbn)。在內(nèi)存空間占用方面，基本沒有外增的輔助空間，僅有一個(gè) x。現(xiàn)在來分析堆排序的穩(wěn)定性問題。設(shè)有一組關(guān)鍵字： {6， 7， 51， 2， 52， 8}，經(jīng)排序后的結(jié)果是：{2， 52， 51， 6， 7， 8}。本來 51在前面，排序后 52移到 51的前面，所以說堆排序是不穩(wěn)定的。堆排序的部分處理過程如圖。 第 9章 排 序 65 2 8725 15 2 8762 5 126 875 15 2圖 堆排序的不穩(wěn)定分析 第 9章 排 序 歸 并 排 序 歸并排序 (merge sort)是一類與插入排序 、 交換排序 、 選擇排序不同的另一種排序方法 。 歸并的含義是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表 。 歸并排序有多路歸并排序 、 兩路歸并排序；可用于內(nèi)排序 ， 也可以用于外排序 。 這里僅對內(nèi)排序的兩路歸并方法進(jìn)行討論 。 兩路歸并排序算法思路： (1) 把 n個(gè)記錄看成 n個(gè)長度為 L的有序子表； (2) 進(jìn)行兩兩歸并使記錄關(guān)鍵字有序 ， 得到 n/2個(gè)長度為 2的有序子表； (3) 重復(fù)第 (2)步直到所有記錄歸并成一個(gè)長度為 n的有序表為止。 第 9章 排 序 例 有一組關(guān)鍵字 {4,7,5,3,2,8,6,1}， n=8，將其按由小到大的順序排序。 兩路歸并排序操作過程如圖 ，其中 L為子表長度。 圖 兩路歸并示例 初 始第 一 趟[ 4 ] [ 7 ] [ 5 ] [ 3 ] [ 2 ] [ 8 ] [ 6 ] [ 1 ] L ＝ 1[4 7] [3 5] [2 8] [1 6] L ＝ 2第 二 趟 4 5 7] [1 2 6 8] L ＝ 4[3第 三 趟 [1 2 3 4 5 6 7 8] L ＝ n第 9章 排 序 算法實(shí)現(xiàn)：此算法的實(shí)現(xiàn)不像圖示那樣簡單，現(xiàn)分三步來討論。首先從宏觀上分析，首先讓子表表長 L=1進(jìn)行處理；不斷地使 L=2*L，進(jìn)行子表處理，直到 L≥n為止，把這一過程寫成一個(gè)主體框架函數(shù) mergesort。然后對于某確定的子表表長 L，將 n個(gè)記錄分成若干組子表，兩兩歸并，這里顯然要循環(huán)若干次，把這一步寫成一個(gè)函數(shù) mergepass，可由 mergesort調(diào)用。最后再看每一組 (一對 )子表的歸并，其原理是相同的，只是子表表長不同，換句話說，是子表的首記錄號(hào)與尾記錄號(hào)不同，把這個(gè)歸并操作作為核心算法寫成函數(shù) merge，由 mergepass來調(diào)用。 第 9章 排 序 主體框架算法描述如下： 算法 void mergesort(node r[?],int n) /*r是包含有 n個(gè)記錄的原文件，歸并過程中另需一個(gè) r2作為輔助存儲(chǔ)空間 */ {l=1。 /*子表初始長度 */ while (ln) { mergepass(r,r2,l,n)。l=l*2。 /*r向量歸并排序到 r2向量中，子表長度加倍 */ mergepass(r2,r,l,n)。l=l*2。 /*再把 r2向量歸并排序送回 r向量中 */ } }/* mergesort*/ /*最后有序表存在于 r向量之中 */ 第 9章 排 序 算法 void mergepass(node r[?],struct r2[?],int l,int n) /*l為子表的長度 ， n為待排序的記錄總數(shù) */ { i=1。 /*從第一個(gè)記錄開始 */ while ((ni+1)=2*l) { /*剩下的記錄數(shù)目大于兩個(gè)子表長度時(shí) */ h1=i。 mid=h1+l1。h2=i+2*l1。 merge(r,r2,h1,mid,h2)。 i=i+2*l。 /*跳過兩個(gè)子