使用C/C++語言 楊正宏 編著 全華科技圖書股份有限公司 印行.

Presentation on theme: "使用C/C++語言 楊正宏 編著 全華科技圖書股份有限公司 印行."— Presentation transcript:

1 使用C/C++語言 楊正宏 編著 全華科技圖書股份有限公司 印行

2 第九章 排 序(1/4) 9-1 前言 9-2 內部排序法(Internal Sort) 9-2-1 交換式排序法 9-2-2 插入式排序
9-1 前言 9-2 內部排序法(Internal Sort) 交換式排序法 氣泡排序法(Bubble Sort) 交換-線性選擇排序法(Linear Selection with Exchange Sort) 過濾排序(Sifting Sort) 快速排序法(Quick Sort) 插入式排序 中心插入排序法(Centered Insertion Sort)

3 第九章 排 序(2/4) 9-2 內部排序法(Internal Sort) 9-2-2 插入式排序 9-2-3 選擇和樹狀排序
插入式排序 二元插入排序法(Binary Insertion Sort) 謝耳排序法(Shell Sort) 選擇和樹狀排序 線性選擇排序法(Lineal Selection Sort) 二次選擇排序法(Quadratic Selection Sort) 賽程排序(Tournament Sort) 堆積排序法(Heap Sort)

4 第九章 排 序(3/4) 9-2 內部排序法(Internal Sort) 9-3 外部排序法(External Sort)
選擇和樹狀排序 二元樹排序法(Binary Tree Sort) 其它排序 合併排序法(Merge Sort) 計數排序法(Counting Sort) 基數排序法(Radix Sort) 9-3 外部排序法(External Sort) 直接合併排序法(Direct Merge Sort) 自然合併排序法(Natural Merge Sort)

5 第九章 排 序(4/4) 9-3 外部排序法(External Sort) 9-4 排序法的效益評估
k路合併法(k-Way Merge Sort) 多階段合併法(Polyphase Merge) 9-4 排序法的效益評估

6 前言 將一些資料，依照某種特定的原則或需求安排成遞增(increment)或遞減(decrement)的順序。
方法分為兩種：內部排序(internal sort)與外部排序(external sort)。 相關的名詞和性質 ： 記憶體空間 效率 穩定性(stability)

7 內部排序法(Internal Sort) 交換式排序(Interchange Sort)
原理：兩項資料互相比較，若符合交換原則(如第二項大於第一項) 。 氣泡排序法(Bubble Sort) 交換線性選擇排序法(Linear Selection with Exchange Sort) 過濾排序法(Sifting Sort) 快速排序法(Quick Sort)

8 氣泡排序法(1/4) 排序的時候，讓較大的元素往下沉，或較小的元素往上浮。
其排序處理程序是從元素的開始位置起，相鄰的兩個元素相比較，若第i個的元素大於第(i+1)的元素，則兩元素互換，比較過所有的元素後，最大的元素將會沈到最底部。

9 氣泡排序法(2/4) 一陣列存有82, 16, 9, 95, 27, 75, 42, 69和34等九個值， 利用氣泡排序法排序
表格中粗體字表示正在比較 移動次數 次 一 第 次 二 第 次 三 第 次 四 第 次 五 第 次 六 第 次 七 第 次 八 第 1 82 16 16 16 16 16 16 16 2 16 82 9 9 9 9 9 9 3 9 9 82 82 82 82 82 82 資 4 95 95 95 27 27 27 27 27 料 5 27 27 27 95 75 75 75 75 數 6 75 75 75 75 95 42 42 42 7 42 42 42 42 42 95 69 69 8 69 69 69 69 69 69 95 34 9 34 34 34 34 34 34 34 95

10 氣泡排序法(3/4) 重覆每一個循環都會把巡視到的最大元素放在巡視範圍內最低的位置，且每次循環的巡視範圍都比前一次循環少一個元素，如此重覆至一個循環中都沒有互換產生才停止。

11 氣泡排序法(4/4) 效率： 每次循環所作的比較依序是(n-1), (n-2), (n-3), ..., 2, 1，合計所需的比較次數序：(n-1) + (n-2) + … = n(n-1)/2次。 每一循環所作的互換元素的次數為(n-1), (n-2), ..., 2, 1，共需(n-1) + (n-2) + … = n(n－1)/2的互換動作。 效率 f(n) = O(n2)。

12 氣泡排序法演算法 1 Procedure Bubble_Sort(p,n) 2 flag  1 3 for i0 to n-1 do
4            if flag=0 then return 5            flag0 6            for j0 to n-1 do 7            if p(j+1)<p(j) then 8            swap p(j),p(j+1) 9            flag1 10        end 11        end 12        end 13        end

13 交換-線性選擇排序法(1/3) 找出陣列中最小的資料(a[lower])，然後與陣列中第一個位置上的資料(a[0])交換。
接著進行循環(在陣列中找出最小值)，從剩餘的資料中(a[1]~a[n-1])，找到最小的資料與最左邊的資料(a[1])互換。 繼續循環，直至整個陣列都排序好。

14 交換-線性選擇排序法(2/3)

15 交換-線性選擇排序法(3/3) 效率： 在k筆資料中循序找出最小值，共需k-1次比較，而完成n筆資料的排序，共需重複此步驟n次，所以總比較次數為 資料交換的次數將不會超過n次，資料的次序與總比較次數無關，但與交換次數有關。 如資料值已由小而大排好，則總比較次數為n*(n-1)/2，但資料卻不需交換，即f(n) ＝O(n2)。 是最簡單的排序法，但相對它的效率較差，僅適用於元素較少的資料排序。

16 交換-線性選擇排序演算法 1 Procedure LSE_Sort(p,n) 2 for i1 to n-1 do
3            lowerp(i) 4            addressi 5           for ji+1 to n do 6           if p(j)<lower then 7            lowerp(j) 8            addressj 9            end 10        end 11        p(address)p(i) 12        p(i)lower 13        end 14     end

17 過濾排序法(1/5) 兩階段的步驟： 和氣泡排序一樣兩兩比較，假設data[n]為現在指標(箭頭指向的位置)的資料，data[n+1]為下一筆資料，若data[n+1]<data[n]則交換。 交換後要重新確認data[n]筆以前的資料是否符合由小到大的規則，若沒有，則重複第一步驟。

18 過濾排序法(2/5) 原資料 交換後 ↓ 82 95 27 75 42 69 34 16 9 第1次比較 82 95 27 75 42 69 34 16 9

19 過濾排序法(3/5) ↓ 82 95 27 75 42 69 34 16 9 第2次比較 82 27 95 75 42 69 34 16 9 第二次交換後 27 82 95 75 42 69 34 16 9 ↓ 27 82 95 75 42 69 34 16 9 指標位置

20 過濾排序法(4/5) 第3次比較 27 82 75 95 42 69 34 16 9 第三次交換後 27 75 82 95 42 69 34 16 9 ↓ 27 75 82 95 42 69 34 16 9 第4次比較 27 75 82 42 95 69 34 16 9

21 過濾排序法(5/5) 以下類推 … 效率： 在最差情況下比較次數為1+2+3+….+(n-1)=n(n-1)/2，其複雜度為O(n2)。
第四次交換後 27 75 42 82 95 69 34 16 9 第五次交換後 27 42 75 82 95 69 34 16 9 以下類推 … 最後結果 9 16 27 34 42 69 75 82 95 效率： 在最差情況下比較次數為1+2+3+….+(n-1)=n(n-1)/2，其複雜度為O(n2)。

22 快速排序法(1/5) 又稱分割排序法(Partition Exchange Sort) 處理原則： Divide and Conquer
隨機在所有元素中設定基準值，依此基準值將所有的元素分割兩部份，然後在兩邊各設一個新的基準值，再分成兩邊，如此一直分到不能再分為止。 撰寫程式的兩種方式： 遞迴式 非遞迴式

23 快速排序法(2/5) 操作方式 選取第一個之元素 為鍵值亦即是基準值K。
由左至右，一直掃視到Ki > K (i = 2, 3, 4, …, n-1, n)。 由右至左，一直掃視到Kj < K (j = n, n-1, …, 4, 3, 2)。 當 時，Ri與Rj互換，否則 與Rj互換。 (此時陣列分成兩個部份，一個是小於 ，另一半是大於 )

24 快速排序法(3/5) 效率： 假設資料數量n是2的整數次方，並令n = 2m，使得m=log2n 對於整個排序動作所需的比較總次數
時間複雜度為O(n*m)，也就是O(nlog2n) (共有m項)

25 快速排序法(4/5) 若鍵值在左邊的快速排序法，則它的最壞情況會發生在資料陣列已經排序好的狀況。 排序好整份資料共需比較的次數
對於“完全未排序”的資料，我們使用快速排序法可以有最佳狀況。 若是資料已經排序過，快速排序法就發揮不了作用了。這樣的現象正好與泡沫排序法相反。 ＝O(n2)

26 快速排序法(5/5) 缺點 ： quicksort是recursive本質，很難去寫一個non-recursive演算法。
quicksort的最差情況是O(n2)，故quicksort只在平均情況下是最佳的sorting。 當資料已經排序好或完全相反次序時，均需O(n2)。 是一種不穩定的排序法(unstable sorting method)。所需額外空間甚多，O(logn)～O(n)。

27 快速排序演算法(1/2) Procedure Quick_Sort(p,left,right) //鍵值(key) 位於最左邊之演算法
if left<right then ileft+1;jright;divided=left ┌ loop 做數值的比較與交換迴圈 │ repeat ii+1 until p(i)>p(divided) │ repeat jj-1 until p(j)<p(divided) │ if i<j then swap p(i),p(j) │ else exit └ forever swap p(divided),p(j) //與鍵值更換// call Quick_Sort(p,left,j-1) ┐ call Quick_Sort(p,j+1,right)] ┘ //做左右兩半排序// end

28 快速排序演算法(2/2) Procedure Quick_Sort(p,left,right) // 鍵值位於中間之演算法
if left<right then ileft;jright; divided=(right+right)/2 ┌ loop 做數值的比較與交換迴圈 │ repeat ii+1 until p(i)>p(divided) │ repeat jj-1 until p(i)<p(divided) │ if i<j then swap p(i),p(j) │ else exit └ forever swap p(divided),p(j) //與鍵值更換// call Quick_Sort(p,left,j-1) ┐ call Quick_Sort(p,j+1,right)] ┘ //做左右兩半排序// end

29 插入式排序法 運作原則是將逐一比對後的資料插入到適當的位置中，所以對一個n個元素的陣列，進行插入式排序法時，需具備一個與資料長度n相同的輔助陣列。 中心插入排序法(Centered Insertion Sort) 二元插入排序法(Binary Insertion Sort) 謝耳排序法(Shell Sort)

30 中心插入排序法(1/3) 具備一個與資料長度相同的輔助陣列。 先將原始資料陣列中的第一個資料放入輔助陣列中間的位置。
設有兩個指標 Low 和 High 指向該位置，其中Low和High分別代表陣列中的所存在資料的最低和最高位址。

31 中心插入排序法(2/3) 從原陣列開始，依序取出一筆資料與 Low 所指的資料相比較
若原資料較大，則再與位置Low + 1到High間的元素相比較，一直找到一個大於它的元素，才把原資料插入於該位置上，而大於此元素的元素皆往右移一位，如向右移已沒有空位，則從插入元素前的位置至Low的位置向左移一位，Low再減1。 若原資料較小，則將資料放入Low-1的位置上，然後再將Low值減1，此時若Low值等於0的話，則把Low至High之間的資料往右移動，再將原資料放入第0位，High值再加1。

32 中心插入排序法(3/3) 效率： 中心插入法對於一個n元素的陣列的比較作法為1, 2, 3, …, (n-1)次，共需 (n-1 ) = n(n-1)/2。至於移動次數則可估為1+2+3＋… +(n-1) = n(n-1)/2所以其效率可估計為f(n) = O( n2 )。

33 二元插入排序法(1/5) 先將一筆資料插入一串有序的資料(ordered data：依大小做好排列的資料)R1, R2, …, Ri中( R1 ≤ R2 ≤ R3 ... ≤ Ri ) 。 一開始將輸入第一筆資料於已預先設定好的陣列長度中的第一位或是最後一位，等待第二筆資料輸入後，與其比較大小，其大小關係影響其陣列排列順序。

34 二元插入排序法(2/5) 第一種排序： 將第一筆的資料放在陣列的第一位，此時的這一筆資料在整個一串資料中被當成是最小，下一筆資料和其比較的情形可分為比其大或小。 若下一筆資料較大：則將這一筆資料放在整個陣列中的第二位，而最小的指標依然不變。 若下一筆資料較小：則將第一筆輸入的資料移到陣列的第二個位置,而第二筆輸入的資料則放在第一個位置，而最小的指標則指向第二筆輸入的資料。若資料數超過三個時則必須一直比下去，直到每筆資料皆比過。但是若遇到前一筆資料比較大時便可停止。

35 二元插入排序法(3/5) 第二種排序： 將第一筆的資料放在陣列的最後一位，此時的這一筆資料在整個一串資料中被當成是最大，下一筆資料和其比較的情形可分為比其大或小。 若較小：則將這一筆資料放在整個陣列中的倒數第二位，而最大的指標依然不變。 若較大：則將第一筆輸入的資料移到陣列的倒數第二個位置，而第二筆輸入的資料則放在最後第一個位置，而最大的指標則指向第二筆輸入的資料。若資料數超過三個時則必須一直比下去，但是若遇到前一筆資料比較小時便可停止。

36 二元插入排序法(4/5) 效率： 執行n-1次插入的動作，所以必須對陣列中的資料做比較與交換的動作，在最差的狀況下共要做1+2+3+…+(n-1)次，經計算n(n-1)/2是O(n2) 。 在平均的狀況下，雖然每次插入只取用一半之資料，不必取用全部資料，但是對於時間複雜度來說，其計算結果依然為O(n2)。

37 二元插入排序法(5/5) 特性 ： 平均時間複雜度與最差時間複雜度均為O(n2)。 為一穩定的排序( stable sorting )。
需要兩個額外的記錄空間，其中一個作為虛擬記錄(dummy record)，另一個作為交換時間的暫存空間。

38 謝耳排序法(1/5) 由D.L. Shell所提出，方法是插入排序法演進而來，允許所要排序的元素距離較遠，目的是減少插入排序法中元素搬移的次數，增快排序的速度。 利用某一變數的間隔來比對其相間隔的元素。 n個元素排序，初始間隔是 Gap = ，開始時是第i個與第 i + Gap個進行比，若第i個元素較大，則兩元素互換，反之則不互換。若有互換時則必須再與往上數Gap項比較，以決定是否再互換；若不再互換，則繼續往下比較，直到 n-Gap 次的比較，然後再互換間隔 ，重覆操作直到 Gap = 0 就停止，表示已經排序完成。

39 謝耳排序法(2/5) 原始資料： 第一次交換：Gap= = 4 1 2 3 4 5 6 7 8 82 16 9 95 27 75 42 69
1 2 3 4 5 6 7 8 82 16 9 95 27 75 42 69 34 1 2 3 4 5 6 7 8 82 16 9 95 27 75 42 69 34

40 謝耳排序法(3/5) 分成的群組有：(0, 4, 8)，(1, 5)，(2, 6)，(3, 7)。 其比較先後次序如下： 結果：
先比較(0, 4)，(1, 5)，(2, 6)，(3, 7)。 再比較第二部分(4, 8) 結果： 第二次交換：Gap=4/2=2 27 16 9 69 34 75 42 95 82 1 2 3 4 5 6 7 8 27 16 9 69 34 75 42 95 82

41 謝耳排序法(4/5) 分成的群組有：(0, 2, 4, 6, 8)，(1, 3, 5, 7)。
其比較先後次序如下：(0, 2)，(1, 3)，(2, 4)，(3, 5)，(4, 6)，(5, 7)，(6, 8) 結果： 第三次交換：Gap=2/2=1 9 16 27 69 34 75 42 95 82 1 2 3 4 5 6 7 8 9 16 27 69 34 75 42 95 82 每個資料互相比較：(0, 1)，(1, 2)，(2, 3)，(3, 4)，(4, 5)，(5, 6)，(6, 7)，(7, 8)

42 謝耳排序法(5/5) 結果： 最後一次：Gap=1/2=0 排序完畢 效率： Ｃprimary = = n(log 2 n) - n
每個 PASS 的比較次數最少為 n-Gap 次，因此 Ｃprimary = = n(log 2 n) - n 9 16 27 34 42 69 75 82 95

43 選擇和樹狀排序 線性選擇排序法(Linear Selection Sort)
二次選擇排序法（Quadratic Selection Sort） 賽程排序(Tournament Sort) 堆積排序法(Heap Sort) 二元樹排序法（Binary Tree Sort）

44 線性選擇排序法(1/2) 每執行一次循環(Pass)便從陣列中選擇最小的資料，並依序存入輸出陣列中。(參考下表)
第一循環時(Pass1)，我們先設定Lower為p[0]，而address為0，然後從第1個資料開始依序比較，直到找到較小值：(Lower：95) 。 (Lower：95)表示Lower值與 95 比較，其他類推。 此時找到較小值9，然後把Lower設定成新的較小值9，同時將Lower值之位置指定給address（即address=8）。 Lower及address設定成新值後，再繼續比較取代，直到所有陣列資料都巡視過。

45

46 線性選擇排序法(2/2) 效率： 對於n個資料的陣列，線性選擇法共需要n次循環，每一次循環都包含(n-1)次的比較(包括與MAXINT或Z比較)，因此線性選擇排序法總共要n*(n-1)次的比較。但這並不完全代表該排序的效率，因為它還包括移動較小值到lower及較小資料之位置到address，而移動次數完全依陣列的排列而定，例如有一排序好的陣列，那移動次數為零，若以相反順序排(最差情況下)，則需要n-1次移動(每一循環)，因此f(n) = O(n2)。

47 線性選擇排序演算法 1 Procedure LS_Sort(p,q,n) 2 for i1 to n do q(i)MAXINT
4            lowerp(1) 5            address1 6            counter0 7            for j1 to n do 8            if p(j)<lower then 9            lowerp(j) 10       addressj 11        q(i)lower 12       countercounter+1 13       end 14        if counter=0 then q(i)lower 15       p(address)MAXINT 16        end 17        end end

48 二次選擇排序法(1/2) 若原始陣列具有 n 個資料，我們可以把它劃分成部份。若 n 不是完全平方的數，我們就以緊接的完全平方數n來代。
劃分好後，分別從各個部份選擇最小的資料，依次放到一輔助陣列，同時把各部份的相對資料以Z取代。 再從輔助陣列的個資料中找到最小的資料，把它置入輸出陣列，並且以Z代表輔助陣列的該最小資料。 以Z代表輔助陣列的該最小資料。然後從該最小資料所屬的部份再找出一較小資料 ，再放入輔助陣列，重覆找最小資料的動作。

49

50 二次選擇排序法(2/2) 最後結果： 效率： 第一個最小資料的選擇需要K(L-1) + (K-1)次比較
每一較小資料都要有(L-1) + (K-1)次比較(包括與Z之比較) 。 (n-1)個資料需要(n-1)[(L-1)+(K-1)]次比較。 總共合計： K(L-1) + (K-1) + (n-1) [(L-1) + (K-1)] = KL-1 + (n-1)(L+K-2) 。 複雜度 f(n)=O(n3/2)。

51 賽程排序法(1/2) 假設一筆資料 。 將所有資料填入一個有2k個葉節點( k=0,1,2… )的競賽樹(tournament tree)，而剩下的空節點填入”*”符號。 對節點內的值兩兩做比較，數值較大者為父節點，依照此規則可得到下圖(a) 。 最大數值95為整棵樹的根，將最大者輸出，再將樹重新整理，得圖(b) 。 其中 -1 代表已輸出資料項，照此規則可得到一由大到小的數列，最後一項資料必須假設為0代表已輸出完畢。

52 82 75 69 27 42 9 16 -1 (b) 輸出95，然後重新調整 95 (a) (c) 輸出82，然後重新調整

53 賽程排序法(2/2) ….. -1 (d)

54 堆積排序法(1/10) 利用堆積樹(Heap tree)的方式進行排序的功能，是一種特殊的二元樹 具備下列特性：
是一棵完全二元樹(Complete Binary Tree)。 每一個節點之值均大於或等於它的兩個子節點之值。 樹根的值是堆積樹中最大的。

55 堆積排序法(2/10) 圖(a)是堆積樹，圖(b)不是堆積樹 95 24 82 75 42 69 34 圖(a) 27 圖(b)

56 堆積排序法(3/10) 先將原始資料依序建立成完全二元樹，然後在依序下列的處理程序處理： 將完全二元樹轉換成堆積樹。
從陣列中間位置的資料為父節點，開始調整。 找出此父節點中的兩個子節點中之較大者，再與父節點比較，若父節點資料較小，則交換這兩個資料。然後以交換後的子節點做為新的父節點，重覆此步驟直到沒有子節點為止。 以步驟3中原本的父節點的所在位置往前推一個位置，做為新的父節點。繼續重覆步驟3，直到調整到樹根完畢為止。則堆積樹已形成。 有了堆積樹後，我們便開始排序。將樹根與二元樹的最後一個節點互換後，將最後一個節點輸出（即輸出的是原本的樹根）。然後比較樹根的兩個子節點，若左子節點的資料較大，則調整左子樹；反之，則調整右子樹部份，使之再成為堆積樹。 重覆上一步驟，直到二元樹剩下一個節點為止。

57 堆積排序法(4/10) 完全二元樹結構 82 95 9 16 27 75 42 69 34 圖

58 堆積排序法(5/10) 輸出 34 69 75 82 27 9 42 16 95 圖 95 69 75 82 27 9 42 16 34 圖

59 堆積排序法(6/10) 16 34 75 69 27 9 42 輸出82 82 34 75 69 27 9 42 16 調整 圖 圖

60 堆積排序法(7/10) 16 34 42 69 27 9 輸出75 69 16 42 34 27 9 調整 75 34 42 69 27 9 16 調整 圖

61 堆積排序法(8/10) 9 16 42 34 27 輸出69 42 16 9 34 27 調整 27 16 9 34 輸出42 圖

62 堆積排序法(9/10) 9 34 16 9 27 調整 27 9 16 調整 16 9 27 輸出34 16 9 調整 圖9-2-3-5.5
輸出16 16 9 調整 9 最後輸出樹根9 圖

63 堆積排序法(10/10) 效率： 執行時間主要耗費在建立堆積樹和反覆的調整堆積樹上面，對於深度為k的堆積樹，在ADJUST演算法中進行的比較次數最多為2(k-1)次。 對於n個節點的完全二元樹，其深度為 ，因此調整堆積樹時呼叫ADJUST演算法(n-1)次，所以總共進行的比較次數不超過下式之值： 堆積排序在最壞的情況下，其時間複雜度也為O(nlogn)

64 二元樹排序法(1/6) 將資料以二元搜尋樹來表示，以中序追蹤二元搜尋樹，以進行排序。 建立二元樹的步驟： 將第一個元素放在樹根節點。
把每一個要加進來的元素與樹根節點比較，若比樹根節點小，再與左子節點比較，若沒有左子樹，則把此元素放於左子樹。反之，比樹根節點大，則再與右子節點比較，若沒有右子樹，就把此元素放於右子樹。 連續步驟2的操作，直到所有的元素皆被加入二元樹中。

65 二元樹排序法(2/6) 原始資料 建立二元樹的過程圖 82 16 9 95 圖

66 二元樹排序法(3/6) 82 9 16 95 27 75 82 9 16 95 27 75 42 69 34 圖

67 二元樹排序法(4/6) 效率： 此分類法的效率依各個元素的原始順序而定，若原始陣列完全分類好（或依相反方向排好），則所得到的樹狀成為一個循序右鏈結（或左鏈結），如圖 所示。在此情況下，建立樹狀時，插入第一個節點不須比較；插入的第二個結點須比較兩次；插入第三個結點須比較三次…，以此類推，比較次數的總和為： 2+3+…+ n = [(n*(n+1))/2] 其效率為O(n2)

68 二元樹排序法(5/6) 效率： 原始資料 比較次數：14 16 8 12 17 26 4 圖

69 二元樹排序法(6/6) 效率： 若原始陣列的排序結構為第一個元素a，其後大約有一半元素大於a，令一半元素小於a，在此狀況下，所得的二元素之高度d最小，其值大於或等於 log(n+1)-1。在二元樹之第X階層的節點數（最後階層除外）為 2 個，且欲將一元素置於階層（X=0除外）需要X+1次比較。故比較的次數為： 與 之間 可證明比較次數的總和為 O(n log n)。

70 內部排序法(Internal Sort) 其它排序 合併排序法(Merge Sort) 計數排序法(Counting Sort)
基數排序法(Radix Sort)

71 合併排序法(1/7) 可被應用去排序一堆沒有排序的資料或將兩個或兩個以上排序好的資料，合併成一個已排序好的資料。
可分為遞迴排序法、非遞迴排序法。 可分為直接合併法 (Direct Merge Sort)與自然合併法 (Natural Merge Sort)。 假設兩個已排序好的資料集合A及B，將其合併後放入空資料集合C ，合併的運作方式： 每次比較A和B的第一筆資料，將較小的那一筆放入C中。 重覆上一步驟，直到A或B其中一個變為空集合。 將另一集合剩下的所有資料依序放到C的尾端，則合併完成。

72 合併排序法(2/7) 合併完成後，將資料細分至長度值為1的集合，然後再一一合併，最後得到了一個已經排序好的資料集合，其步驟如下：
直接排序法先將資料分成左、右兩個部份集合，再將左半部的資料一分為二，直到資料長度值為1。 將第一及第二個子資料集合合併，第三及第四個子資料集合合併，…，以此類推。 重覆上一步驟，將合併後的子集合再次兩兩合併。 最後，所有的子集合已合併成為一個排序好的資料集合，即排序完成。

73 合併排序法(3/7) 原始資料： 首先，將資料分成左、右兩部份： 再將左半部劃分，直到長度為1：

74 合併排序法(4/7) 進行比較後，再依小至大的方式排列來進行合併： 再將 [95 27] 分成二部份，再進行比較合併：

75 合併排序法(5/7) 再合併 [9 16 82] [27 95]，得到經過排序後的左半部： 將右半部的資料依左半部資料處理的方式處理得到：
再合併 [ ] [27 95]，得到經過排序後的左半部： 將右半部的資料依左半部資料處理的方式處理得到： 合併經處理左、右兩部份

76 合併排序法(6/7) 最後結果

77 合併排序法(7/7) 效率： 遞迴式的合併排序法不論在平均狀況或最壞狀況下，效率皆是O(nlog n)。而非遞迴的合併排序法，共需log n循環，每循環約需n次比較，所以效率仍為O(nlog n)。 優點： 平均情況(average case)或是最糟情況（worst case）下，其效率皆為n log n(假設有n筆記錄)。 缺點: 進行合併的動作時，必須用到額外的記憶體空間，此空間的大小正比於n

78 計數排序法(1/3) 每項資料設置一個計數器，再巡視整個陣列，方法是先從資料陣列中依序取出一筆資料。
取出之資料再分別與其他筆資料兩兩相比，並在較大（或小）資料的計數器上加1。 從第一筆資料開始與其下每一筆資料相比較，當比完後，再拿第二筆資料與其下每一筆資料相比（第一筆資料不用再比），以此類推。 構想是對每一個值都計算關鍵值的個數，再根據計數來搬動資料的位置。

79 計數排序法(2/3) 一陣列存有82, 16, 9, 95, 27, 75, 42, 69, 34共9筆資料 。 第一次比較是82與其下8筆資料做比較，比較大的值則在其計數器上加一，過程如下圖：

80 計數排序法(3/3) 效率： ｎ筆資料共需要比較 n-1 次。 總比較次數：

81 基數排序法(1/4) 又稱Bucket sort或Binsort 。 流程是將鍵值分成幾個單元，把同一單元的放在一堆 。
比較方向可分為最有效鍵(Most Significant Digit, MSD)或最無效鍵(Least Significant Digit, LSD) 。 MSD法是從最左邊的位數開始比較，是採用分配、排序、收集三個步驟進行。 LSD是從最右邊的位數開始比較，只須採用分配和收集兩個步驟。

82 基數排序法(2/4) 原始資料： 方法1：採用MSD，依照十位數的大小排序。 排序結果：

83 基數排序法(3/4) 方法2：採用LSD，先依照個位數的大小排序，再排序十位數。 按照個位數排序可得結果 再按照十位數排序

84 基數排序法(4/4) 效率： 缺點： 時間需求很明顯的是依資料位數的數目(m)及檔案中元素的數目(n)而定。
外部迴圈會被執行m次，內部迴圈會被執行n次，所以效率大約是O(m*n)。 缺點： 需要的額外空間較大，需要(m*n)個儲存空間。

85 外部排序法(External Sort) 可對於資料量非常龐大且無法全部載入記憶體中的資料進行排序。
效率比較差，但卻是必須時常使用的排序法。 直接合併排序法 (Direct Merge Sort) 自然合併排序法 (Natural Merge Sort) k 路合併法 (k-Way Merge Sort) 多階段合併法 (Polyphase Merge)

86 自然合併排序法(1/5) 利用原始資料中有些資料已排序的特性。
巡視所有資料的過程中，發現元素的數值有減小（stepdown）的現象時，即將其分裂，待全部分裂完成後，再將其合併，如此分裂、合併交互的進行，直至所有的元素被排序。

87 自然合併排序法(2/5) 原始資料： 將其分成兩組：
首先以將82填入B陣列，然後比較下一資料，是否有分裂現象(即是否比上筆資料小)，因為16<82，故分裂，16填入C陣列中，下一筆資料9直接填入B陣列，繼續上一步驟，檢查是否分裂，若沒有則將值填入B陣列；若有分裂，將值丟入C陣列，下一筆資料直接送入B陣列。反覆此步驟，直到最後一個值。

88 自然合併排序法(3/5) 進行合併： 再將其分組： 合併為：

89 自然合併排序法(4/5) 分裂為： 合併：

90 自然合併排序法(5/5) 效率： 假設要排序的元素有 n個，如以遞迴的方式處理，則每次分割的長度為原來的一半，所以合併的關係式可表示為：
a n=1 a為常數 T(n)＝ 2T(2/n)+Cn n>1 c為常數

91 k路合併法(1/6) 利用磁碟來作排序，假設原始資料為： 因為記憶體的關係，每次傳輸資料只能有兩筆資料 步驟1：

92 k路合併法(2/6) 令磁碟一、二為輸入資料，磁碟三、四為輸出資料用。 步驟2： 重複步驟，直至所有原始資料全部被載入。

93 k路合併法(3/6) 開始合併排序，第一次輸入資料16, 9進入記憶體，經排序後寫出較小的9至磁碟三中，同時也由磁碟二中讀入資料95。經排序後寫出16至磁碟三，同時讀入磁碟一的資料82。經排序結果依序寫出82, 95至磁碟三中。重複以上步驟，將第二區段的資料寫入磁碟四。

94 k路合併法(4/6) 將磁碟三、四的排序結果送入磁碟一、二中，直到排序完整，最後結果如下表：

95 k路合併法(5/6) 以兩個磁碟輸入資料作合併排序的樹

96 k路合併法(6/6) 以四個磁碟作合併排序的樹 效率：
此法之k值越大，則樹之高度越低。假設有n個資料要用k-路合併法，則其樹的高度表示為（logkn），即要執行合併排序法的次數。

97 多階段合併法(1/7) 做法是每次將行程最小的磁帶與其他磁帶中相同數目的行程作一k向合併。
然後把結果寫至空白磁帶上，如此周而復始地重複此步驟，直到合併成一個行程為止，此程序就稱之為“合併到無”。 多階段合併法比k路合併排序法節省磁帶。因k路合併排序法需2k盒磁帶，而多階段合併法只需k+1盒磁帶。

98 多階段合併法(2/7) 假設Tape1有5個行程，Tape2有3個行程，Tape3則為空白帶 ： Tape2 5 7 11 1 12 15
17 19 20 23 9 14 7 8 4 5 16 Tape2 5 7 11 1 12 15

99 多階段合併法(3/7) 將Tape1和Tape2的行程一、二、三合併至Tape3 Tape2 4 5 9 16 7 15 Tape1 1
11 17 19 20 23 12 14 8 Tape3

100 多階段合併法(4/7) 將Tape1及Tape3作合併，然後寫入Tape2 Tape1 Tape3 8 Tape2 1 4 5 7 9 11
16 17 19 20 23 12 14 15 Tape3 8

101 多階段合併法(5/7) 把Tape3與Tape2合併至Tape1 Tape1 Tape2 Tape3

102 多階段合併法(6/7) 將Tape1與Tape2的雙向合併結果寫至Tape3 Tape1 Tape2 Tape3 圖 　完成合併

103 多階段合併法(7/7) 也可表示成： 效率： 是(n-1)項合併而不是(n/2)項的合併，由於所需的迴圈次大約是logkn 。

104 排序法的效益評估(1/2)

105 排序法的效益評估(2/2)