Download presentation
Presentation is loading. Please wait.
1
本教學投影片係屬教科書著作之延伸，亦受著作權法之保護。
請依出版社授權使用規範利用本教學資源，非經授權許可不得以影印、拷貝、列印等方法進行重製，亦不得改作、公開展示著作內容，亦請勿對第三人公開傳輸、散布。 戴顯權 著 / 資料結構 © 滄海圖書
2
Chapter 6 排序 戴顯權 著 / 資料結構 © 滄海圖書
3
本章內容 6.1 為什麼要排序？ 6.2 泡沫排序法 6.3 插入排序法 6.4 選擇排序法 6.5 快速排序法 6.6 合併排序法
6.1 為什麼要排序？ 6.2 泡沫排序法 6.3 插入排序法 6.4 選擇排序法 6.5 快速排序法 6.6 合併排序法 6.7 堆積排序法 6.8 基數排序法 6.9 各種內部排序法的比較 與選擇 6.10 外部排序法 戴顯權 著 / 資料結構 © 滄海圖書
4
排序 就是把一堆資料或紀錄根據某一個鍵值，由小到大 或由大到小排列，其方法大致可分為三類：
(1) 簡單排序技術 (2) 高等排序技術 (3) 基數排序技術 三者所需的計算時間在輸入資料量很大時會有相當 大的差異 戴顯權 著 / 資料結構 © 滄海圖書
5
排序 若依待排序資料的儲存位置來區分，排序法又可以 分成兩種：
如果我們想要排序的資料物件都存在主記憶體中，那麼就 稱為內部排序(internal sort) 如果要排序的資料是在檔案裡，則稱為外部排序(external sort) 戴顯權 著 / 資料結構 © 滄海圖書
6
為什麼要排序？ 物件的搜尋 排序是針對同類物件(相同格式的資料) 的一種常見處理， 它的目的是要讓這些物件依照某種特性
例如當中某一個特定屬性的值，呈現有規律地排列 戴顯權 著 / 資料結構 © 滄海圖書
7
物件的搜尋 圖6.1 是一批學生的資料物件，它包含了許多筆學生 紀錄(record)，而每一筆紀錄又包含六個屬性 (attribute)，它們是每位學生的學號、姓名、年級、 班級、性別，以及電話，分別存在資料表格的六個 欄位(field) 中 戴顯權 著 / 資料結構 © 滄海圖書
8
物件的搜尋 我們可根據「某些線索」，找到其中一位或多位學 生的所有基本資料，而所使用的線索往往就是其中 一個欄位的屬性值
尋找的過程，則稱為搜尋(search)。通常用來搜尋的 欄位多半是具有識別性的，也就是它最多只會出現 在其中一個資料紀錄中，否則就會找出許多筆不是 我們想要的資料，這個欄位特別稱為鍵值(key) 戴顯權 著 / 資料結構 © 滄海圖書
9
循序搜尋法 搜尋的動作就是去比對所有可能物件中的特定欄位 值，若沒有預先對物件的排列順序進行適當地處理， 那麼我們要找的物件便可能會出現在任何位置 為了避免漏掉任何一個可能性，最簡單的方法就是 從頭一筆一筆地進行比對，直到找到符合所需的資 料為止，這就是所謂的循序搜尋法(sequential search) 戴顯權 著 / 資料結構 © 滄海圖書
10
循序搜尋法 假設有一串以任意順序出現的數字：5, 96, 21, 67, 55, 87, 12, 30
假設有一串以任意順序出現的數字：5, 96, 21, 67, 55, 87, 12, 30 如果我們想找出21 的話，得比對3 次 如果要找12 的話，得比對7 次 如果是要確認25 並不存在於此數列中，那麼我們必 須比對過數列中的每一筆資料後，才能確定當中並 沒有25，由於這個數列一共有8 筆資料，因此每當要 搜尋的數字不在該數列中，就必須進行8 次的比對 戴顯權 著 / 資料結構 © 滄海圖書
11
循序搜尋法 所需要的比對次數跟要搜尋的數字大小無關
但如果我們把整個數列先由小到大重新排列，那麼 數列會變成：5, 12, 21, 30, 55, 67, 87, 96 這時候若要尋找21，只需從頭比對3 次；尋找12 只 需2 次；要確認25 並不在數列中，則只需要4 次 比對到30 就知道結果了，因為後面的數值都比30 大， 當然不可能有25 戴顯權 著 / 資料結構 © 滄海圖書
12
循序搜尋法 當我們要尋找或確認的數字比較大的時候，也可以 選擇從後面找回來
平均起來，我們搜尋一筆資料所需要的比對次數會 是沒排序過的情況的一半 事實上，若是先把整個數列排序好，並且用陣列結 構來儲存資料，則我們還可以使用更有效率的二元 搜尋法(binary search) 來進行搜尋 戴顯權 著 / 資料結構 © 滄海圖書
13
戴顯權 著 / 資料結構 © 滄海圖書
14
戴顯權 著 / 資料結構 © 滄海圖書
15
戴顯權 著 / 資料結構 © 滄海圖書
16
戴顯權 著 / 資料結構 © 滄海圖書
17
戴顯權 著 / 資料結構 © 滄海圖書
18
排序的穩定性 假設我們容許原始資料中有兩筆或兩筆以上的資料 具有相同的鍵值
當我們做完資料的排序後，若是這兩筆資料仍然保 持它們原先的順序而沒有互換，我們就稱它為穩定 (stable) 排序；反之，則稱為不穩定(unstable) 排序 戴顯權 著 / 資料結構 © 滄海圖書
19
資料搬動的方法 讓整個資料紀錄跟著鍵值一起實際搬動 戴顯權 著 / 資料結構 © 滄海圖書
20
資料搬動的方法 只更改指標陣列中各 個指標所紀錄的資料 所在位置 戴顯權 著 / 資料結構 © 滄海圖書
21
泡沫排序法的原理與分析 泡沫排序法(bubble sort) 堪稱是最簡單的一種排序方 法，它會反覆地從紀錄串列的開頭往後進行掃描， 且每一次的掃描過程中，會一個一個地連續比較相 鄰的兩筆資料：如果前面的資料比後面的大，兩者 就交換位置，較大的那個再跟下一個資料比較；這 樣的動作持續做到尾端才停止 泡沫排序法是以「交換」的方式來逐步修正資料的 排列順序，也屬於交換排序法(interchange sort) 的一 種 戴顯權 著 / 資料結構 © 滄海圖書
22
https://en.wikipedia.org/wiki/Bubble_sort
戴顯權 著 / 資料結構 © 滄海圖書
23
戴顯權 著 / 資料結構 © 滄海圖書
24
戴顯權 著 / 資料結構 © 滄海圖書
25
戴顯權 著 / 資料結構 © 滄海圖書
26
戴顯權 著 / 資料結構 © 滄海圖書
27
插入排序法的原理與分析 插入排序法(insertion sort) 的過程就類似於玩牌的人 在發牌過程中，對剛上手之新牌所做的排列動作： 一開始手上並沒有牌，爾後每拿到一張新牌，就把 它插入到手上牌堆中的正確位置，逐一將所有的牌 都排序好 只不過電腦不像人類這麼聰明，看一眼就知道新牌 該插入哪裡；它必須將新拿到的牌依序與前面已經 排好的牌一張一張做比較 戴顯權 著 / 資料結構 © 滄海圖書
28
https://en.wikipedia.org/wiki/Insertion_sort
戴顯權 著 / 資料結構 © 滄海圖書
29
戴顯權 著 / 資料結構 © 滄海圖書
30
戴顯權 著 / 資料結構 © 滄海圖書
31
戴顯權 著 / 資料結構 © 滄海圖書
32
選擇排序法的原理與分析 先在所有n 筆資料中挑出最小的，並與第一個位置的 資料交換位置；然後再從剩下來的n – 1 筆資料中挑 選出最小的，來與第二個位置的資料對調……，以 此類推，直到全部的資料都就正確位置為止。也是 屬於交換排序法中的一種 第一次選擇的範圍大小為n，之後每次的範圍都較前 一次少1 個元素，直到最後僅剩一個元素為止，總共 需選擇n – 1 次 戴顯權 著 / 資料結構 © 滄海圖書
33
選擇排序法的原理與分析 https://en.wikipedia.org/wiki/Selection_sort
戴顯權 著 / 資料結構 © 滄海圖書
34
戴顯權 著 / 資料結構 © 滄海圖書
35
戴顯權 著 / 資料結構 © 滄海圖書
36
戴顯權 著 / 資料結構 © 滄海圖書
37
戴顯權 著 / 資料結構 © 滄海圖書
38
快速排序法的原理與分析 快速排序法(quick sort) 就是一種「可能」加快排序 速度的方法
所採用的是一種稱為各個擊破(divide and conquer) 的設計概念：也就是先設法將要排序的資料紀錄分 為前、後兩個數量較少的集合，然後再分別套用同 樣的方法來處理這兩個集合；當兩個集合都完成排 序時，即完成所有資料紀錄的排序 戴顯權 著 / 資料結構 © 滄海圖書
39
快速排序法的原理與分析 它的原理很簡單：由於我們在將所有元素分為兩部 分時，會選出一個樞紐值(pivot) 放在兩部分的中間， 讓前半部的所有元素鍵值都不大於它、而後半部的 任何一個元素鍵值都不小於它，如此等於已經依照 大小把兩個集合分割好了，只要再分別把前半部及 後半部個別排序好，就等於完成所有元素的排序 戴顯權 著 / 資料結構 © 滄海圖書
40
快速排序法的原理與分析 在快速排序法裡，我們先從待排序的紀錄中選擇一 個樞鈕值
接下來利用比較與交換兩種動作，把待排序的紀錄 重新排列，使得在樞鈕左方的資料值都小於或等於 樞鈕；而在樞鈕右方的資料值則都大於或等於樞鈕 最後，樞鈕左方的資料以及樞鈕右方的資料再分別 以同樣的方法獨立地做排序 這個「同樣的方法」，即是一種稱為遞迴(recursive) 戴顯權 著 / 資料結構 © 滄海圖書
41
圖6.7 快速排序法之範例 i j i j j i 戴顯權 著 / 資料結構 © 滄海圖書
42
i j i j j i j i j i j i i j 戴顯權 著 / 資料結構 © 滄海圖書
43
快速排序法的原理與分析 假設當次要排序的範圍內有n 筆資料，其值為Ql, Ql+1, …, Qr (一開始 l = 0、r = l + n – 1)： 如果n = 1，return； 令樞鈕值K 為第一筆資料的值(Ql)； 由左向右找出一筆資料Qi，使得Qi > K。找不到時，令Qi 為最後一筆資料(即Qr)。 由右向左找出一筆資料Qj，使得Qj < K。但僅檢查到位 置j 以前。 戴顯權 著 / 資料結構 © 滄海圖書
44
快速排序法的原理與分析 如果i < j，那麼把Qi 與Qj 交換，並且跳到步驟3；
如果i = j 而且Qj > K，那麼把j 再左移一個位置。執行到 這裡表示j 與j 之後的資料全都與K 比對過，不會小於K 了。 把K 與Qj 交換，並且以j 為基點把資料分割成左右兩部 分(不包含j 本身)，然後分別針對左右兩部分進行步驟1 ～步驟7。 戴顯權 著 / 資料結構 © 滄海圖書
45
戴顯權 著 / 資料結構 © 滄海圖書
46
戴顯權 著 / 資料結構 © 滄海圖書
47
戴顯權 著 / 資料結構 © 滄海圖書
48
戴顯權 著 / 資料結構 © 滄海圖書
49
戴顯權 著 / 資料結構 © 滄海圖書
50
戴顯權 著 / 資料結構 © 滄海圖書
51
合併排序法的原理與分析 合併排序法(merge sort) 的核心概念是：把已經排序 好的兩個較小數列合併成為一個較大的、排序好的 數列
合併排序法的執行過程一定要經過分割、個別排序 與合併這三個階段 戴顯權 著 / 資料結構 © 滄海圖書
52
合併排序法的原理與分析 將 n 個長度為 1 的數列，合併成 n/2 個長度為 2 的 數列
戴顯權 著 / 資料結構 © 滄海圖書
53
戴顯權 著 / 資料結構 © 滄海圖書
54
合併排序法之範例 戴顯權 著 / 資料結構 © 滄海圖書
55
合併排序法之範例 戴顯權 著 / 資料結構 © 滄海圖書
56
戴顯權 著 / 資料結構 © 滄海圖書
57
戴顯權 著 / 資料結構 © 滄海圖書
58
戴顯權 著 / 資料結構 © 滄海圖書
59
堆積排序法的原理與分析 堆積分為最大堆積與最小堆積兩種： 1. 最大堆積 2. 最小堆積 (1) 是一棵完整的二元樹。
(2) 每一個父節點的值都不小於子節點的值。 (3) 堆積裡的最大元素位於樹根。 2. 最小堆積 (1) 是一棵完整二元樹。 (2) 每一個父節點的值都不大於子節點的值。 (3) 堆積裡的最小元素位於樹根。 戴顯權 著 / 資料結構 © 滄海圖書
60
堆積排序法的原理與分析 假設現在有10 筆資料{10, 66, 30, 52, 61, 21, 3, 27, 55, 10+}，我們希望把它們組 成最小堆積，採取的步驟 是： 第1 步 先把它們放入二元樹中 戴顯權 著 / 資料結構 © 滄海圖書
61
堆積排序法的原理與分析 第2 步 調整成為如圖6.10 所示 的最小堆積 戴顯權 著 / 資料結構 © 滄海圖書
62
堆積排序法的原理與分析 第3 步 重複地「從樹的頂端彈出 最小的元素」，以及「重 新調整剩下的二元樹，使 其再度成為最小堆積」這 兩個步驟，直到最小堆積 中的元素個數減為0 為止 戴顯權 著 / 資料結構 © 滄海圖書
63
堆積排序法的原理與分析 戴顯權 著 / 資料結構 © 滄海圖書
64
堆積排序法的原理與分析 戴顯權 著 / 資料結構 © 滄海圖書
65
堆積排序法的原理與分析 戴顯權 著 / 資料結構 © 滄海圖書
66
戴顯權 著 / 資料結構 © 滄海圖書
67
戴顯權 著 / 資料結構 © 滄海圖書
68
戴顯權 著 / 資料結構 © 滄海圖書
69
戴顯權 著 / 資料結構 © 滄海圖書
70
戴顯權 著 / 資料結構 © 滄海圖書
71
戴顯權 著 / 資料結構 © 滄海圖書
72
基數排序法的原理與分析 排序多個鍵值的排序演算法 每張撲克牌都有兩個鍵值— 花色與點數，因此我們 得先定義這兩個鍵值的大小關係：
Key 花色： > > > Key 點數： A > K > Q > J > 10 > 9 > 8 > 7 > 6 > 5 > 4 > 3 > 2 排好的牌將形成這樣的順序： 2,…, A,…, 2,…, A 戴顯權 著 / 資料結構 © 滄海圖書
73
基數排序法的原理與分析 MSD 優先(Most Significant Digit)
從最左邊的位數開始比較，依序以每一個位數為鍵值，執 行以下的三個步驟： (1) 分配— 把含有相同高位鍵值的資料放到同一箱中； (2) 排序— 把各個箱子裡的資料分別排序；以及 (3) 合併— 把各箱裡的資料依序合成一串。 戴顯權 著 / 資料結構 © 滄海圖書
74
例題一 以基數排序法之MSD 優先法對{80, 44 , 324, 44+, 3, 94, 221, 8, 25, 210} 做排序 步驟1
最高位數為百位數。用百位數當鍵值，把數字分別放在不 同的箱子裡 戴顯權 著 / 資料結構 © 滄海圖書
75
例題一 戴顯權 著 / 資料結構 © 滄海圖書
76
例題一 步驟2 步驟3 分別將各箱子裡的數值做排序 合併各箱子裡的資料成一份
{3, 8, 25, 44, 44+, 80, 94, 210, 221, 324} 戴顯權 著 / 資料結構 © 滄海圖書
77
基數排序法的原理與分析 LSD 優先(Least Significant Digit)
從最右邊的位數開始比較，依序以每一個位數為鍵值，執 行以下兩個步驟： 分配— 從最右邊的位數開始比較，把含有相同鍵值的資 料放在同一箱裡。重複以上動作，直到到達最大數的最 高位數為止。如果最大數是P 位數，那麼需要比較P 次 合併— 把各箱裡的資料用插入排序法合成一串 戴顯權 著 / 資料結構 © 滄海圖書
78
例題二 以基數排序法之LSD 優先法對{80, 44 , 324, 44+, 3, 94, 221, 8, 25, 210} 做排序 步驟1
步驟1-1：根據個位數做分配 戴顯權 著 / 資料結構 © 滄海圖書
79
例題二 戴顯權 著 / 資料結構 © 滄海圖書
80
例題二 步驟1-2：根據十位數做分配 戴顯權 著 / 資料結構 © 滄海圖書
81
例題二 步驟1-3：根據百位數做分配 戴顯權 著 / 資料結構 © 滄海圖書
82
例題二 步驟2： 合併各箱子裡的資料成一份 {3, 8, 25, 44, 44+, 80, 94, 210, 221, 324}
戴顯權 著 / 資料結構 © 滄海圖書
83
基數排序法的原理與分析 LSD比MSD簡單 基數排序法的複雜度分析與數值的範圍(m)，基數的 大小(r)，以及數列的鍵值數量有關(n)
戴顯權 著 / 資料結構 © 滄海圖書
84
戴顯權 著 / 資料結構 © 滄海圖書
85
戴顯權 著 / 資料結構 © 滄海圖書
86
戴顯權 著 / 資料結構 © 滄海圖書
87
戴顯權 著 / 資料結構 © 滄海圖書
88
戴顯權 著 / 資料結構 © 滄海圖書
89
戴顯權 著 / 資料結構 © 滄海圖書
90
戴顯權 著 / 資料結構 © 滄海圖書
91
戴顯權 著 / 資料結構 © 滄海圖書
92
各種內部排序法的比較與選擇 戴顯權 著 / 資料結構 © 滄海圖書
93
各種內部排序法的比較與選擇 排序時能使用的空間有多大？ 對於排序時所花的時間要求如何？ 要求排序的穩定性否？ 要求演算法簡單否？
所要排序的資料數目大或小？ 所要排序的資料紀錄本身大或小？ 戴顯權 著 / 資料結構 © 滄海圖書
94
外部排序法 假設要排序的串列太大，以至於無法將整個串列放 在電腦的內部記憶體做處理，因此不可能做內部排 序
我們將假設要排序的串列(或檔案) 被放在磁碟上 如何對外部儲存裝置裡的資料做排序是一個很重要 的議題，尤其是在資料庫系統的應用上 戴顯權 著 / 資料結構 © 滄海圖書
95
外部排序法 外部排序最常用的方法是合併排序法。它先把檔案 分段，每一段檔案都用內部排序法加以排序好之後， 再把它們寫出到外部儲存裝置
排序好的各段資料稱為行程(runs)，把各行程利用合 併排序法逐步做合併，直到最後只剩下一個行程， 即可完成排序 戴顯權 著 / 資料結構 © 滄海圖書
96
外部排序法 若我們使用二路合併(2-way merge)，那麼以m 個行程 來說，將需要處理log2m 次的合併；如果採用k-路合 併(k-way merge) 的話，那麼將需要logk m 次的合併 當然，k 越大，需要處理的合併次數就越少 戴顯權 著 / 資料結構 © 滄海圖書
97
外部排序法 使用k-路合併的原意是希望減少輸出入時間，但合併 k 個行程前要決定下一筆輸出的排序資料，必須做k – 1 次比較才可以得到答案； 也就是說，雖然輸出入時間減少了，但進行k-路合併 時，卻增加了更多的比較時間，因此選擇合適的k 值， 才能在這兩者之間取得平衡 戴顯權 著 / 資料結構 © 滄海圖書
98
外部排序法 戴顯權 著 / 資料結構 © 滄海圖書
99
外部排序法 戴顯權 著 / 資料結構 © 滄海圖書
Similar presentations
