Download presentation
Presentation is loading. Please wait.
1
Chapter 8 排序 資料結構導論 - C語言實作
2
8.1 前言 排序(Sort) ： 乃是將檔案中的紀錄(Records)依照特定欄位(Field)(或稱屬性(Attribute))的資料值來重新排列順序。 排序時須指定： 用哪一個欄位的資料值來排序。 按遞增(Ascending Order)或 按遞減(Descending Order)之順序來排序。 鍵(Key)：用來排序的欄位。 鍵值(Key Value)：欄位的資料值。 資料結構導論 - C語言實作
3
8.2 檔案、紀錄、欄位、索引與排序 檔案 資料表 欄位、屬性、資料行 紀錄、資料列 索引 資料結構導論 - C語言實作
4
8.2 檔案、紀錄、欄位、索引與排序 資料表(Table) 資料結構導論 - C語言實作
5
8.2 檔案、紀錄、欄位、索引與排序 索引(Index) 資料結構導論 - C語言實作
6
8.2 檔案、紀錄、欄位、索引與排序 索引(Index) 資料結構導論 - C語言實作
7
8.3 內部排序法(Internal Sort) 內部排序法 外部排序法 利用記憶體來排序 速度快 利用磁碟、磁帶等輔助記憶體來排序 速度慢
資料結構導論 - C語言實作
8
8.3 內部排序法(Internal Sort) 8.3.1. 氣泡浮昇排序法(Bubble Sort)。
8.3.2. 挑選排序法(Selection Sort)。 8.3.3. 插入排序法(Insertion Sort)。 8.3.4. 謝耳排序法(Shell Sort)。 8.3.5. 快速排序法(Quick Sort)。 8.3.6. 樹排序法 (Tree Sort)。 8.3.7. 堆積排序法(Heap Sort)。 8.3.8. 合併排序法(Merge Sort)。 基數排序法(Radix Sort)。 資料結構導論 - C語言實作
9
8.3.1. 氣泡浮昇排序法(Bubble Sort) 採用氣泡浮昇排序法將編號為0、1、2、...、n-1的n筆記錄按照「鍵值不遞減」的順序(Non-decreasing Order)加以排列的步驟如下： 步驟1：將n筆記錄的鍵值儲存到陣列d[n]中，其中d[0]儲存第0號記錄的鍵值、d[1]儲存第1號記錄的鍵值、…、d[n-1]儲存第n-1號記錄的鍵值。 資料結構導論 - C語言實作
10
8.3.1. 氣泡浮昇排序法(Bubble Sort) 步驟2：重複執行步驟3共計n-1回合，其中若有任一回合完全沒有發生陣列元素值「交換」的情形時，就執行步驟4。 步驟3：依序比較陣列d中相鄰兩元素之鍵值；即第i回合須依序比較(d[0]和d[1])、(d[1]和d[2])、(d[2]和d[3])、...、 (d[n-i+1]和d[n-i])；若前面的元素d[x]大於後面的元素d[x+1]，則立刻將d[x]與d[x+1]之值「交換」。 步驟4：列印出陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-i]之值。 資料結構導論 - C語言實作
11
8.3.1. 氣泡浮昇排序法(Bubble Sort) 【例1】氣泡浮昇排序法
假設有一組未經排序的資料R0、R1、R2、...、R7，其鍵值 {83，66，55，21，88，18，88*，99} 已經儲存在一維陣列d[8]中。 按照「鍵值不遞減」的順序加以排序 資料結構導論 - C語言實作
12
8.3.1. 氣泡浮昇排序法(Bubble Sort) 第1回合相鄰元素兩兩比較、交換位置之分解動作 資料結構導論 - C語言實作
13
8.3.1. 氣泡浮昇排序法(Bubble Sort) 資料結構導論 - C語言實作
14
8.3.1. 氣泡浮昇排序法(Bubble Sort) 穩定排序(Stable Sort) ： 不穩定排序(Unstable Sort)
相同鍵值的資料於排序後仍然保持排序前之前後關係者 不穩定排序(Unstable Sort) 資料結構導論 - C語言實作
15
8.3.2. 挑選排序法(Selection Sort)
挑選排序法也是透過「鍵值交換」來達成排序的目的。 第1回合從n筆鍵值中挑選出最小的鍵值，然後將它與d[0]交換位置。 第2回合從剩下的n-1筆鍵值中挑選出最小的鍵值，然後將它與d[1]交換位置。 第3回合從剩下的n-2筆鍵值中挑選出最小的鍵值，然後將它與d[2]交換位置。 第n-1回合從剩下的2筆鍵值中挑選出最小的鍵值，然後將它與d[n-2]交換位置。 剩下的1筆鍵值便是所有鍵值中的最大者，它自然存放在d[n-1]位置。 資料結構導論 - C語言實作
16
8.3.2. 挑選排序法(Selection Sort)
採用挑選排序法將編號為0、1、2、...、n-1的n筆紀錄按照「鍵值不遞減」的順序加以排列的步驟如下： 步驟1：將n筆紀錄的鍵值儲存到陣列d[n]中，其中d[0]儲存第0號紀錄的鍵值、d[1]儲存第1號紀錄的鍵值、…、d[n-1]儲存第n-1號紀錄的鍵值。 步驟2：重複執行步驟3，共計n-1回合。 步驟3：第i回合(i從1開始)，從陣列d[i-1]至d[n-1]中找出最小的鍵值(設d[x])，然後將d[x]與d[i-1]之鍵值交換。 步驟4：列印出陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-1]之值。 資料結構導論 - C語言實作
17
8.3.2. 挑選排序法(Selection Sort)
【例1】挑選排序法 假設有一組未經排序的資料R0、R1、R2、...、R7，其鍵值{83，66，55，21，88，18，88*，99}已經儲存在一維陣列d[8]中。 如果我們採用「挑選排序法」來將該組資料依「鍵值不遞減」的順序排序，總共須要7個回合，每一回合排序後之結果詳如表8.2所示。 資料結構導論 - C語言實作
18
8.3.2. 挑選排序法(Selection Sort)
19
8.3.2. 挑選排序法(Selection Sort)
第1回合， 從d[0]到d[7]找出最小者，結果找到d[5]=18最小，將d[5]之值與d[0]之值交換。 本回合排序後，最小之鍵值已經被安排到d[0]位置。 第2回合， 從d[1]到d[7]找出最小者，結果找到d[3]=21最小，將d[3]之值與d[1]之值交換。 本回合排序後，第2小之鍵值已經被安排到d[1]位置。 第3回合， 從d[2]到d[7]找出最小者，結果找到d[2]=55最小，將d[2]之值與d[2]之值交換。 本回合排序後，第3小之鍵值已經被安排到d[2]位置。 資料結構導論 - C語言實作
20
8.3.3. 插入排序法(Insertion Sort)
插入排序法的觀念是將n筆鍵值區分成「已排序」和「未排序」的A、B兩群 A群：已經排序好了 B群：尚未排序 排序時從B群取出一筆資料然後將之插入到A群的正確位置，重複這個動作直到B群空無資料，此時A群便是完整排序的資料了。 資料結構導論 - C語言實作
21
8.3.3. 插入排序法(Insertion Sort)
資料結構導論 - C語言實作
22
8.3.3. 插入排序法(Insertion Sort)
採用插入排序法將編號為0、1、2、...、n-1的n筆紀錄按照「鍵值不遞減」的順序加以排列的步驟如下： 步驟1：將n筆紀錄的鍵值儲存到陣列d[n]中，其中d[0]儲存第0號紀錄的鍵值、d[1]儲存第1號紀錄的鍵值、…、d[n-1]儲存第n-1號紀錄的鍵值。 步驟2：重複執行步驟3共計n-1回合。 步驟3：第i回合(i從1開始)，將陣列d[i]插入到其前面d[0]至d[i-1]的正確位置。 步驟4：列印出陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-1]之值。 資料結構導論 - C語言實作
23
8.3.3. 插入排序法(Insertion Sort)
【例1】插入排序法 假設有一組未經排序的資料R0、R1、R2、...、R7，其鍵值 {83，66，55，21，88，18，88*，99} 已經儲存在一維陣列d[8]中。 如果我們採用「插入排序法」來將該組資料依「鍵值不遞減」的順序排序，總共須要7個回合，每一回合排序後之結果詳如表8.3所示。 資料結構導論 - C語言實作
24
8.3.3. 插入排序法(Insertion Sort)
【例1】插入排序法 一開始， A群={83}， B群={66，55，21，88，18，88*，99}。 第1回合， 將B群的第1個鍵值d[1](66)插入A群，且必須保持A群的鍵值均按「不遞減」的順序排列。 因此66必須放到83之前，即d[0]=66，d[1]=83， 完成後A群={66，83}， B群={55，21，88，18，88*，99}。 資料結構導論 - C語言實作
25
8.3.3. 插入排序法(Insertion Sort)
資料結構導論 - C語言實作
26
8.3.4. 謝耳排序法(Shell Sort) 利用「固定間格」將部分鍵值先進行一次粗略的排序。
挑選一個固定的間距值s，然後將待排序的n筆鍵值分割成s組，每一群組裡的鍵值是從原始n個鍵值中挑出相間隔s間距的鍵值而成。 可減少插入排序法的資料搬動次數。 資料結構導論 - C語言實作
27
8.3.4. 謝耳排序法(Shell Sort) 採用謝耳排序法將編號為0、1、2、...、n-1的n筆記錄按照「鍵值不遞減」的順序加以排列的步驟如下： 步驟1：將n筆記錄的鍵值儲存到陣列d[n]中，其中d[0]儲存第0號記錄的鍵值、d[1]儲存第1號記錄的鍵值、…、d[n-1]儲存第n號記錄的鍵值。 步驟2：設定一適當之s值。(最好選用質數來當作 s值) 資料結構導論 - C語言實作
28
8.3.4. 謝耳排序法(Shell Sort) 步驟3：分組，將陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-1]均勻地分成s組，且同一組內的陣列元素之間距均為s，分配結果如下： 令a = (n-1)/s。 第1組 = {d[0]，d[s]，s[2×s]，...，A[a×s]}。 第2組 = {d[1]，d[1+s]，s[1+2×s]，...， A[1+a×s]}。 第3組 = {d[2]，d[2+s]，s[2+2×s]，...，A[2+a×s]}。 ‧‧‧ 第s組 = {d[s-1]，d[2×(s-1)]，s[3×(s-1)]，...。 資料結構導論 - C語言實作
![謝耳排序法(Shell Sort) 步驟3：分組，將陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-1]均勻地分成s組，且同一組內的陣列元素之間距均為s，分配結果如下：](http://slidesplayer.com/slide/15528747/93/images/28/%E8%AC%9D%E8%80%B3%E6%8E%92%E5%BA%8F%E6%B3%95%28Shell+Sort%29+%E6%AD%A5%E9%A9%9F3%EF%BC%9A%E5%88%86%E7%B5%84%EF%BC%8C%E5%B0%87%E9%99%A3%E5%88%97%E5%85%83%E7%B4%A0d%5B0%5D%E3%80%81d%5B1%5D%E3%80%81d%5B2%5D%E3%80%81d%5B3%5D%E3%80%81...%E3%80%81d%5Bn-2%5D%E3%80%81d%5Bn-1%5D%E5%9D%87%E5%8B%BB%E5%9C%B0%E5%88%86%E6%88%90s%E7%B5%84%EF%BC%8C%E4%B8%94%E5%90%8C%E4%B8%80%E7%B5%84%E5%85%A7%E7%9A%84%E9%99%A3%E5%88%97%E5%85%83%E7%B4%A0%E4%B9%8B%E9%96%93%E8%B7%9D%E5%9D%87%E7%82%BAs%EF%BC%8C%E5%88%86%E9%85%8D%E7%B5%90%E6%9E%9C%E5%A6%82%E4%B8%8B%EF%BC%9A.jpg "令a = (n-1)/s。 第1組 = {d[0]，d[s]，s[2×s]，...，A[a×s]}。 第2組 = {d[1]，d[1+s]，s[1+2×s]，...， A[1+a×s]}。 第3組 = {d[2]，d[2+s]，s[2+2×s]，...，A[2+a×s]}。 ‧‧‧ 第s組 = {d[s-1]，d[2×(s-1)]，s[3×(s-1)]，...。 資料結構導論 - C語言實作.")
29
8.3.4. 謝耳排序法(Shell Sort) 步驟4：使用插入排序法分別針對第1組、第2組、第3組、...、第s組進行「鍵值不遞減」排序。 步驟5：重新排列，將每一組的第1個值、第2個鍵值、第3個鍵值、...重新排列到d[0]、d[1]、d[2]、…、d[n-1]位置。 步驟6：重新設定一個較小的s值。若s>0則回到步驟3。 步驟7：列印出陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-i]之值。 資料結構導論 - C語言實作
![謝耳排序法(Shell Sort) 步驟4：使用插入排序法分別針對第1組、第2組、第3組、...、第s組進行「鍵值不遞減」排序。 步驟5：重新排列，將每一組的第1個值、第2個鍵值、第3個鍵值、...重新排列到d[0]、d[1]、d[2]、…、d[n-1]位置。](http://slidesplayer.com/slide/15528747/93/images/29/%E8%AC%9D%E8%80%B3%E6%8E%92%E5%BA%8F%E6%B3%95%28Shell+Sort%29+%E6%AD%A5%E9%A9%9F4%EF%BC%9A%E4%BD%BF%E7%94%A8%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%B3%95%E5%88%86%E5%88%A5%E9%87%9D%E5%B0%8D%E7%AC%AC1%E7%B5%84%E3%80%81%E7%AC%AC2%E7%B5%84%E3%80%81%E7%AC%AC3%E7%B5%84%E3%80%81...%E3%80%81%E7%AC%ACs%E7%B5%84%E9%80%B2%E8%A1%8C%E3%80%8C%E9%8D%B5%E5%80%BC%E4%B8%8D%E9%81%9E%E6%B8%9B%E3%80%8D%E6%8E%92%E5%BA%8F%E3%80%82+%E6%AD%A5%E9%A9%9F5%EF%BC%9A%E9%87%8D%E6%96%B0%E6%8E%92%E5%88%97%EF%BC%8C%E5%B0%87%E6%AF%8F%E4%B8%80%E7%B5%84%E7%9A%84%E7%AC%AC1%E5%80%8B%E5%80%BC%E3%80%81%E7%AC%AC2%E5%80%8B%E9%8D%B5%E5%80%BC%E3%80%81%E7%AC%AC3%E5%80%8B%E9%8D%B5%E5%80%BC%E3%80%81...%E9%87%8D%E6%96%B0%E6%8E%92%E5%88%97%E5%88%B0d%5B0%5D%E3%80%81d%5B1%5D%E3%80%81d%5B2%5D%E3%80%81%E2%80%A6%E3%80%81d%5Bn-1%5D%E4%BD%8D%E7%BD%AE%E3%80%82.jpg "步驟6：重新設定一個較小的s值。若s>0則回到步驟3。 步驟7：列印出陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-i]之值。 資料結構導論 - C語言實作.")
30
8.3.4. 謝耳排序法(Shell Sort) 【例1】謝耳排序法
假設有一組未經排序的資料R0、R1、R2、...、R7，其鍵值分別為 {83，66，55，21，88，18，88*，99}， 並且已經儲存在一維陣列d[8]中。 採用「謝耳排序法」來將該組資料依「鍵值不遞減」的順序排序之過程如下： 第1回合，我們假設s=3，將8個鍵值區分成3組。每一個組最多有3個鍵值，最少有2個鍵值。 第1組鍵值={d[0]、d[3]、d[6]}={83、21、88*}。 第2組鍵值={d[1]、d[4]、d[7]}={66、88、99}。 第3組鍵值={d[2]、d[5]}={55、18}。 資料結構導論 - C語言實作
31
8.3.4. 謝耳排序法(Shell Sort) 使用插入排序法分別對第1組、第2組、第3組鍵值進行排序，結果為：
第1組鍵值={21、83、88*}。 第2組鍵值={66、88、99}。 第3組鍵值={18、55}。 重新排列，將每一組的第1個鍵值，分別放入d[0]、d[1]、 d[2]。將每一組的第2個鍵值，分別放入d[3]、d[4]、 d[5]。將每一組的第3個鍵值，分別放入d[6]、d[7]，得到： 資料結構導論 - C語言實作
32
8.3.4. 謝耳排序法(Shell Sort) 第2回合，令s=s-1=3-1=2，將8個鍵值區分成2組。
第1組鍵值={d[0]、d[2]、d[4]、d[6]}={21、18、88、88*}。 第2組鍵值={d[1]、d[3]、d[5]、d[7]}={66、83、55、99}。 使用插入排序法分別對第1組、第2組鍵值進行排序，結果為： 第1組鍵值={18、21、88、88*}。 第2組鍵值={55、66、83、99}。 資料結構導論 - C語言實作
33
8.3.4. 謝耳排序法(Shell Sort) 第3回合，令s=s-1=2-1=1，直接用插入排序法對陣列d的鍵值排序，得到：
資料結構導論 - C語言實作
34
8.3.5. 快速排序法(Quick Sort) 採用插入排序法將編號為0、1、2、...、n-1的n筆記錄按照「鍵值不遞減」的順序加以排列的步驟如下： 步驟1：將n筆紀錄的鍵值儲存到陣列d[n]中，其中d[0]儲存第0號紀錄的鍵值、d[1]儲存第1號紀錄的鍵值、…、d[n-1]儲存第n-1號紀錄的鍵值。 步驟2：設d[low]至d[high]為本次待排序的資料範圍(low < high)。 令K= d[low]。 步驟3：從左(d[low+1])向右(d[high])找出一個鍵值Ki=d[i]，滿足Ki K。(若Ki不存在，則令i=high+1)。 資料結構導論 - C語言實作
35
8.3.5. 快速排序法(Quick Sort) 步驟4：從右(d[high])向左(d[low])找出一個鍵值Kj=d[j]，滿足Kj ≤ K。(若Kj不存在，則令j=low)。 步驟5：若i < j，則將Ki 與Kj交換，然後跳到步驟2。 步驟6：若i j則將K與Kj交換，並以j為分割點將待排序的鍵值範圍(d[low]至d[high])分割成左右兩半，即： 左半邊 = {d[low]、d[low+1]、d[low+2]、...、 d[j-1]}。 右半邊 = {d[j+1]、d[j+2]、d[j+3]、...、 d[high]}。 步驟7：再分別針對左右兩半邊遞迴地執行步驟2-6，直到low = high(即只剩下一個鍵值)為止。 步驟8：列印出陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-1]之值。 資料結構導論 - C語言實作
![快速排序法(Quick Sort) 步驟4：從右(d[high])向左(d[low])找出一個鍵值Kj=d[j]，滿足Kj ≤ K。(若Kj不存在，則令j=low)。 步驟5：若i < j，則將Ki 與Kj交換，然後跳到步驟2。](http://slidesplayer.com/slide/15528747/93/images/35/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%B3%95%28Quick+Sort%29+%E6%AD%A5%E9%A9%9F4%EF%BC%9A%E5%BE%9E%E5%8F%B3%28d%5Bhigh%5D%29%E5%90%91%E5%B7%A6%28d%5Blow%5D%29%E6%89%BE%E5%87%BA%E4%B8%80%E5%80%8B%E9%8D%B5%E5%80%BCKj%3Dd%5Bj%5D%EF%BC%8C%E6%BB%BF%E8%B6%B3Kj+%E2%89%A4+K%E3%80%82%28%E8%8B%A5Kj%E4%B8%8D%E5%AD%98%E5%9C%A8%EF%BC%8C%E5%89%87%E4%BB%A4j%3Dlow%29%E3%80%82+%E6%AD%A5%E9%A9%9F5%EF%BC%9A%E8%8B%A5i+%3C+j%EF%BC%8C%E5%89%87%E5%B0%87Ki+%E8%88%87Kj%E4%BA%A4%E6%8F%9B%EF%BC%8C%E7%84%B6%E5%BE%8C%E8%B7%B3%E5%88%B0%E6%AD%A5%E9%A9%9F2%E3%80%82.jpg "步驟6：若i j則將K與Kj交換，並以j為分割點將待排序的鍵值範圍(d[low]至d[high])分割成左右兩半，即： 左半邊 = {d[low]、d[low+1]、d[low+2]、...、 d[j-1]}。 右半邊 = {d[j+1]、d[j+2]、d[j+3]、...、 d[high]}。 步驟7：再分別針對左右兩半邊遞迴地執行步驟2-6，直到low = high(即只剩下一個鍵值)為止。 步驟8：列印出陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-1]之值。 資料結構導論 - C語言實作.")
36
8.3.5. 快速排序法(Quick Sort) 【例1】快速排序法
假設有一組未經排序的資料R0、R1、R2、...、R7，其鍵值 {83，66，55，21，88，18，88*，99} 已經儲存到一維陣列d[8]中。 如果我們採用「快速排序法」來將該組資料依「鍵值不遞減」的順序排序，每一回合排序處理過程詳如表8.8所示。 資料結構導論 - C語言實作
37
8.3.5. 快速排序法(Quick Sort) 步驟1， 排序範圍為d[0]至d[7]，即low=0，high=7。
K=d[0]=83，從d[0]往右(d[7])找出 Ki K，結果找到Ki=K4=d[4]=88 83。 從d[7]往左(d[0])找出Kj ≤ K，結果找到Kj=K5=d[5]=18 ≤ 83。 因i < j，將Ki 與 Kj交換(即d[4]=88與d[5]=18交換)， 得到d[4]=18，d[5]=88。結果如表8.8步驟2所示。 資料結構導論 - C語言實作
![快速排序法(Quick Sort) 步驟1， 排序範圍為d[0]至d[7]，即low=0，high=7。](http://slidesplayer.com/slide/15528747/93/images/37/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%B3%95%28Quick+Sort%29+%E6%AD%A5%E9%A9%9F1%EF%BC%8C+%E6%8E%92%E5%BA%8F%E7%AF%84%E5%9C%8D%E7%82%BAd%5B0%5D%E8%87%B3d%5B7%5D%EF%BC%8C%E5%8D%B3low%3D0%EF%BC%8Chigh%3D7%E3%80%82.jpg "K=d[0]=83，從d[0]往右(d[7])找出 Ki K，結果找到Ki=K4=d[4]=88 83。 從d[7]往左(d[0])找出Kj ≤ K，結果找到Kj=K5=d[5]=18 ≤ 83。 因i < j，將Ki 與 Kj交換(即d[4]=88與d[5]=18交換)， 得到d[4]=18，d[5]=88。結果如表8.8步驟2所示。 資料結構導論 - C語言實作.")
38
8.3.5. 快速排序法(Quick Sort) 步驟2， 排序範圍還是d[0]至d[7]，即low=0，high=7。
K=d[0]=83，從d[0]往右(d[7])找出 Ki K，結果找到Ki=K5=d[5]=88 83。 從d[7]往左(d[0])找出Kj ≤ K，結果找到Kj=K4=d[4]=18 ≤ 83。 因i > j，將K 與 Kj交換(即d[0]=83與d[4]=18交換)， 得到d[0]=18，d[4]=83。結果如表8.8步驟3所示。 資料結構導論 - C語言實作
![快速排序法(Quick Sort) 步驟2， 排序範圍還是d[0]至d[7]，即low=0，high=7。](http://slidesplayer.com/slide/15528747/93/images/38/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%B3%95%28Quick+Sort%29+%E6%AD%A5%E9%A9%9F2%EF%BC%8C+%E6%8E%92%E5%BA%8F%E7%AF%84%E5%9C%8D%E9%82%84%E6%98%AFd%5B0%5D%E8%87%B3d%5B7%5D%EF%BC%8C%E5%8D%B3low%3D0%EF%BC%8Chigh%3D7%E3%80%82.jpg "K=d[0]=83，從d[0]往右(d[7])找出 Ki K，結果找到Ki=K5=d[5]=88 83。 從d[7]往左(d[0])找出Kj ≤ K，結果找到Kj=K4=d[4]=18 ≤ 83。 因i > j，將K 與 Kj交換(即d[0]=83與d[4]=18交換)， 得到d[0]=18，d[4]=83。結果如表8.8步驟3所示。 資料結構導論 - C語言實作.")
39
8.3.5. 快速排序法(Quick Sort) 步驟3， 其餘詳細步驟，請參閱課本表8.8
以d[j]=d[4]=83為分割點，將待排序的資料範圍分割成左半邊(即d[0]到d[3])和右半邊(即d[5]到d[7])， 結果如表8.8步驟3所示。 其餘詳細步驟，請參閱課本表8.8 資料結構導論 - C語言實作
40
8.3.5. 快速排序法(Quick Sort) 資料結構導論 - C語言實作
41
資料結構導論 - C語言實作
42
8.3.6. 樹排序法 (Tree Sort) 二元搜尋樹(Binary Search Tree)
二元搜尋樹中的任一節點其左子樹的節點鍵值一定比它小 其右子樹的節點鍵值一定大於或等於它 資料結構導論 - C語言實作
43
8.3.6. 樹排序法 (Tree Sort) 採用樹排序法將編號為0、1、2、...、n-1的n筆記錄按照「鍵值不遞減」的順序加以排列的步驟如下： 步驟1：輸入n筆鍵值，以鍵值為樹的節點來建造一棵二元搜尋樹。即： 以第1個輸入的鍵值為樹根。 對於第2個鍵值到第n個鍵值執行下列動作： a. 從樹根開始比較大小，若比樹根小 則往左子樹繼續比較，否則往右子 樹繼續比較。 b. 當遇到樹葉節點，若比樹葉節點小 則放在左子樹，否則放在右子樹。 步驟2：以中序法追蹤所得即為按鍵值不遞減之排序結果。 資料結構導論 - C語言實作
44
8.3.6. 樹排序法 (Tree Sort) 【例1】樹排序法(Tree Sort)
假設有一組未經排序的資料R0、R1、R2、...、R7，其鍵值為： {83，66，55，21，88，18，88*，99}。 步驟1，輸入鍵值 {83，66，55，21，88，18，88*，99}， 並建造出一棵二元搜尋樹。 資料結構導論 - C語言實作
45
8.3.6. 樹排序法 (Tree Sort) 資料結構導論 - C語言實作
46
8.3.6. 樹排序法 (Tree Sort) 步驟2，用中序法追蹤二元搜尋樹即可得到按鍵值不遞減之排序結果，即：
18、21、55、66、83、88、88*、99 資料結構導論 - C語言實作
47
8.3.7. 堆積排序法(Heap Sort) 完整二元樹須滿足以下條件： 完整二元樹是一棵二元樹。
完整二元樹的建立須先有左子樹然後才有右子樹。 完整二元樹的樹葉節點，頂多相差1個階度。 資料結構導論 - C語言實作
48
8.3.7. 堆積排序法(Heap Sort) 圖8.7即是一個含有8個節點的完整二元樹
其中0、1、2、3、...、7為節點之編號，也是建造完整二元樹的順序，而 K0、K1、K2、K3、...、K7為樹中節點所儲存之鍵值。 資料結構導論 - C語言實作
49
8.3.7. 堆積排序法(Heap Sort) 堆積樹須滿足以下條件： 是一棵完整二元樹(或完滿二元樹)。
每一個節點之鍵值大於或等於其子節點之鍵值。 資料結構導論 - C語言實作
50
8.3.7. 堆積排序法(Heap Sort) 採用堆積排序法將編號為0、1、2、...、n-1的n筆記錄之鍵值{K0，K1，K2，…，Kn-1}，按照「鍵值不遞增」的順序加以排列的步驟如下： 步驟1：以鍵值{K0，K1，K2，…，Kn-1}建造出完整二元樹(如圖8.7之結構)，如果用陣列d[n]來儲存完整二元樹，則d[0]=K0，d[1]=K1，d[2]=K2，d[3]=K3，...，A[n-1]=Kn-1。 步驟2：將完整二元樹轉換成對應的堆積樹。 步驟3：將樹根砍下來並輸出樹根之鍵值。 資料結構導論 - C語言實作
51
8.3.7. 堆積排序法(Heap Sort) 步驟4：將堆積樹的最後一個節點(即編號最大的節點)搬到樹根位置成為新的樹根節點。
步驟5：如果只剩樹根節點則輸出樹根之鍵值，結束。否則，重建堆積樹，然後回到步驟3。 資料結構導論 - C語言實作
52
8.3.7. 堆積排序法(Heap Sort) 【例1】堆積排序法
假設有一組未經排序的資料R0、R1、R2、...、R7，其鍵值 {83，66，55，21，88，18，88*，99}， 我們要將這一組資料依照鍵值不遞增(Non-increasing Order)之順序加以排序，其過程如下： 資料結構導論 - C語言實作
53
8.3.7. 堆積排序法(Heap Sort) 步驟1： 以鍵值{83，66，55，21，88，18，88*，99}建造出一棵完整二元樹，即： 資料結構導論 - C語言實作
54
8.3.7. 堆積排序法(Heap Sort) 步驟2： 將完整二元樹轉換成對應的堆積樹。其方法是從樹根(節點0)開始，對於所有非樹葉節點，做以下處理： 步驟2.1： 檢查其鍵值是否大於或等於其左子樹根之鍵值，若是，則執行驟2.2，否則須與左子樹根之鍵值交換(對調)。 步驟2.2： 檢查其鍵值是否大於或等於其右子樹根之鍵值，若是，則執行驟2.3，否則須與右子樹根之鍵值交換。 步驟2.3： 檢查其鍵值是否大於其父節點之鍵值，若是，則須與父節點之鍵值交換(對調)，並繼續遵此原則追朔至樹根為止。 資料結構導論 - C語言實作
55
8.3.7. 堆積排序法(Heap Sort) 資料結構導論 - C語言實作
56
8.3.7. 堆積排序法(Heap Sort) 資料結構導論 - C語言實作
57
8.3.7. 堆積排序法(Heap Sort) 資料結構導論 - C語言實作
58
8.3.7. 堆積排序法(Heap Sort) 資料結構導論 - C語言實作
59
8.3.7. 堆積排序法(Heap Sort) 步驟3： 開始排序，參考圖8.10(1)，輸出樹根之鍵值99，然後將最後一號節點之鍵值21搬到樹根位置，成為圖8.10(2)。接著，重建堆積樹，就是將樹根節點之鍵值調整到正確的位置上，得到圖8.10(3)。 同樣地，輸出樹根之鍵值88，然後將最後一號節點之鍵值55搬到樹根位置，成為圖8.10(4)。接著，重建堆積樹，得到圖8.10(5)。 其餘排序過程詳如圖8.10(6)至圖8.10(13)。我們得到之排序結果為： 99、88、88*、83、66、55、21、18。 資料結構導論 - C語言實作
60
8.3.7. 堆積排序法(Heap Sort) 資料結構導論 - C語言實作
61
8.3.7. 堆積排序法(Heap Sort) 資料結構導論 - C語言實作
62
8.3.7. 堆積排序法(Heap Sort) 資料結構導論 - C語言實作
63
8.3.8. 合併排序法(Merge Sort) 2-路合併 3-路合併 ... k-路合併 資料結構導論 - C語言實作
64
8.3.8. 合併排序法(Merge Sort) 採用合併排序法將編號為0、1、2、...、n-1的n筆記錄按照「鍵值不遞減」的順序加以排列的步驟如下： 步驟1：將n筆記錄的鍵值儲存到陣列d[n]中，其中d[0]儲存第0號記錄的鍵值、d[1]儲存第1號記錄的鍵值、…、d[n-1]儲存第n-1號記錄的鍵值。將d[i]視為長度為1的鍵值。 步驟2：第i回合，將 個長度為i的鍵值，兩兩合併，成為 個長度為2i的鍵值組。 步驟3： i=i+1，重複執行步驟1，直到合併成1組長度為n的鍵值組為止。 步驟4：列印出陣列元素d[0]、d[1]、d[2]、d[3]、...、d[n-2]、d[n-i]之值。 資料結構導論 - C語言實作
65
8.3.8. 合併排序法(Merge Sort) 資料結構導論 - C語言實作
66
8.3.9. 基數排序法(Radix Sort) 【例1】2-路合併排序法
假設有一組未經排序的資料R0、R1、R2、...、R7，其鍵值{83，66，55，21，88，18，88*，99}已經儲存在一維陣列d[8]中，共計8個鍵值。 第1回合，{83}與{66}合併排序，{55}與{21}合併排序，{88}與{18}合併排序，{88*}與{90}合併排序。得到4組長度為2的鍵值組，即{66、83}、{21、55}、{18、88}、{88*、90}。 第2回合，{66、83}與{21、55}合併排序，{18、88}與{88*、90}合併排序。得到2組長度為4的鍵值組，即{21、55、66、83}、{18、88、88*、90}。 資料結構導論 - C語言實作
67
8.3.9. 基數排序法(Radix Sort) 又稱為「桶(箱)子」排序法。
根據待排序的鍵值之「個別位數(Digit)」進行處理以獲得排序的結果。 最有效鍵優先(Most Significant Digit First：MSD) 從鍵值最左邊的位數開始處理，採用 「分配」、「排序」、「收集」等三個步驟。 最無效鍵優先(Least Significant Digit First：LSD) 從鍵值最右邊的位數開始處理，採用 「分配」和「收集」兩個步驟。 資料結構導論 - C語言實作
68
8.3.9. 基數排序法(Radix Sort) 【例1】基數排序法－最無效鍵優先(LSD)，按「鍵值不遞減」排序
假設有一組未經排序的資料R0、R1、R2、...、R10、R11，其鍵值為： {185，66，221，88，700，88*，9，1，123，8765，917，2}。 第0號鍵值185，表示有三個位數，即1、8和5。 倒數第3個鍵值8765，則表示有四個位數，即8、7、6和5。 採用LSD排序法將上述鍵值按「鍵值不遞減」之順序來列的處理步驟如下： 資料結構導論 - C語言實作
69
8.3.9. 基數排序法(Radix Sort) 步驟1：準備好10個箱子，編號分別為0，1，2，…，9。
步驟2：(第1回合)依據鍵值的「個位數」將鍵值{185，66，221，88，700，88*，9，1，123，8765，917，2}一一「分配」到相同編號的箱子中： 資料結構導論 - C語言實作
70
8.3.9. 基數排序法(Radix Sort) 步驟3：依0，1，2，…，9號箱子的順序「收集」每個箱子內的鍵值，結果如下：
700，221，1，2，123，185，8765，66，917，88，88*，9 步驟4：(第2回合)依據鍵值的「十位數」將鍵值{700，221，1，2，123，185，8765，66，917，88，88*，9}一一「分配」到相同編號的箱子中： 資料結構導論 - C語言實作
71
8.3.9. 基數排序法(Radix Sort) 步驟5：依0，1，2，…，9號箱子的順序「收集」每個箱子內的鍵值，結果如下：
700，1，2，9，917，221，123，8765，66，185， 88，88* 步驟6：(第3回合)依據鍵值的「百位數」將鍵值{700，1，2，9，917，221，123，8765，66，185，88，88*}一一「分配」到相同編號的箱子中： 資料結構導論 - C語言實作
72
基數排序法(Radix Sort) 步驟7：依0，1，2，…，9號箱子的順序「收集」每個箱子內的鍵值，結果如下： 1，2，9，66，88，88*，123，185， 221，700，8765，917 步驟8：(第4回合)依據鍵值的「千位數」將鍵值{1，2，9，66，88，88*，123，185，221，700，8765，917}一一「分配」到相同編號的箱子中，所得之結果如下： 資料結構導論 - C語言實作
73
基數排序法(Radix Sort) 資料結構導論 - C語言實作
74
基數排序法(Radix Sort) 步驟9：依0，1，2，…，9號箱子的順序「收集」每個箱子內的鍵值，結果如下： 1，2，9，66，88，88*，123，185， 221，700，917，8765 資料結構導論 - C語言實作
75
8.3.9. 基數排序法(Radix Sort) 【例2】基數排序法－最有效鍵優先(MSD)，按「鍵值不遞減」排序
假設有一組未經排序的資料R0、R1、R2、...、R10、R11，其鍵值為： {18，66，55，61，21，88，10，88*，99，91，28，51}。 採用MSD排序法將上述鍵值按「鍵值不遞減」之順序來列的處理步驟如下： 資料結構導論 - C語言實作
76
8.3.9. 基數排序法(Radix Sort) 步驟1：準備好10個箱子，編號分別為0，1，2，…，9。
步驟2：(第1回合)依據鍵值的「十位數」將鍵值{18，66，55，61，21，88，10，88*，99，91，28，51}一一「分配」到相同編號的箱子中： 資料結構導論 - C語言實作
77
8.3.9. 基數排序法(Radix Sort) 步驟3：將每一號箱子內之鍵值，分別利用插入法排序按鍵值不遞減排序，所得到的結果如下：
步驟4：依0，1，2，…，9號箱子的順序「收集」每個箱子內的鍵值，結果如下： 10，18，21，28，51，55，61，66，88， 88*，91，99 資料結構導論 - C語言實作
78
8.3 外部排序法(External Sort) 當待排序的鍵值數量大到超過記憶體的容量時
須借助於磁碟、磁帶等輔助記憶體來暫存排序過程中的部分結果。 這種利用外部儲存媒體的排序動作為「外部排序」。 k-路合併排序法。 資料結構導論 - C語言實作
79
8.4 效益評估 排序法大都脫離不了三個基本動作： 衡量因素： 比較。 交換位置。 重新分配位置。 最壞的情況下所須的時間(或比較次數)。
平均情況下所須的時間(或比較次數)。 排序過程中所須要的額外記憶體空間。 資料結構導論 - C語言實作
80
8.4 效益評估 各種排序法都有其優點與缺點： 快速排序法雖然處理速度非常快，但在最壞的情況下排序的效率與氣泡浮昇排序法、挑選排序法、插入排序法都是O(n2)。 氣泡浮昇排序法、挑選排序法、插入排序法的效率都不是很好，但程式很容易撰寫，當鍵值數量較少或部份鍵值已經排序好時效果也不差。 資料結構導論 - C語言實作
81
8.4 效益評估 各種排序法都有其優點與缺點： 基數排序法的LSD排序方式，平均而言效益最佳，但不適合負數之排序。而其最大的缺點是須要許多額外的記憶體空間，不信的話可以拿文字串來排序看看。 堆積排序法在最壞的情況下優於快速排序法。但在平均情況下比快速排序法稍慢一些，因為第一次建立堆積樹須額外花費一些時間。又快速排序法所須的額外記憶體多於堆積排序法。 資料結構導論 - C語言實作
82
8.4 效益評估 資料結構導論 - C語言實作
83
8.4 效益評估 資料結構導論 - C語言實作
Similar presentations
