數(shù)據(jù)結(jié)構(gòu)-清華大學(xué)嚴(yán)蔚敏PPT - 副本 (10)

1、 采用的是以采用的是以 “玩橋牌者玩橋牌者”的方法為基礎(chǔ)的的方法為基礎(chǔ)的。即在。即在 考察記錄考察記錄Ri之前之前，設(shè)以前的所有記錄，設(shè)以前的所有記錄R1, R2 ,., Ri-1已已 排好序，然后將排好序，然后將Ri插入到已排好序的諸記錄的適當(dāng)位置插入到已排好序的諸記錄的適當(dāng)位置 。 最基本的插入排序是最基本的插入排序是直接插入排序直接插入排序(Straight Insertion Sort) 。 1 排序思想排序思想 將待排序的記錄將待排序的記錄Ri，插入到已排好序的記錄表，插入到已排好序的記錄表R1, R2 ,., Ri-1中，得到一個(gè)新的、記錄數(shù)增加中，得到一個(gè)新的、記錄數(shù)增加1的有序

2、表的有序表 。 直到所有的記錄都插入完為止直到所有的記錄都插入完為止。 設(shè)設(shè)待排序的記錄順序存放在數(shù)組待排序的記錄順序存放在數(shù)組R1n中，在排中，在排 序的某一時(shí)刻，將記錄序列分成兩部分：序的某一時(shí)刻，將記錄序列分成兩部分： R1i-1：已排好序的有序部分；：已排好序的有序部分； Rin：未排好序的無序部分。：未排好序的無序部分。 顯然，在剛開始排序時(shí)，顯然，在剛開始排序時(shí)，R1是已經(jīng)排好序的。是已經(jīng)排好序的。 例例：設(shè)有關(guān)鍵字序列為：設(shè)有關(guān)鍵字序列為：7, 4, -2, 19, 13, 6，直接插，直接插 入排序的過程如下圖入排序的過程如下圖10-1所示：所示： 初始記錄的關(guān)鍵字：初始記錄的

3、關(guān)鍵字： 7 4 -2 19 13 6 第一趟排序：第一趟排序： 4 7 -2 19 13 6 第二趟排序：第二趟排序： -2 4 7 19 13 6 第三趟排序：第三趟排序： -2 4 7 19 13 6 第四趟排序：第四趟排序： -2 4 7 13 19 6 第五趟排序：第五趟排序： -2 4 6 7 13 19 圖圖10-1 直接插入排序的過程直接插入排序的過程 2 算法實(shí)現(xiàn)算法實(shí)現(xiàn) void straight_insert_sort(Sqlist *L) int i, j ; for (i=2; ilength; i+) L-R0=L-Ri; j=i-1; /* 設(shè)置哨兵設(shè)置哨兵 */

4、 while( LT(L-R0.key, L-Rj.key) ) L-Rj+1=L-Rj; j-; /* 查找插入位置查找插入位置 */ L-Rj+1=L-R0; /* 插入到相應(yīng)位置插入到相應(yīng)位置 */ 3 算法說明算法說明 算法中的算法中的R0開始時(shí)并不存放任何待排序的記錄，開始時(shí)并不存放任何待排序的記錄， 引入的作用主要有兩個(gè)：引入的作用主要有兩個(gè)： 不需要增加輔助空間：不需要增加輔助空間： 保存當(dāng)前待插入的記錄保存當(dāng)前待插入的記錄 Ri，Ri會(huì)因?yàn)橛涗浀暮笠贫徽加?；?huì)因?yàn)橛涗浀暮笠贫徽加茫?保證查找插入位置的內(nèi)循環(huán)總可以在超出循環(huán)邊保證查找插入位置的內(nèi)循環(huán)總可以在超出循環(huán)邊 界之前

5、找到一個(gè)等于當(dāng)前記錄的記錄，起界之前找到一個(gè)等于當(dāng)前記錄的記錄，起“哨兵監(jiān)哨兵監(jiān) 視視”作用，避免在內(nèi)循環(huán)中每次都要判斷作用，避免在內(nèi)循環(huán)中每次都要判斷j是否越界是否越界 。 4 算法分析算法分析 最好情況最好情況：若待排序記錄按關(guān)鍵字從小到大排若待排序記錄按關(guān)鍵字從小到大排 列列( (正序正序) )，算法中的內(nèi)循環(huán)無須執(zhí)行，則一趟排序，算法中的內(nèi)循環(huán)無須執(zhí)行，則一趟排序 時(shí)：關(guān)鍵字比較次數(shù)時(shí)：關(guān)鍵字比較次數(shù)1次，記錄移動(dòng)次數(shù)次，記錄移動(dòng)次數(shù)2次次 (RiR0, R0Rj+1)。 則整個(gè)排序的關(guān)鍵字比較次數(shù)和記錄移動(dòng)次數(shù)分則整個(gè)排序的關(guān)鍵字比較次數(shù)和記錄移動(dòng)次數(shù)分 別是：別是： 比較次數(shù)比較次

6、數(shù)：1=n-1 n i=2 移動(dòng)次數(shù)移動(dòng)次數(shù)： 2=2(n-1) n i=2 最壞情況最壞情況：若待排序記錄按關(guān)鍵字從大到小排若待排序記錄按關(guān)鍵字從大到小排 列列( (逆序逆序) )，則一趟排序時(shí)：算法中的內(nèi)循環(huán)體執(zhí)行，則一趟排序時(shí)：算法中的內(nèi)循環(huán)體執(zhí)行i- 1，關(guān)鍵字比較次數(shù)，關(guān)鍵字比較次數(shù)i次，記錄移動(dòng)次數(shù)次，記錄移動(dòng)次數(shù)i+1。 則就整個(gè)排序而言：則就整個(gè)排序而言： 比較次數(shù)比較次數(shù)： i= n i=2 (n-1)(n+1) 2 移動(dòng)次數(shù)移動(dòng)次數(shù)：(i+1)= n i=2 (n-1)(n+4) 2 一般地一般地，認(rèn)為，認(rèn)為待排序的記錄可能出現(xiàn)的各種排列的待排序的記錄可能出現(xiàn)的各種排列的

7、概率相同概率相同，則取以上兩種情況的平均值，作為排序的，則取以上兩種情況的平均值，作為排序的關(guān)關(guān) 鍵字比較次數(shù)和記錄移動(dòng)次數(shù)鍵字比較次數(shù)和記錄移動(dòng)次數(shù)，約為約為n2/4，則復(fù)雜度為，則復(fù)雜度為 O(n2) 。 從時(shí)間上比較從時(shí)間上比較，折半插入排序僅僅減少了關(guān)鍵字的，折半插入排序僅僅減少了關(guān)鍵字的 比較次數(shù)比較次數(shù)，卻沒有減少，卻沒有減少記錄的移動(dòng)次數(shù)記錄的移動(dòng)次數(shù)，故時(shí)間故時(shí)間復(fù)雜度復(fù)雜度 仍然為仍然為O(n2) 。 排序示例排序示例 設(shè)有一組關(guān)鍵字設(shè)有一組關(guān)鍵字30, 13, 70, 85, 39, 42, 6, 20，采用折，采用折 半插入排序方法排序的過程如圖半插入排序方法排序的過程如

8、圖10-2所示：所示： i=1 (30) 13 70 85 39 42 6 20 i=2 13 (13 30) 70 85 39 42 6 20 i=7 6 (6 13 30 39 42 70 85) 20 i=8 20 (6 13 30 39 42 70 85) 20 low high mid i=8 20 (6 13 30 39 42 70 85) 20 low high mid i=8 20 (6 13 30 39 42 70 85) 20 mid highlow i=8 20 (6 13 20 30 39 42 70 85) 圖圖10-2 折半插入排序過程折半插入排序過程 27 76d

9、 49 first first first firstfinal final final final 65 38 97 97 13 13 圖圖10-3 2-路插入排序過程路插入排序過程 例：例：設(shè)有關(guān)鍵字集合設(shè)有關(guān)鍵字集合49, 38, 65, 97, 76, 13, 27, 49 ，采，采 用表插入排序的過程如下圖用表插入排序的過程如下圖10-4所示所示。 0 1 2 3 4 5 6 7 8 key域域 next域域 MAXINT 49 38 65 13 97 27 76 49 1 0 - - - - - - - i=2 MAXINT 49 38 65 13 97 27 76 49 2 0

10、1 - - - - - - i=3 MAXINT 49 38 65 13 97 27 76 49 2 3 1 0 - - - - - i=4 MAXINT 49 38 65 13 97 27 76 49 4 3 1 0 2 - - - - i=5 MAXINT 49 38 65 13 97 27 76 49 4 3 1 5 2 0 - - - 和直接插入排序相比，不同的是修改和直接插入排序相比，不同的是修改2n次指針值以次指針值以 代替移動(dòng)記錄，而關(guān)鍵字的比較次數(shù)相同，故時(shí)間復(fù)雜代替移動(dòng)記錄，而關(guān)鍵字的比較次數(shù)相同，故時(shí)間復(fù)雜 度為度為O(n2)。 表表插入排序得到一個(gè)有序鏈表，對(duì)其可以方便地

11、進(jìn)插入排序得到一個(gè)有序鏈表，對(duì)其可以方便地進(jìn) 行順序查找，但不能實(shí)現(xiàn)隨即查找行順序查找，但不能實(shí)現(xiàn)隨即查找。根據(jù)需要，可以對(duì)根據(jù)需要，可以對(duì) 記錄進(jìn)行重排，記錄重排詳見記錄進(jìn)行重排，記錄重排詳見P268。 i=6 MAXINT 49 38 65 13 97 27 76 49 4 3 1 5 6 0 2 - - i=7 MAXINT 49 38 65 13 97 27 76 49 4 3 1 7 6 0 2 5 - i=8 MAXINT 49 38 65 13 97 27 76 49 4 8 1 7 6 0 2 5 3 圖圖10-4 表插入排序過程表插入排序過程 9 7 1 2 5 13 13

12、8 15 11第一趟排序后第一趟排序后: 2 5 1 9 7 13 11 8 15 13第二趟排序后第二趟排序后: 1 2 5 7 8 9 11 13 13 15第三趟排序后第三趟排序后: 圖圖10-5 希爾排序過程希爾排序過程 9 13 8 2 5 13 7 1 15 11 713 18 初始關(guān)鍵字序列初始關(guān)鍵字序列: 第一趟排序過程第一趟排序過程: 3 算法實(shí)現(xiàn)算法實(shí)現(xiàn) 先給出一趟希爾排序的算法，類似直接插入排序先給出一趟希爾排序的算法，類似直接插入排序。 void shell_pass(Sqlist *L, int d) /* 對(duì)順序表對(duì)順序表L進(jìn)行一趟希爾排序進(jìn)行一趟希爾排序, 增量為

13、增量為d */ int j, k ; for (j=d+1; jlength; j+) L-R0=L-Rj ; /* 設(shè)置監(jiān)視哨兵設(shè)置監(jiān)視哨兵 */ k=j-d ; while (k0 k=k-d ; L-Rk+j=L-R0 ; 然后在根據(jù)增量數(shù)組然后在根據(jù)增量數(shù)組dk進(jìn)行希爾排序進(jìn)行希爾排序。 void shell_sort(Sqlist *L, int dk, int t) /* 按增量序列按增量序列dk0 t-1,對(duì)順序表對(duì)順序表L進(jìn)行希爾排序進(jìn)行希爾排序 */ int m ; for (m=0; m=t; m+) shll_pass(L, dkm) ; 希爾排序的分析比較復(fù)雜，涉及一些

14、數(shù)學(xué)上的問題，希爾排序的分析比較復(fù)雜，涉及一些數(shù)學(xué)上的問題， 其時(shí)間是所取的其時(shí)間是所取的“增量增量”序列的函數(shù)序列的函數(shù)。 希爾排序特點(diǎn)希爾排序特點(diǎn) 子序列的構(gòu)成不是簡(jiǎn)單的子序列的構(gòu)成不是簡(jiǎn)單的“逐段分割逐段分割”，而是將相，而是將相 隔某個(gè)增量的記錄組成一個(gè)子序列隔某個(gè)增量的記錄組成一個(gè)子序列。 希爾排序可提高排序速度，原因是：希爾排序可提高排序速度，原因是： 分組后分組后n值減小，值減小，n更小，而更小，而T(n)=O(n),所以所以T(n) 從總體上看是減小了從總體上看是減小了； 關(guān)鍵字較小的記錄跳躍式前移，在進(jìn)行最后一趟關(guān)鍵字較小的記錄跳躍式前移，在進(jìn)行最后一趟 增量增量為為1的插入

15、排序時(shí)，序列已基本有序。的插入排序時(shí)，序列已基本有序。 增量序列取法增量序列取法 無除無除1以外的公因子；以外的公因子； 最后一個(gè)增量值必須為最后一個(gè)增量值必須為1。 圖圖10-6 冒泡排序過程冒泡排序過程 23 38 22 45 23 67 31 15 41初始關(guān)鍵字序列初始關(guān)鍵字序列: 第一趟排序后第一趟排序后:23 22 38 23 45 31 15 41 67 第二趟排序后第二趟排序后:22 23 23 38 31 15 41 45 67 第三趟排序后第三趟排序后:22 23 23 31 15 38 41 45 67 第四趟排序后第四趟排序后:22 23 23 15 31 38 41

16、45 67 第五趟排序后第五趟排序后:22 23 15 23 31 38 41 45 67 第六趟排序后第六趟排序后:22 15 23 23 31 38 41 45 67 第七趟排序后第七趟排序后:15 22 23 23 31 38 41 45 67 void Bubble_Sort(Sqlist *L) int j ,k , flag ; for (j=0; jlength; j+) /* 共有共有n-1趟排序趟排序 */ flag=TRUE ; for (k=1; klength-j; k+) /* 一趟排序一趟排序 */ if (LT(L-Rk+1.key, L-Rk.key ) ) f

17、lag=FALSE ; L-R0=L-Rk ; L-Rk=L-Rk+1 ; L-Rk+1=L-R0 ; if (flag=TRUE) break ; 4 算法分析算法分析 時(shí)間復(fù)雜度時(shí)間復(fù)雜度 最好情況最好情況(正序正序)：比較次數(shù)：比較次數(shù)：n-1；移動(dòng)次數(shù)：；移動(dòng)次數(shù)：0； 最壞情況最壞情況(逆序逆序)： 比較次數(shù)比較次數(shù)： (n-i)= n-1 i=1 n(n-1) 2 移動(dòng)次數(shù)移動(dòng)次數(shù)： 3(n-i)= n-1 i=1 3n(n-1) 2 int i=low, j=high ; 圖圖10-7 一趟快速排序過程一趟快速排序過程 j前移前移2個(gè)位置后個(gè)位置后, Rj放放Ri的位置的位置:

18、29 23 38 22 45 67 31 ij 初始關(guān)鍵字序列初始關(guān)鍵字序列:29 29 38 22 45 23 67 31 ij 0 29 23 22 45 38 67 31 ij i后移后移1個(gè)位置后個(gè)位置后, Ri放放Rj的位置的位置: 29 23 22 45 38 67 31 ij j前移前移2個(gè)位置后個(gè)位置后, Rj放放Ri的位置的位置: 29 23 22 29 45 38 67 31 i j i后前移后前移1個(gè)位置后個(gè)位置后, i和和j的位置重合的位置重合: low=stacktop- ; high=stacktop- ; hn+2hC(n/2h) ，當(dāng)，當(dāng)n/2h=1時(shí)排序結(jié)時(shí)排

19、序結(jié) 束。束。 比較次數(shù)比較次數(shù)： (n-i)= n-1 i=1 n(n-1) 2 即即C(n)=O(n2) k) Tavg(n)=nC+ Tavg(k-1)+Tavg(n-k) n k=0 1 n =nC+ Tavg(k) n-1 k=0 2 n Tavg(n)=(n-1)C+ Tavg(k) n-2 k=0 2 n nTavg(n)-(n-1)Tavg(n-1)=(2n-1)C+2Tavg(n-1) ，即即 Tavg(n)=(n+1)/nTavg(n-1)+(2n-1)/nC (n+1)/nTavg(n-1)+2C (n+1)/nn/(n-1)Tavg(n-2)+2C+2C =(n+1)/

20、(n-1)Tavg(n-2)+2(n+1)1/n+1/(n+1)C Tavg(1)+2(n+1)C 2 n+1 3 1 4 1 + 1 n+1n 1 + Tavg(n) 只有只有1個(gè)記錄的排序時(shí)間是個(gè)記錄的排序時(shí)間是一個(gè)常數(shù)一個(gè)常數(shù)， 快速排序的平均時(shí)間復(fù)雜度是快速排序的平均時(shí)間復(fù)雜度是：T(n)=O(n2n) 從所需要的附加空間來看，快速排序算法是遞歸調(diào)從所需要的附加空間來看，快速排序算法是遞歸調(diào) 用，系統(tǒng)內(nèi)用堆棧保存遞歸參數(shù)，當(dāng)每次劃分比較均勻用，系統(tǒng)內(nèi)用堆棧保存遞歸參數(shù)，當(dāng)每次劃分比較均勻 時(shí)，棧的最大深度為時(shí)，棧的最大深度為2n+1 。 快速排序的空間復(fù)雜度是：快速排序的空間復(fù)雜度是：

21、S(n)=O(2n) 從排序的穩(wěn)定性來看，快速排序是從排序的穩(wěn)定性來看，快速排序是不穩(wěn)定不穩(wěn)定的。的。 選擇排序選擇排序(Selection Sort)的基本思想是：每次的基本思想是：每次 從當(dāng)前從當(dāng)前待排序的記錄待排序的記錄中選取關(guān)鍵字最小的記錄表，然后中選取關(guān)鍵字最小的記錄表，然后 與與待排序的記錄序列待排序的記錄序列中的第一個(gè)記錄進(jìn)行交換，直到整中的第一個(gè)記錄進(jìn)行交換，直到整 個(gè)記錄序列有序?yàn)橹箓€(gè)記錄序列有序?yàn)橹埂?簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序(Simple Selection Sort ，又稱為，又稱為直直 接選擇排序接選擇排序)的基本操作是：通過的基本操作是：通過n-i次關(guān)鍵字間的比較次

22、關(guān)鍵字間的比較 ，從，從n-i+1個(gè)記錄中選取關(guān)鍵字最小的記錄，然后和第個(gè)記錄中選取關(guān)鍵字最小的記錄，然后和第i 個(gè)記錄進(jìn)行交換，個(gè)記錄進(jìn)行交換，i=1, 2, n-1 。 1 排序示例排序示例 例：例：設(shè)有關(guān)鍵字序列為：設(shè)有關(guān)鍵字序列為：7, 4, -2, 19, 13, 6，直接選，直接選 擇排序的過程如下圖擇排序的過程如下圖10-8所示。所示。 圖圖10-8 直接選擇排序的過程直接選擇排序的過程 初始記錄的關(guān)鍵字：初始記錄的關(guān)鍵字： 7 4 -2 19 13 6 第一趟排序：第一趟排序：-2 4 7 19 13 6 第二趟排序：第二趟排序： -2 4 7 19 13 6 第三趟排序：第三

23、趟排序： -2 4 6 19 13 7 第四趟排序：第四趟排序： -2 4 6 7 13 19 第五趟排序：第五趟排序： -2 4 6 7 13 19 第六趟排序：第六趟排序： -2 4 6 7 13 19 2 算法實(shí)現(xiàn)算法實(shí)現(xiàn) void simple_selection_sort(Sqlist *L) int m, n , k; for (m=1; mlength; m+) k=m ; for (n=m+1; nlength; n+) if ( LT(L-Rn.key, L-Rk.key) ) k=n ; if (k!=m) /* 記錄交換記錄交換 */ L-R0=L-Rm; L-Rm=L-

24、Rk; L-Rk=L-R0; 3 算法分析算法分析 整個(gè)算法是二重循環(huán)整個(gè)算法是二重循環(huán)：外循環(huán)控制排序的趟數(shù)，對(duì)：外循環(huán)控制排序的趟數(shù)，對(duì) n個(gè)記錄進(jìn)行排序的趟數(shù)為個(gè)記錄進(jìn)行排序的趟數(shù)為n-1趟；內(nèi)循環(huán)控制每一趟的趟；內(nèi)循環(huán)控制每一趟的 排序排序。 進(jìn)行第進(jìn)行第i趟排序時(shí)趟排序時(shí)，關(guān)鍵字的比較次數(shù)為，關(guān)鍵字的比較次數(shù)為n-i，則：，則： 比較次數(shù)比較次數(shù)： (n-i)= n-1 i=1 n(n-1) 2 時(shí)間復(fù)雜度時(shí)間復(fù)雜度是是：T(n)=O(n2) 空間復(fù)雜度是空間復(fù)雜度是：S(n)=O(1) 從排序的穩(wěn)定性來看從排序的穩(wěn)定性來看，直接選擇排序是直接選擇排序是不穩(wěn)定不穩(wěn)定的。的。 輸出最小

25、關(guān)鍵字后輸出最小關(guān)鍵字后，根據(jù)，根據(jù)關(guān)系的可傳遞性關(guān)系的可傳遞性，欲選取，欲選取 次小關(guān)鍵字，只需將葉子結(jié)點(diǎn)中的最小關(guān)鍵字改為次小關(guān)鍵字，只需將葉子結(jié)點(diǎn)中的最小關(guān)鍵字改為“最最 大值大值” ，然后重復(fù)上述步驟即可，然后重復(fù)上述步驟即可。 含有含有n個(gè)葉子結(jié)點(diǎn)的完全二叉樹的深度為個(gè)葉子結(jié)點(diǎn)的完全二叉樹的深度為 2n +1， 則總的時(shí)間復(fù)雜度為則總的時(shí)間復(fù)雜度為O(n2n) 。 4925 25 3728 28 1965 19 1534 15 2515 15 圖圖10- “淘汰賽淘汰賽”過程示意圖過程示意圖 kik2i 當(dāng)當(dāng)2in時(shí)時(shí) kik2i+1 當(dāng)當(dāng)2i+1n時(shí)時(shí) 或或 kik2i 當(dāng)當(dāng)2in

26、時(shí)時(shí) ki k2i+1 當(dāng)當(dāng)2i+1n時(shí)時(shí) 其中其中： i=1,2 , , n/2 3 堆排序思想堆排序思想 對(duì)一組待排序的記錄，按堆的定義對(duì)一組待排序的記錄，按堆的定義建立堆建立堆； 將將堆頂記錄和最后一個(gè)記錄交換堆頂記錄和最后一個(gè)記錄交換位置，則前位置，則前n-1 個(gè)記錄是無序的，而最后一個(gè)記錄是有序的；個(gè)記錄是無序的，而最后一個(gè)記錄是有序的； 堆頂記錄堆頂記錄被交換后，前被交換后，前n-1個(gè)記錄不再是堆，需個(gè)記錄不再是堆，需 將前將前n-1個(gè)待排序記錄重新組織成為一個(gè)堆，然后將個(gè)待排序記錄重新組織成為一個(gè)堆，然后將 堆頂記錄和倒數(shù)第二個(gè)記錄交換堆頂記錄和倒數(shù)第二個(gè)記錄交換位置，即將整個(gè)序

27、位置，即將整個(gè)序 列中次小關(guān)鍵字值的記錄調(diào)整列中次小關(guān)鍵字值的記錄調(diào)整(排除排除)出無序區(qū)；出無序區(qū)； 重復(fù)上述步驟，直到全部記錄排好序?yàn)橹怪貜?fù)上述步驟，直到全部記錄排好序?yàn)橹埂?結(jié)論結(jié)論：排序過程中，若采用排序過程中，若采用小根堆小根堆，排序后得到的是，排序后得到的是 非遞減序列非遞減序列；若采用；若采用大根堆大根堆，排序后得到的是，排序后得到的是非遞增非遞增 序列序列。 堆排序的關(guān)鍵堆排序的關(guān)鍵 如何由一個(gè)無序序列建成一個(gè)堆？如何由一個(gè)無序序列建成一個(gè)堆？ 如何在輸出堆頂元素之后，調(diào)整剩余元素，使之如何在輸出堆頂元素之后，調(diào)整剩余元素，使之 成為一個(gè)新的堆？成為一個(gè)新的堆？ 4 堆的調(diào)整堆

28、的調(diào)整篩選篩選 堆的調(diào)整思想堆的調(diào)整思想 輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；輸出堆頂元素之后，以堆中最后一個(gè)元素替代之； 然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并 與其中小者進(jìn)行交換與其中小者進(jìn)行交換；重復(fù)上述操作，直到是葉子結(jié)點(diǎn)；重復(fù)上述操作，直到是葉子結(jié)點(diǎn) 或其關(guān)鍵字值小于等于左、右子樹的關(guān)鍵字的值，將得或其關(guān)鍵字值小于等于左、右子樹的關(guān)鍵字的值，將得 到新的堆。稱這個(gè)從堆頂至葉子的調(diào)整過程為到新的堆。稱這個(gè)從堆頂至葉子的調(diào)整過程為“篩選篩選”， 如圖如圖10-10所示所示。 注意注意：篩選過程中，根結(jié)點(diǎn)的左、右子樹都是堆，

29、因篩選過程中，根結(jié)點(diǎn)的左、右子樹都是堆，因 此，篩選是從根結(jié)點(diǎn)到某個(gè)葉子結(jié)點(diǎn)的一次調(diào)整過程此，篩選是從根結(jié)點(diǎn)到某個(gè)葉子結(jié)點(diǎn)的一次調(diào)整過程。 圖圖10-10 堆的篩選過程堆的篩選過程 492537 28 19 65 3418 27 15 492537 28 19 65 3427 18 15 492737 28 19 65 3425 18 15 492537 28 19 65 3418 15 27 堆調(diào)整堆調(diào)整算法實(shí)現(xiàn)算法實(shí)現(xiàn) void Heap_adjust(Sqlist *H, int s, int m) /* H-Rsm中記錄關(guān)鍵字除中記錄關(guān)鍵字除H-Rs.key均滿足堆定義均滿足堆定義 *

30、/ /* 調(diào)整調(diào)整H-Rs的位置使之成為的位置使之成為小根堆小根堆 */ int j=s, k=2*j ; /* 計(jì)算計(jì)算H-Rj的左孩子的位置的左孩子的位置 */ H-R0=H-Rj ; /* 臨時(shí)保存臨時(shí)保存H-Rj */ for (k=2*j; k=m; k=2*k) if (kRk+1.key, H-Rk.key) k+ ; /* 選擇選擇左、右孩子中關(guān)鍵字的最小者左、右孩子中關(guān)鍵字的最小者 */ if ( LT(H-Rk.key, H-R0.key) ) H-Rj=H-Rk ; j=k ; k=2*j else break ; H-Rj=H-R0 ; 5 堆的建立堆的建立 利用篩選算

31、法，可以將任意無序的記錄序列建成一利用篩選算法，可以將任意無序的記錄序列建成一 個(gè)堆，設(shè)個(gè)堆，設(shè)R1,R2, ,Rn是待排序的記錄序列。是待排序的記錄序列。 將二叉樹的將二叉樹的每棵子樹都篩選成為堆每棵子樹都篩選成為堆。只有根結(jié)點(diǎn)的。只有根結(jié)點(diǎn)的 樹是堆。第樹是堆。第 n/2 個(gè)結(jié)點(diǎn)之后的所有結(jié)點(diǎn)都沒有子樹，個(gè)結(jié)點(diǎn)之后的所有結(jié)點(diǎn)都沒有子樹， 即以第即以第 n/2 個(gè)結(jié)點(diǎn)之后的結(jié)點(diǎn)為根的子樹都是堆。因此，個(gè)結(jié)點(diǎn)之后的結(jié)點(diǎn)為根的子樹都是堆。因此， 以這些結(jié)點(diǎn)為左、右孩子的結(jié)點(diǎn)，其左、右子樹都是堆，以這些結(jié)點(diǎn)為左、右孩子的結(jié)點(diǎn)，其左、右子樹都是堆， 則則進(jìn)行一次篩選進(jìn)行一次篩選就可以成為堆。同理，只

32、要將這些結(jié)點(diǎn)就可以成為堆。同理，只要將這些結(jié)點(diǎn) 的直接父結(jié)點(diǎn)的直接父結(jié)點(diǎn)進(jìn)行一次篩選進(jìn)行一次篩選就可以成為堆就可以成為堆。 只需從第只需從第 n/2 個(gè)記錄到第個(gè)記錄到第1個(gè)記錄依次進(jìn)行篩選就個(gè)記錄依次進(jìn)行篩選就 可以建立堆?？梢越⒍?。 可用下列語(yǔ)句實(shí)現(xiàn)可用下列語(yǔ)句實(shí)現(xiàn)： for (j=n/2; j=1; j-) Heap_adjust(R, j , n) ; 6 堆排序算法實(shí)現(xiàn)堆排序算法實(shí)現(xiàn) 堆的根結(jié)點(diǎn)是關(guān)鍵字最小的記錄，輸出根結(jié)點(diǎn)后，堆的根結(jié)點(diǎn)是關(guān)鍵字最小的記錄，輸出根結(jié)點(diǎn)后， 是以序列的最后一個(gè)記錄作為根結(jié)點(diǎn)，而原來堆的左、是以序列的最后一個(gè)記錄作為根結(jié)點(diǎn)，而原來堆的左、 右子樹都是堆

33、，則右子樹都是堆，則進(jìn)行一次篩選進(jìn)行一次篩選就可以成為堆。就可以成為堆。 void Heap_Sort(Sqlist *H) int j ; for (j=H-length/2; j0; j-) Heap_adjust(H, j , H-length) ; /* 初始建堆初始建堆 */ for (j=H-length/2; j=1; j-) H-R0=H-R1 ; H-R1=H-Rj ; H-Rj=H-R0 ; /* 堆頂與最后一個(gè)交換堆頂與最后一個(gè)交換 */ Heap_adjust(H, 1, j-1) ; 7 算法分析算法分析 主要過程：初始建堆和重新調(diào)整成堆。設(shè)記錄數(shù)為主要過程：初始建堆

34、和重新調(diào)整成堆。設(shè)記錄數(shù)為n， 所對(duì)應(yīng)的完全二叉樹深度為所對(duì)應(yīng)的完全二叉樹深度為h 。 初始建堆初始建堆：每個(gè)非葉子結(jié)點(diǎn)都要從上到下做：每個(gè)非葉子結(jié)點(diǎn)都要從上到下做“篩篩 選選” 。第。第i層結(jié)點(diǎn)數(shù)層結(jié)點(diǎn)數(shù)2i-1，結(jié)點(diǎn)下移的最大深度是，結(jié)點(diǎn)下移的最大深度是h-i， 而每下移一層要比較而每下移一層要比較2次，則比較次數(shù)次，則比較次數(shù)C1(n)為：為： C1(n) 2 (2i-1(h-i)4(2h-h-1) h-1 i=1 h= 2n +1， C1(n)4(n-2n-1) 篩選調(diào)整篩選調(diào)整：每次篩選要將根結(jié)點(diǎn)：每次篩選要將根結(jié)點(diǎn)“下沉下沉”到一個(gè)到一個(gè) 合適位置。第合適位置。第i次篩選時(shí)次篩選時(shí)

35、：堆中元素個(gè)：堆中元素個(gè)數(shù)為數(shù)為n-i+1；堆；堆 的深度是的深度是 2(n-i+1) +1，則進(jìn)行，則進(jìn)行n-1次次“篩選篩選”的比的比 較次數(shù)較次數(shù)C2(n)為為： C2(n) (22(n-i+1) n-1 i=1 C2(n)2n2n 堆排序的比較次數(shù)的數(shù)量級(jí)為：堆排序的比較次數(shù)的數(shù)量級(jí)為： T(n)=O(n2n)； 而附加空間就是交換時(shí)所用的臨時(shí)空間，故空間復(fù)雜而附加空間就是交換時(shí)所用的臨時(shí)空間，故空間復(fù)雜 度為：度為： S(n)=O(1) 。 歸并歸并(Merging) ：是指將兩個(gè)或兩個(gè)以上的有序序：是指將兩個(gè)或兩個(gè)以上的有序序 列合并成一個(gè)有序序列。若采用線性表列合并成一個(gè)有序序列。若采用線性表(無論是那種存無論是那種存 儲(chǔ)結(jié)構(gòu)儲(chǔ)