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

Presentation on theme: "第七章 資料排序 Sorting 版權屬作者所有，非經作者 同意不得用於教學以外用途."— Presentation transcript:

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

2 本章內容 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 二元樹排序法

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

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

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

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

7 (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 次交換

8 [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後 排序完畢

9 資料量 n = 9 1. void Bubble_Sort(int a[], int n) 2. { int i, j, temp;
for (i = n-1 ; i > 0 ; i--) //i是右限 4. for (j = 0 ; j < i ; j++) if (a[j] > a[j+1]) //左大右小 { temp = a[j]; //將 a[j] 與 a[j+1] 交換 7. a[j] = a[j+1]; 8. a[j+1] = temp; } 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

10 交換三部曲 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   

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

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

13 圖示說明 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後 排序完畢

14 資料量 n = 9 1. void Select_Sort(int a[], int n)
{ int i, j, max, temp; 3. for (i = n-1 ; i > 0 ; i--) //i是右限 4. { max = i; //找出範圍中(a[0] ~ a[i])最大者，先假設a[i]最大 for ( j = i-1 ; j >= 0 ; j--) // j由右而左掃描 if (a[j] > a[max]) //第j個挑戰成功 7. max = j; //max隨時紀錄最大者 temp = a[max]; //將a[i] 與a[max] 交換 a[max] = a[i]; a[i] = temp; 11. } } 外圈 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

15 選擇 – 掃描一次的自然產物 最大值為 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

16 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]最大 for ( j = i-1 ; j >= 0 ; j--) // j由右而左掃描 if (a[j] > a[max]) //第j個挑戰成功 7. max = j; //max隨時紀錄最大者 temp = a[max]; //將a[i] 與a[max] 交換 a[max] = a[i]; a[i] = temp; 11. } } 比較〈第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)

17 插入排序法 基本動作：將鍵值插入左邊適當的地方，使範圍內鍵值都排好。 假設要排序第 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插入到最左邊位置

18 現在的任務，是要把 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] 就都照順序排好了。

19 [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]

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

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

22 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 的速度遞增 )，將可獲得不錯的效率

23 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 合併排序法：兩組各一個資料合併為一組二個、兩組各二個合併為一組四個直到所有資料合併成一組。

24 圖示說明 已經排序好的鍵值組 [19 25 ] 鍵值切割及合併的過程 對應步驟說明 1 37 41 19 81 41’ 25 56 61
[ ] 鍵值切割及合併的過程 對應步驟說明 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，結束

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

26 → 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)

27 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' ….61 ….49 i = l + 1 往右直到大於等於基準值。 j = r 往左直到小於等於基準值 2 暫停未交錯 3 37 ….25… 19… .81… .41' ….61 ….49 交換 4 暫停已交錯 5 19 ….25… 37… .81… .41' ….61 ….49 基準值 a[l] 和a[j] 交換 j i i j i j j i 分割點 j l j r 基準值 小於等於基準值 大於等於基準值

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

29 圖示說明 已經就定位的鍵值 鍵值分割及排序狀況 說明 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

30 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[]

31 鍵值的每一位數只有 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[]

32 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[]

33 [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[]

34 例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

35 [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[] 即完成。

36 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[]，我們也可以將它看成完整二元樹，但是這個完整二元樹不一定是堆積

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

38 插入法 (向上調整) 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

39 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

40 往下調整法 演算法：往下調整法將陣列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

41 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

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

43 假設這已經是一個堆積 (使用向上或向下調整法其中一種)
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

44 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

45 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.重複 “ 交換 -- 調整 “ 過程，即可將陣列排序好

46 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