第七章 資料排序 Sorting 版權屬作者所有，非經作者 同意不得用於教學以外用途

本章內容 7-1 排序及定義 7-2 基本排序法 氣泡排序法、選擇排序法、插入排序法 7-3 Shell 排序法 7-4 合併排序法 7-1 排序及定義 7-2 基本排序法 氣泡排序法、選擇排序法、插入排序法 7-3 Shell 排序法 7-4 合併排序法 7-5 快速排序法 7-6 基數排序法 7-7 堆積排序法 7-8 二元樹排序法

7-1 排序及定義 ※ 用某些欄位為依據來調整紀錄間的順序，這個動作稱為排序（sort）。用來排序的欄位稱為鍵欄（key field），鍵欄的值稱為鍵值 ( key value) 紀錄編號 姓名 年齡 電話 住址 1 張四 31 (02)2334---- 台北市XXX 2 李五 16 (02)2999---- 新北市XXX 3 王六 25 (03)3444---- 桃園縣XXX 4 趙大 41 (02)2887---- 5 陳文 53 (04)333---- 台中市XXX 6 江水 28 (03)534---- 新竹市XXX 紀錄 欄位 根據年齡欄位排序 紀錄編號 姓名 年齡 電話 住址 1 李五 16 (02)2999---- 新北市XXX 2 王六 25 (03)3444---- 桃園縣XXX 3 江水 28 (03)534---- 新竹市XXX 4 張四 31 (02)2334---- 台北市XXX 5 趙大 41 (02)2887---- 6 陳文 53 (04)333---- 台中市XXX

※ 內部排序法 ( internal sort ) 待排序的資料全部在主記憶體 ( RAM ) 中，這些排序法稱為內部排序法 ※ 外部排序法 ( external sort ) 待排序的資料只有部分在主記憶體中，其他大部份資料存於外部記憶體 ※ 排序法主要是比較它們排序的效率。通常我們以排序的資料量 ( n 個資料 ) 為參數，有些需時 O(n2)，有些可達 O(n lg n) ※ 排序法另一個要素是執行這些排序法所需的額外記憶體空間大小。有些完全不需額外記憶體，有些只需少數記憶體，有些需要O(n)的額外記憶體，有些甚至更多 ※ 在內部排序法中，影響效率的因素通常是作比較 ( compare ) 的次數，和資料交換 ( 或移動 ) 的次數

具有穩定性 不具有穩定性 ※ 排序法的穩定性 ( stability ) 所謂穩定性，是指原先具有相同鍵值的那些記錄，經過排序後仍然保持原先的先後次序 ( 鍵值不同的當然已經改變過 ) 18, 3, 9, 18’, 10, 9’, 6, 3’ 兩個人都18歲 兩個人都18歲 3, 3’, 6, 9, 9’, 10, 18, 18’ 具有穩定性 3, 3’, 6, 9’, 9, 10, 18, 18’ 不具有穩定性

7-2 基本排序法 氣泡排序法 基本動作：相鄰兩個元素比較，左大右小則交換。 41 19 19 41 只有2個資料時 41 19 65 7-2 基本排序法 氣泡排序法 基本動作：相鄰兩個元素比較，左大右小則交換。 41 19 19 41 只有2個資料時 比較發現左大右小 交換 41 19 65 19 41 65 有3個資料時 先比較第1、2個資料 比較發現左大右小 交換 19 41 65 19 41 65 再比較第2、3個資料 比較發現非 左大右小 不交換

(81 > 41’ 須交換)，接著a[4]比a[5] Pass 1 (第一回合) [0] [1] [2] [3] [4] [5] [6] [7] [8] 說明 37 41 19 81 41’ 25 56 61 49 a[0]比a[1] (37  41不須交換)，接著a[1]比a[2] (41 > 19 須交換)，接著a[2]比a[3] (41  81不須交換)，接著a[3]比a[4] (81 > 41’ 須交換)，接著a[4]比a[5] (81 > 25 須交換)，接著a[5]比a[6] (81 > 56 須交換)，接著a[7]比a[7] (81 > 61 須交換)，接著a[7]比a[8] (81 > 49 須交換) Pass 1 : 8 次比較 Pass 1 : 5 次交換

[0] [1] [2] [3] [4] [5] [6] [7] [8] 說明 原始資料 37 41 19 81 41’ 25 56 61 49 Pass 1 : a[0] ~ a[8] 執行Pass 1後 Pass 2 : a[0] ~ a[7] 執行Pass 2後 Pass 3 : a[0] ~ a[6] 執行Pass 3後 Pass 4 : a[0] ~ a[5] 執行Pass 4後 Pass 5 : a[0] ~ a[4] 執行Pass 5後 Pass 6 : a[0] ~ a[3] 執行Pass 6後 Pass 7 : a[0] ~ a[2] 執行Pass 7後 Pass 8 : a[0] ~ a[1] 執行Pass 8後 排序完畢

資料量 n = 9 1. void Bubble_Sort(int a[], int n) 2. { int i, j, temp; 3. for (i = n-1 ; i > 0 ; i--) //i是右限 4. for (j = 0 ; j < i ; j++) 5. if (a[j] > a[j+1]) //左大右小 6. { temp = a[j]; //將 a[j] 與 a[j+1] 交換 7. a[j] = a[j+1]; 8. a[j+1] = temp; 9. } 10. } 資料量 n = 9 外圈 i = 8~0 內圈 j = 0 ~ 7 [0] [1] [2] [3] [4] [5] [6] [7] [8] 37 41 19 81 41’ 25 56 61 49 a[j] 與 a[j+1] 作比較，若a[j] > a[j+1] 則交換 當 j 由 0 到 7

交換三部曲 a b a 和 b 的值要交換 5 10 a b t  t = b; //先將b的值存起來 5 10  a b t  b = a; //a的值就可以給b 5 10   a b t  a = t; //暫存的b值給a 10 5   

1. void Bubble_Sort(int a[], int n) 2. { int i, j, temp; 3. for (i = n-1 ; i > 0 ; i--) //i是右限 4. for (j = 0 ; j < i ; j++) 5. if (a[j] > a[j+1]) //左大右小 6. { temp = a[j]; //將 a[j] 與 a[j+1] 交換 7. a[j] = a[j+1]; 8. a[j+1] = temp; 9. } 10. } 比較〈第5行〉 交換〈第6~8行〉 最好狀況 最壞狀況 Pass 1 n-1 Pass 2 n-2 Pass 3 n-3 ： Pass n-1 1 總 計

選擇排序法 基本動作：選擇出範圍內最大的元素，將之與範圍內最右邊的元素交換。 逐一掃描，選擇出最大的資料 81，最右邊的資料是 49 37 41 19 81 41’ 25 56 61 49 逐一掃描，選擇出最大的資料 81，最右邊的資料是 49 37 41 19 49 41’ 37 56 61 81 將 81與最右邊的資料交換 氣泡排序法是 一步一腳印– 最大元素慢慢交換到最右邊位置 選擇排序法是 一步到位– 最大元素一次交換到最右邊位置

圖示說明 81 已經就定位的鍵值 49 範圍內最右的鍵值 這兩個鍵值要交換 81 範圍內最大的鍵值 [0] [1] [2] [3] [4] [5] [6] [7] [8] 說明 原始資料 37 61 19 41 81 25 56 41’ 49 Pass 1：a[0]~a[8]，8149 Pass 1後 Pass 2：a[0]~a[7]，6141’ Pass 2後 Pass 3：a[0]~a[6]，5656 Pass 3後 Pass 4：a[0]~a[5]，4925 Pass 4後 Pass 5：a[0]~a[4]，4125 Pass 5後 Pass 6：a[0]~a[3]，41’25 Pass 6後 Pass 7：a[0]~a[2]，3719 Pass 7後 Pass 8：a[0]~a[1]，2525 Pass 8後 排序完畢

資料量 n = 9 1. void Select_Sort(int a[], int n) 2. { int i, j, max, temp; 3. for (i = n-1 ; i > 0 ; i--) //i是右限 4. { max = i; //找出範圍中(a[0] ~ a[i])最大者，先假設a[i]最大 5. for ( j = i-1 ; j >= 0 ; j--) // j由右而左掃描 6. if (a[j] > a[max]) //第j個挑戰成功 7. max = j; //max隨時紀錄最大者 8. temp = a[max]; //將a[i] 與a[max] 交換 9. a[max] = a[i]; 10. a[i] = temp; 11. } 12. } 外圈 i = 8~1 資料量 n = 9 內圈 j = 7 ~ 0 [0] [1] [2] [3] [4] [5] [6] [7] [8] 37 41 19 81 41’ 25 56 61 49 max = 8 a[j] 與 a[max] 作比較，若a[j] > a[max] 則交換重新設定 max 為 j 當 j 由 7 到 0

選擇 – 掃描一次的自然產物 最大值為 81 [0] [1] [2] [3] [4] [5] [6] [7] [8] 說明 原始資料 37 61 19 41 81 25 56 41’ 49 初設最大值 = 49 第1次比較  41’  49, 最大值不變 第2次比較 56 > 49, 最大值 = 56 第3次比較 25  56, 最大值不變 第4次比較 81 > 56, 最大值= 81 第5次比較 41  81, 最大值不變 第6次比較 19  81, 最大值不變 第7次比較 61  81, 最大值不變 第8次比較 37  81, 最大值不變 最大值為 81

1. void Select_Sort(int a[], int n) 2. { int i, j, max, temp; 3. for (i = n-1 ; i > 0 ; i--) //i是右限 4. { max = i; //找出範圍中(a[0] ~ a[i])最大者，先假設a[i]最大 5. for ( j = i-1 ; j >= 0 ; j--) // j由右而左掃描 6. if (a[j] > a[max]) //第j個挑戰成功 7. max = j; //max隨時紀錄最大者 8. temp = a[max]; //將a[i] 與a[max] 交換 9. a[max] = a[i]; 10. a[i] = temp; 11. } 12. } 比較〈第6行〉 交換及設定〈第4, 7, 8~10行〉 最好狀況 最壞狀況 Pass 1 n-1 1+1 n + 1 Pass 2 n-2 n-1 + 1 Pass 3 n-3 n-2 + 1 ： Pass n-1 1 2 + 1 總 計 2(n-1)

插入排序法 基本動作：將鍵值插入左邊適當的地方，使範圍內鍵值都排好。 假設要排序第 3 個資料(前2個已經排好) up [0] [1] [2] 假設要排序第 3 個資料(前2個已經排好) 37 41 19 1. 首先將a[2]的值往上提，放入up變數，則 a[2] 的位置等於空下來一樣。 [0] [1] [2] 37 41 19 up 由於 41 > 19，因此將41往右移，現在變成a[1] 的位置空下來了。 [0] [1] [2] 37 41 19 up 由於 37 > 19，因此將37往右移，現在變成a[0] 的位置空下來了。 [0] [1] [2] 37 41 19 up 空位已經在最左邊了，因此把 up 中的值 ( 19 ) 放入空位a[0]。 [0] [1] [2] 37 41 up 19 因此 a[0] ~ a[2] 已經照順序排好了 以上連續動作相當於將19插入到最左邊位置

現在的任務，是要把 a[8] ( 49 ) 插入左邊適當的位置。 首先將a[8]的值 ( 49 ) 往上提，放入up變數，則 a[8] 產生空位。 up 49 [0] [1] [2] [3] [4] [5] [6] [7] [8] 19 25 37 41 41’ 56 61 81 2. 81 > 49, 61 > 49, 56 > 49，因此它們分別往右移一位。41’ 不大於49，因此41’ 不動，空位停在a[5]。 up 49 [0] [1] [2] [3] [4] [5] [6] [7] [8] 19 25 37 41 41’ 56 61 81 3. 將 up 的值 ( 49) 放入空位a[5] 中。 [0] [1] [2] [3] [4] [5] [6] [7] [8] 19 25 37 41 41’ 49 56 61 81 因此 a[0] ~ a[8] 就都照順序排好了。

[0] [1] [2] [3] [4] [5] [6] [7] [8] 說明 開始 37 41 19 81 41’ 25 56 61 49   [0] [1] [2] [3] [4] [5] [6] [7] [8] 說明 開始 37 41 19 81 41’ 25 56 61 49 粗體字為插入資料 Pass 1後 37不比41大，41不動 Pass 2後 41,37各往右移，19插入a[0] Pass 3後 41不比81大，81不動 Pass 4後 81>41’往右移，41’插入a[3] Pass 5後 比25大的均右移 Pass 6後 81>56往右移，56插入a[5] Pass 7後 81>61往右移，61插入a[6] Pass 8後 81,61,56往右移，49插入a[5]  

移動 (包括a[i]指定給 up及up指定給a[j]) 1. void Insert_Sort(int a[], int n) 2. { int i, j, up; 3. for (i = 1 ; i < n ; i++) //a[i]是要整理的元素(a[0]~a[i-1]已經整理好) 4. { up = a[i]; 5. j = i; //j 記錄空格位置 6. while (j > 0 && a[j-1] > up) //空格左邊的值比up大 7. { a[j] = a[j-1]; //空格左邊的值往右移一格 8. j--; 9. } 10. a[j] = up; //up中的值放入最後的空位 11. } 12. } 比較 移動 (包括a[i]指定給 up及up指定給a[j]) 最好狀況 最壞狀況 Pass 1 1 2 2+1 Pass 2 2+2 Pass 3 3 2+3 ： Pass n-1 n-1 2+(n-1) 總計 2(n-1)

基本排序法的比較 最好效率 平均效率 額外記憶體需求 穩定性 氣泡排序法 O(n2) 有 選擇排序法 無 插入排序法 O(n)

7-3 Shell 排序法 37 41 19 81 25 56 61 49 4 - Sorted File 37 25 19 61 41 [0] [1] [2] [3] [4] [5] [6] [7] [8] 待排序資料 37 41 19 81 41‘ 25 56 61 49 將鍵值分成 4 組，因此每隔 4 個元素，歸為同一組： 第一組：a[0], a[0+4], a[0+2*4], .., a[0+ i*4],… 第二組：a[1], a[1+4], a[1+2*4], .., a[1+ i*4],… 第三組：a[2], a[2+4], a[2+2*4], .., a[2+ i*4],… 第四組：a[3], a[3+4], a[3+2*4], .., a[3+ i*4],… 再針對每一組內部執行插入排序法，鍵值變成： [0] [1] [2] [3] [4] [5] [6] [7] [8] 4 - Sorted File 37 25 19 61 41‘ 41 56 81 49 [0] [1] [2] [3] [4] [5] [6] [7] [8] (1 - )Sorted File 19 25 37 41‘ 41 49 56 61 81 如果鍵值很多，可以先進行 13-sort，再進行 4-sort，最後再進行 1-sort，以此類推。Knuth 提出的遞增數列是1, 4, 13, 40, 121, …( 以 3h+1 的速度遞增 )，將可獲得不錯的效率

7-4 合併排序法 合併 (merge) 排序好的 A[] 9 12 17 21 37 排序好的 B[] 3 11 20 55 67 71 7-4 合併排序法 合併 (merge) [0] [1] [2] [3] [4] 排序好的 A[] 9 12 17 21 37 [0] [1] [2] [3] [4] [5] [6] 排序好的 B[] 3 11 20 55 67 71 89 合併 合併成排序好的 C[] [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 3 9 11 12 17 20 21 37 55 67 71 89 合併排序法：兩組各一個資料合併為一組二個、兩組各二個合併為一組四個直到所有資料合併成一組。

圖示說明 已經排序好的鍵值組 [19 25 ] 鍵值切割及合併的過程 對應步驟說明 1 37 41 19 81 41’ 25 56 61 [19 25 ] 鍵值切割及合併的過程 對應步驟說明 1 37 41 19 81 41’ 25 56 61 49 有斜線部分為合併動作 2 [37 81] [41’ 49] 首先對切 3 41] [19 左半部再對切 4 [37] [41] 第一組2個可再對切 5 左邊2個組進行合併 6 [19] [81] 第二組2個對切 7 第二組2個合併 8 前二組2,2合併成4個 9 25] [56 右半部對切成2,3兩組 10 [41’] [25] 右前半部對切 11 [25 41’] 合併 12 [56] [61 右後半部對切 13 [61] [49] 最右一組對切 14 [49 61] 最右1,1合併為2 15 最右1,2合併為3 16 最右2,3合併為5 17 4,5合併為9，結束

從排序的過程來看，合併排序法是不斷地將鍵值對切，切到不能再切（一個鍵值）再進行合併。合併時則反向兩組兩組進行，直到最後合併成整個檔案。 我們從遞迴的角度來看，如果從步驟1,2直接對切後跳至步驟16，接著只是單純地將兩組排好的資料合併而已。但是步驟16的成果，卻是由步驟2~7（左半部）及步驟8~15（右半部）分別進行合併排序累積起來的。 先把大問題切成小問題，再分開解決小問題，最後再把解決小問題所獲致的成果累積起來，成為大問題的成果，這種解題方法稱為「個個擊破法」( divide and conquer )。 合併排序法就是採用個個擊破法，積小勝為大勝，最後獲得全盤的勝利。

→ T(n)  2( 2T(n/4) + n/2 ) + n , ∵ T(n/2)  2 T(n/4) + n/2 T(n)  2 T(n/2) + n , T(1) = 0 → T(n)  2( 2T(n/4) + n/2 ) + n , ∵ T(n/2)  2 T(n/4) + n/2 → T(n)  22T(n/22) + n + n ： → T(n)  2kT(n/2k) + kn 當 n ≒ 2k ( lg n ≒ k )時 → T(n)  n T(n/2k) + kn → T(n)  nT(1) + kn ＝ kn ＝ n lg n 因此 T(n) ＝ O(n lg n)

7-5 快速排序法 分割 (partition) j i i j i j j i 分割點 j 暫停未交錯 交換 暫停已交錯 基準值 l r 7-5 快速排序法 分割 (partition) 基準值   l r 說 明 1 37 ….41… 19… .81… .41'.. ..25... .56 ….61 ….49 i = l + 1 往右直到大於等於基準值。 j = r 往左直到小於等於基準值 2 暫停未交錯 3 37 ….25… 19… .81… .41'.. ..41... .56 ….61 ….49 交換 4 暫停已交錯 5 19 ….25… 37… .81… .41'.. ..41... .56 ….61 ….49 基準值 a[l] 和a[j] 交換 j i i j i j j i 分割點 j l j r 基準值 小於等於基準值 大於等於基準值  

分割的另一個例子 l r 說 明 1 40 41 19 81 41' 25 56 21 61 49 i = + 1 j ; ( , 都是位置 ) 2 一路往右，直到 ³ 一路往左，直到 £ 3 < ，將 a[ ] 和 交 換 4 5 6 ’ 7 > ，已經錯身而過，將 基準值 分割點

圖示說明 已經就定位的鍵值 鍵值分割及排序狀況 說明 1 37 41 19 81 41’ 25 56 61 49 原始資料 2 [19   已經就定位的鍵值 鍵值分割及排序狀況 說明 1 37 41 19 81 41’ 25 56 61 49 原始資料 2 [19 25] [81 49] 第一次分割後 3 []19 [25] 空的中括號[]代表無元素 4 [49 61] 81[] 5 [41 41’] [56 陰影部分為已就定位 6 []41 [41’] 7 []56 [61] 8

7-6 基數排序法 LSD ( Least Significant Digit First ) 每一位數的排序--使用分配法 7-6 基數排序法 LSD ( Least Significant Digit First ) 初始順序 139 219 532 655 422 164 098 422’ 334 按個位數 按十位數 按百位數 如果個位、十位、百位數都使用前面介紹的任一方法，豈不是多此一舉，因為沒有用到將鍵值拆開的好處。 因此我們介紹分配法，每位數字只需O(n)就可處理 每一位數的排序--使用分配法 1. 計算此位數各種值出現的次數   2. 進行累積 3. 將鍵值分配至暫時陣列 b[] 4. 由暫時陣列 b[] 寫回陣列 a[]

鍵值的每一位數只有 0 ~ 9，共十種可能。例如12個鍵值的個位數： [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] a[] 9 8 2 3 2’ 4 4’ 7 8’ 5 7’ 8” 1. 計算此位數各種值出現的次數：使用輔助陣列 count[10] ( 10 是因為鍵值只有10 種可能 )。count[0] 代表鍵值 0 出現的次數，count[1] 代表鍵值 1 出現的次數，…。因此陣列 count[] 將變成： 2 1 3 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] count[] 8出現3次 2. 執行累積：count[2] = 2 代表有2個元素小於等於鍵值 2。count[4] = 5 代表有 5 個元素小於等於鍵值 4 。因此陣列 count[] 將變成： 2 3 5 6 8 11 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 12 count[]

3. 將鍵值分配至暫時陣列 b[] ：先分配 a[11]，再分配 a[10]，… [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] a[] 9 8 2 3 2’ 4 4’ 7 8’ 5 7’ 8” 分配 a[11] （8），count[8] = 11，代表有11個元素小於等於鍵值8，因此將它分配在陣列b[] 的第11個位置 ( b[10] )。並且count[8] 減1成為10 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 8” b[] 2 3 5 6 8 10 12 count[] 分配 a[10] （7），count[7] = 8，代表有8個元素小於等於鍵值 7，因此將它分配在陣列b[] 的第8個位置 ( b[7] )。並且count[7] 減1成為7 7’ [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 8” b[] 2 3 5 6 7 10 12 count[]

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] a[] 9 8 2 3 2’ 4 4’ 7 8’ 5 7’ 8” 分配 a[9] （5），count[5] = 6，代表有 6 個元素小於等於鍵值 5，因此將它分配在陣列b[] 的第 6 個位置 ( b[5] )。並且count[5] 減1 成為 5 5 7’ [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 8” b[] 2 3 6 7 10 12 count[] 以同樣的方法分配 a[8] ~ a[0] 2 2’ 3 4 4’ 5 7 7’ 8 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] 8’ 8” 9 b[] 4. 由暫時陣列 b[] 寫回陣列 a[]

例7.7 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] a[] 9 2 3 5 3’ 5’ 6 2’ 3” 5” 7 1.計數：count陣列先儲存每種鍵值出現的次數。 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] count[] 1 2 3 count[5] = 3, 代表鍵值5重複3次，其他以此類推。 2. 再由前往後累積。 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] count[] 1 3 6 9 10 11 12 count[3] = 6, 代表有6個鍵值小於等於3，其他以此類推 3. 再將陣列a的鍵值由後往前分配至陣列b。 A. 分配 a[11] ( = 0 ) [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] count[] 1 3 6 9 10 11 12 b[] B. 分配 a[10] ( = 7 ) [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] count[] 1 3 6 9 10 11 12 b[] 7

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] a[] 9 2 3 5 3’ 5’ 6 2’ 3” 5” 7 C. 分配 a[9] ( = 5” ) [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] count[] 1 3 6 8 10 11 12 b[] 5” 7 同樣方式分配 a[8] ~ a[0]： [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] count[] 1 3 6 9 10 11 b[] 2 2’ 3’ 3” 5 5’ 5” 7 4. 由陣列b[] 回寫至陣列a[] 即完成。

7-7 堆積排序法 堆積 ( heap ) 的定義：堆積是一種完整二元樹，在堆積中任一個內部節點的鍵值，都大於等於其子節點的鍵值 91 72 7-7 堆積排序法 堆積 ( heap ) 的定義：堆積是一種完整二元樹，在堆積中任一個內部節點的鍵值，都大於等於其子節點的鍵值 91 1 72 53 2 3 39 4 62 43 5 21 6 28 7 堆積可以按照完整二元樹的方式儲存： [0] [1] [2] [3] [4] [5] [6] [7] a[] 91 72 53 39 62 45 21 28 反過來說，如果有一個任意的陣列a[]，我們也可以將它看成完整二元樹，但是這個完整二元樹不一定是堆積

將任意的完整二元樹調整成堆積的方法 往下調整法 插入法(往上調整) 【方法一】插入(往上調整)法 不斷插入元素到堆積中，並且加以調整。 調整的方法是：跟它的父節點作比較，若大於其父節點則交換，交換後重複與其新的父節點比較，直到不能再上為止。 演算法：逐一插入法將陣列a調整成堆積 從第二個資料開始直到最後一個資料，假設資料為a[k]，重複迴圈 當a[k] 有父節點且大於其父節點，重複迴圈 a[k] 與它的父節點交換 //a[k]相當於升了一代 迴圈結束 演算法結束

插入法 (向上調整) 38 72 67 41 39 37 25 66 73 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] a[] 38 72 67 41 39 72’ 37 25 66 73 38 72 1 72 38 1 67 2 38 72 38 1 67 2 41 3 72 41 1 67 2 38 3 39 4 72’ 5 72 41 1 67 2 38 3 39 4 72 41 1 72’ 2 38 3 39 4 67 5 37 6 72 41 1 72’ 2 38 3 39 4 67 5 37 6 25 7

72 41 1 72’ 2 38 3 39 4 67 5 37 6 25 7 66 8 72 66 1 72’ 2 41 3 39 4 67 5 37 6 25 7 38 8 73 9

往下調整法 演算法：往下調整法將陣列a調整成堆積 從最後一個有子節點的節點 a[k] 開始，直到樹根a[0]，重複迴圈 當a[k] 有兒子且小於兒子中最大的（稱為大兒子），重複迴圈 a[k] 與它的大兒子交換 //a[k]相當於降了一代 迴圈結束 演算法結束 38 a[4] (39) 與 a[9] (73)交換 大兒子 38 72 67 41 73 25 72’ 37 1 2 3 4 5 6 7 66 8 39 9 調整對象 1 72 67 2 3 41 4 72’ 5 6 37 39 7 25 8 66 9 73 大兒子 a[3] (41) 與 a[8] (66)交換 大兒子 a[2] (67) 與 a[5] (72’)交換 38 72 41 73 25 37 1 2 3 4 5 6 7 66 8 39 9 72’ 67 38 72 41 73 25 37 1 2 3 4 5 6 7 66 8 39 9 72’ 67

a[1] (72) 與 a[4] (73) 交換 38 41 73 25 37 1 2 3 4 5 6 7 66 8 39 9 72’ 67 72 a[0] (38) < a[1] (73)交換，接著 a[1] (38) < a[4] (72)交換，接著a[4] (38) < a[9] (39)交換 41 73 25 37 1 2 3 4 5 6 7 66 8 39 9 72’ 67 72 38

堆積排序法 演算法：堆積排序法 將陣列調整成堆積(使用向上或向下調整法) 當堆積節點數目大於1時，重複迴圈 將堆積的樹根與堆積的最後一個元素交換 堆積少最後一個節點 重新調整成堆積 迴圈結束 演算法結束

假設這已經是一個堆積 (使用向上或向下調整法其中一種) 73 假設這已經是一個堆積 (使用向上或向下調整法其中一種) 1 72 72’ 2 3 66 4 39 67 5 6 37 實際對應的陣列 7 25 8 41 38 9 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] a[] 73 72 72’ 66 39 67 37 25 41 38 1. 將a[0] ( 73 ) 和 a[9] ( 38，堆積的最後一個元素 ) 交換，並且73就不算入堆積的一部份，接著只看 a[0] ~ a[8] ，將a[0] 向下調整成堆積 ： 72 66 72’ 41 25 67 37 1 2 3 4 5 6 7 38 8 39 Downheap 調整成堆積 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 73 a[] 38 72 72’ 66 25 67 37 1 2 3 4 5 6 7 41 8 39 9 73

2. 將a[0] ( 72 ) 和 a[8] ( 38，堆積的最後一個元素 ) 交換，並重新調整： 72’ 66 67 41 39 38 37 25 72 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 73 a[] 1 2 3 4 5 6 7 Downheap 調整成堆積 38 66 72’ 41 25 67 37 1 2 3 4 5 6 7 39 8 72 3. 將a[0] ( 72’ ) 和 a[7] ( 25，堆積的最後一個元素 ) 交換，並重新調整： 67 66 38 41 39 25 37 72’ 72 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 73 a[] Downheap 調整成堆積 1 2 4 5 6 3 25 66 67 41 38 37 1 2 4 5 6 39 3 72’ 7

4. 將a[0] ( 67 ) 和 a[6] ( 37，堆積的最後一個元素 ) 交換，並重新調整： 66 41 38 37 39 25 67 72’ 72 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 73 a[] Downheap 調整成堆積 1 2 4 5 3 37 66 38 41 25 1 2 4 5 39 3 67 6 5.重複 “ 交換 -- 調整 “ 過程，即可將陣列排序好

7-8 二元樹排序法 二元樹排序法是使用「二元搜尋樹」( binary search tree ) 來完成排序，排序的步驟是： 7-8 二元樹排序法 二元樹排序法是使用「二元搜尋樹」( binary search tree ) 來完成排序，排序的步驟是： 1. 根據鍵值建立二元搜尋樹。 2. 對這棵二元搜尋樹進行中序走訪，並輸出結果。 [0] [1] [2] [3] [4] [5] [6] [7] [8] a[] 37 41 19 81 41’ 25 56 61 49 1. 建立二元搜尋樹 2. 中序走訪此二元搜尋樹 37 19 41 19, 25, 37, 41, 41’, 49, 56, 61, 81 25 81 41’ 56 49 61