第 十 章 排序(Sorting) 課程名稱：資料結構 授課老師：________ 2019/4/20
本章學習目標 1.讓讀者了解各種排序的方法與適用時機。 2.讓讀者了解排序的意義與分類。 2019/4/20
本章內容 10-1 排序(Sorting) 10-2 氣泡排序法(Bubble Sort) 10-3 選擇排序法（Selection Sort） 10-4 插入排序 ( Insertion Sort ) 10-5 快速排序 ( Quick Sort ) 10-6 堆積排序 ( Heap Sort ) 10-7 謝耳排序 ( Shell sort ) 10-8 合併排序 ( Merge Sort ) 10-9 基數排序 ( Radix Sort ) 2019/4/20
10-1 排序(Sorting) 所謂排序(Sorting)就是將一組資料依使用者的需要予以重新安排其順序。而資料在經過排序之後，其優點為容易閱讀、利於統計分析及可以快速搜尋所要的資料等等。如果我們將排序的方式應用在「資料庫系統」中，可分為兩種，一種是由小至大的遞增(Ascending)排序，另一種是由大至小的遞減(Descending)排序。在「資料結構」課程中，排序法可分為兩大類： 第一類：內部與外部排序法 第二類：穩定與不穩定排序 2019/4/20
第一類：內部與外部排序法 1.內部排序法(Internal Sort)：又稱為「陣列排序」 【定義】排序的工作是在主記憶體(RAM)內完成。 【適用時機】資料量較少者。 2.外部排序法(External Sort)：又稱為「檔案排序」 【定義】排序的工作是在輔助記憶體內完成。 【適用時機】資料量較大者。 2019/4/20
第二類：穩定與不穩定排序 1.穩定排序(Stable Sorting) 如果鍵值相同之資料在排序後的相對位置和排序前相同時，則稱為穩定排序。 【例如】 (1)排序前：3,5,19,1,3+,10 (兩個相同鍵值3，故第二個鍵值3寫成3+) (2)排序後：1,3,3+,5,10,19 (因為兩個3的相對位置在排序前後是相同的) 2.不穩定排序(UnStable Sorting) 如果鍵值相同之資料在排序後的相對位置和排序前是不相同時，則稱為不穩定 排序。 (2)排序後：1,3+,3,5,10,19 (因為兩個3的相對位置在排序前後是不相同的) 2019/4/20
表10-1 各種排序的比較 排序方式 最壞時間 平均時間 穩定度 額外空間 備註說明 氣泡排序 (Bubble Sort) O( n2 ) 選擇排序 (Selection Sort) 不穩定 插入排序 (Insertion Sort) 大部份已排序者較好 薛爾排序 (Shell Sort) O( ns ) 1<s<2 O(n log2 n) s是分組 快速排序 (Quick Sort) O(n log2 n ) O( log n ) ~ O( 1 ) n大時較好 堆積排序 (Heap Sort) 合併排序 (Merge Sort) O( N ) 常用於外部排序 基數排序 (Radix Sort) O (n logr B ) O(n logbk) ~O( n ) O ( n * b ) k:箱子個數 b:基數 2019/4/20
10-2 氣泡排序法(Bubble Sort) 在日常生活中，我們常常會根據某些要求做簡單的排序，而在資料結構中最普遍也最簡單的應該就是氣泡排序法。所謂氣泡排序法(Bubble Sort) 就是將兩個相鄰的資料相互做比較，若比較時發現次序不對，則將兩資料互換，依次由上往下比，而結果則會依次由下往上浮起，猶如氣泡一般。 2019/4/20
【分析】 1. 比較之回合次數=資料個數-1 2. 在每一回合之後，至少會有一個資料可以排列到正確位置， 1. 比較之回合次數=資料個數-1 2. 在每一回合之後，至少會有一個資料可以排列到正確位置， 再進行下一個回合的排列時，便可以減少此資料的比較。 3. 時間複雜度：最壞情況與平均情況都是O( n2 )。 4. 需要一個額外空間。 5. 為一種穩定排序 ( stable sorting ) 。 6. 當資料量較小時，使用氣泡排序法效果效佳。 2019/4/20
【原理】 逐次比較兩個相鄰的資料，按照排序的條件交換位置，直到全部資料依序排好為止。其排序過程如圖10-1所示： 2019/4/20
2019/4/20
氣泡排序法的演算法如下： 2019/4/20
請利用氣泡排序法由小至大來寫出排序的過程。 【老師上課動態展示】檔案在附書光碟中。 輸入資料：3, 7, 9, 6, 8, 5 請利用氣泡排序法由小至大來寫出排序的過程。 2019/4/20
10-3 選擇排序法（Selection Sort） 2019/4/20
【分析】 1. 時間複雜度：最壞情況與平均情況都是O(n2) 2. 需要暫存一筆記錄的額外空間。 3. 是一種不穩定排序。 4. 資料量愈小，選擇排序法的效果愈好。 2019/4/20
【原理】 第一回合由資料中選取最大的資料和第一個資料對調、第二回合由資料中選取第二大的資料和第二個資料對調(因最大的資料已排到第一個位置)、依此循環直到最後一個資料，即完成資料的排序。 2019/4/20
其排序過程如圖10-2所示： 2019/4/20
選擇排序法的演算法如下： 2019/4/20
【老師上課動態展示】檔案在附書光碟中。 輸入資料：25,57,48,37,12,92,86,33 請利用選擇排序法由大至小來寫出排序的過程。 2019/4/20
10-4 插入排序 ( Insertion Sort ) 【定義】每一次往後拿一筆記錄，插入到前面已經排序好的記錄，亦即是插入一個記錄 R在一堆已排序的記錄(R1,R2,R3 ,...., Ri)中。像是玩樸克一樣，我們將牌分作兩堆(第一堆為已排序，第二堆則尚未排序)，每次從第二堆牌中抽出第一張牌，然後插入到第一堆牌的適當位置。如圖10-3所示。 2019/4/20
【分析】 1. 時間複雜度：最壞情況與平均情況都是O( n2 ) 。 2. 只需一個額外的空間，所以空間複雜度為最佳。 3. 是穩定排序 ( stable ) 。 4. 此排序法適用於大部份資料已經過排序或已排序資料庫新增資料 後進行排序。 2019/4/20
【原理】 插入排序法(Insert Sort)是將陣列中的元素，逐一與已排序好的資料作比較，再將該陣列元素插入適當的位置。其排序過程如下所示： 原始資料：7 5 9 8 4 3 2019/4/20
插入排序法的演算法如下： 2019/4/20
【老師上課動態展示】檔案在附書光碟中。 輸入資料：25,57,48,37,12,92,86,33 請利用選擇排序法由小至大來寫出排序的過程。 2019/4/20
10-5 快速排序 ( Quick Sort ) 【定義】 快速排序法又稱分割交換排序法，其觀念是先在資料中找到一個中間值，把小於中間值的資料放在左邊而大於中間值的資料放在右邊，再以同樣的方式分別處理左右兩邊的資料，直到完成為止。 2019/4/20
【分析】 1. 時間複雜度：最壞情況為 O( n2 ) 與平均情況為O( n log2 n ) 。 2. 快速排序法是平均執行時間最快的內部排序法。 3. 需要額外的堆疊 ( stack ) 空間。 4. 是一種不穩定排序 ( stable ) 。 2019/4/20
【作法】 1. 取第一個記錄的鍵值 K0 當作中間值 。 2. 由左而右，找到第一個 Ki，使得Ki≧K0。 由右而左，找到第一個Kj，使得 Kj ≦K0。 <亦即從左找比它大，從右找比它小的數字> ３. 若 i < j 則 Ki 與Kj 對調位置，並繼續執行步驟2. 否則，K0與 Kj 對調位置，此時以j為基準點將此記錄資料串列分為左右 兩部份。並以遞迴方式分別為左右兩半進行排序，直至完成排序。 2019/4/20
其排序過程如下所示： 原始資料：26,5,37,1,61,11,59,15,48,19 2019/4/20
2019/4/20
2019/4/20
快速排序法的演算法如下： 2019/4/20
10-6 堆積排序 ( Heap Sort ) 【定義】 堆積排序法是選擇排序法的改良版，目的是為了減少選擇排序法的比較次數。而堆積排序法就是利用堆積樹的樹根與最後一個節點交換，再重新建立堆積樹，直到只剩下最後一個節點為止，排序也完成了。 2019/4/20
【特性】 1.堆積樹是一棵完整二元樹(Complete Binary Tree)。 2. 每一個節點之值均大於或等於它的兩個子節點之值。 2019/4/20
【分析】 1. 時間複雜度：最壞情況與平均情況都是O( n log n ) 。 2. 為一種不穩定排序。 3. 只需要一個額外的記錄空間。 2019/4/20
【作法】 將原始資料( x1 , x2 , x3 , ... , xn )轉換成完整二元樹。如下圖所示 2. 將完整二元樹化為堆積樹 ( heap tree ) 。 3. 輸出樹根鍵值。 4. 將樹中最後一個節點搬到樹根。 5. 重覆步驟 2 到 4，直到輸出所有鍵值為止。 2019/4/20
堆積排序法的演算法如下： 2019/4/20
【舉例】 假設一個尚未排序的陣列(unsorted array)中包含下列整數： 45,83,7,61,12,99,44,77,14,29 (1)建立完整二元樹(Complete binary tree) (2)將完整二元樹轉換成堆積樹 (3)堆積排序(Heap sort) 2019/4/20
(1)建立完整二元樹(Complete binary tree) 2019/4/20
(2)將完整二元樹轉換成堆積樹 2019/4/20
2019/4/20
(3)堆積排序(Heap sort) 2019/4/20
2019/4/20
2019/4/20
2019/4/20
2019/4/20
【老師上課動態展示】檔案在附書光碟中。 2019/4/20
10-7 謝耳排序 ( Shell sort ) 【定義】由D.L. Shell所提出，方法是插入排序法演進而來，其目的是用來減少插入排序法中元素搬移的次數，增快排序的速度。 利用某一變數的間隔來比對其相間隔的元素。 n個元素排序，初始間隔是 Gap = ，開始時是第i個與第 i + Gap個進行比較，若第i個元素較大，則兩元素互換，反之則不互換。每排序一次之後，Gap的值必須減半，重覆操作直到 Gap = 0 就停止，表示已經排序完成。 2019/4/20
【舉例】 原始資料：5 9 6 3 4 2 1 7 8 2019/4/20
2019/4/20
2019/4/20
【特性】 1. 時間複雜度：最壞情況為O( Ns )，平均情況為O( n ( log n ) 2 ) 。 2. 是穩定排序( stable ) 2019/4/20
【牛刀小試】 輸入資料：26 5 37 1 61 11 59 15 48 19 4 請利用謝耳排序法由小至大來寫出排序的過程。 輸入資料：26 5 37 1 61 11 59 15 48 19 4 請利用謝耳排序法由小至大來寫出排序的過程。 2019/4/20
謝耳排序法的演算法如下： 2019/4/20
【老師上課動態展示】檔案在附書光碟中。 2019/4/20
10-8 合併排序 ( Merge Sort ) 【定義】 合併排序適用於內部排序和外部排序，也是一種典型的「分而治之」的方法，將 N 筆記錄依鍵值順序排序的方法為： 1. 將 N個長度為 1 的鍵值成對地合併長度為 2 的鍵值組。 2. 將 N/2個長度為 2 的鍵值成對地合併長度為 4 的鍵值組。 3. 將鍵值組成對地合併，直到合併成一組長度為 N 的鍵值組為止。 如圖10-5所示。 圖10-5 合併排序法的過程 2019/4/20
【特性】 1. 時間複雜度：最壞情況與平均情況均為O( n log n ) 。 2. 為一穩定排序 ( stable sorting ) 。 2019/4/20
【老師上課動態展示】檔案在附書光碟中。 2019/4/20
【隨堂練習 1】 輸入資料：25,57,48,37,12,92,86,33 請利用合併排序法由小至大來寫出排序的過程。 2019/4/20
【隨堂練習 2】 輸入資料：37,57,32,23,15 請利用合併排序法由小至大來寫出排序的過程。 2019/4/20
10-9 基數排序 (Radix Sort ) 【定義】 先將n筆數字資料依個位數來加以分類，並分別放入由數字0,1,2,...9 的暫存陣列Temp[10][n]中，再由數字的順序放回原陣列。則此時的 資料已依個位數大小由小到大排序。 2. 將n筆數字資料依十位數來加以分類，並分別放入由數字0,1,2,...9的 暫存陣列Temp[10][n]中，再由數字的順序放回原陣列。則此時的資 料已依十位數和個位數大小由小到大排序。 3. 同理再作百位數、千位數、...即可得由小到大排序好的數字。 2019/4/20
【作法】 假設 r 為基底 (Base, 或稱進制)，則必須要準備 r 個 Buckets， 編號為 0 ~ n-1 2. 假設 d 為n筆資料中的最大鍵值之位數個數，則須執行 d 回合才能 完成 Sort 工作 3. 從最低位數到最高位數，其每一回合必須要完成以下的程序： (1)分配：依位數值，將資料分配到對應的 Bucket 中 (2)合併：指合併 r 個 Buckets (從 0 ~ n-1) 2019/4/20
基數排序法的演算法如下： 2019/4/20
【實例】 將下列數字以LSD Radix Sort加以排序 (Base = 10) 79, 8, 6, 93, 59, 84, 55, 9, 71, 33 (1) Base = 10, ∴準備 10個桶子，編號為 0 ~ 9 (2) 最大的數值是93，有二個位數，∴d = 2，同時可知道需執行 2 個回合才會完成 Sort 工作 (3) 從最低位數 (個位數) 開始執行各回合 2019/4/20
2019/4/20
【老師上課動態展示】檔案在附書光碟中。 2019/4/20