第八章　排序 8-1 排序簡介 8-2 內部排序法 8-3 外部排序法.

Presentation on theme: "第八章　排序 8-1 排序簡介 8-2 內部排序法 8-3 外部排序法."— Presentation transcript:

1 第八章　排序 8-1 排序簡介 8-2 內部排序法 8-3 外部排序法

2 排序簡介 在排序的過程中，資料的移動方式可分為「直接移動」及「邏輯移動」兩種。
「直接移動」是直接交換儲存資料的位置，而「邏輯移動」並不會移動資料儲存位置，僅改變指向這些資料的輔助指標的值。 資料在經過排序後，會有下列幾點好處： 1.資料較容易閱讀。 2.資料較利於統計及整理。 3.可大幅減少資料搜尋的時間。

3 排序的分類 1、內部排序：排序的資料量小，可以完全在記憶體內進 行排序。 2、外部排序：排序的資料量無法直接在記憶體內進行排
序，而必須使用到輔助記憶體(如硬碟)。 內部排序法有：氣泡排序法、選擇排序法、插入排序法、合併排序法、快速排序法、堆積排序法、謝耳排序法、基數排序法等。 外部排序法有：直接合併排序法、k路合併法、多相合併法等。

4 排序演算法分析 演算法是否穩定 穩定的排序是指資料在經過排序後，兩個相同鍵值的記錄仍然保持原來的次序，如下例中7左的原始位置在7右的左邊（所謂7左及7右是指相同鍵值一個在左一個在右），穩定的排序(Stable Sort)後7左仍應在7右的左邊，不穩定排序則有可能7左會跑到7右的右邊去。例如： 原始資料順序： 7左 右 6 穩定的排序： 左 7右 9 不穩定的排序： 右 7左 9

5 時間複雜度(Time complexity)：
可分為最好情況(Best Case)、最壞情況(Worst Case)及平均情況(Average Case)。 最好情況就是資料已完成排序，例如原本資料已經完成遞增排序了，如果再進行一次遞增排序所使用的時間複雜度就是最好情況。 最壞情況是指每一鍵值均須重新排列，簡單的例子如原本為遞增排序重新排序成為遞減，就是最壞情況。 排序前： 排序後： 【這種排序的時間複雜度就是最壞情況】

6 空間複雜度(Space complexity)：
指演算法在執行過程所需付出的額外記憶體空間。 挑選的排序法必須藉助遞迴的方式來進行，那麼遞迴過程中會使用到的堆疊就是這個排序法必須付出的額外空間。 排序法所使用到的額外空間愈少，它的空間複雜度就愈佳。 氣泡法在排序過程中僅會用到一個額的空間，在所有的排序演算法中，這樣的空間複雜度就算是最好的。

7 內部排序法 排序名稱 排序特性 簡單排序法 1.氣泡排序法(Bubble Sort) (1)穩定排序法
2.選擇排序法(Selection Sort) (1)不穩定排序法 3.插入排序法(Insertion Sort) 4.謝耳排序法(Shell Sort)

8 高等排序法 1.快速排序法 (Quick Sort) (1)不穩定排序法 (2)空間複雜度最差O(n)最佳O(log2n) 2.堆積排序法 (Heap Sort) (2)空間複雜度為最佳，只需一個額外空間O(1) 3.基數排序法 (Radix Sort) (1)穩定排序法 (2)空間複雜度為O(np)，n為原始資料的個數，p為基底

9 氣泡排序法 氣泡排序法又稱為交換排序法，是由觀察水中氣泡變化構思而成，氣泡隨著水深壓力而改變。
氣泡排序法的比較方式是由第一個元素開始，比較相鄰元素大小，若大小順序有誤，則對調後再進行下一個元素的比較。 如此掃描過一次之後就可確保最後一個元素是位於正確的順序。 接著再逐步進行第二次掃描，直到完成所有元素的排序關係為止。

10 氣泡排序法演算流程 由小到大排序：

11 第一次掃描會先拿第一個元素6和第二個元素4作比較，如果第二個元素小於第一個元素，則作交換的動作。
接著拿6和9作比較，就這樣一直比較並交換，到第4次比較完後即可確定最大值在陣列的最後面。

12 第二次掃描亦從頭比較起，但因最後一個元素在第一次掃描就已確定是陣列最大值，故只需比較3次即可把剩餘陣列元素的最大值排到剩餘陣列的最後面。

13 第三次掃描完，完成三個值的排序 第四次掃描完，即可完成所有排序 由此可知5個元素的氣泡排序法必須執行5-1次掃描，第一次掃描需比較5-1次，共比較 =10次

14 氣泡法分析 1. 最壞清況及平均情況均需比較：(n-1)+(n-2)+(n-3) + …+3+2+1= 次；時間複雜度為O(n2)，最好情
況只需完成一次掃描，發現沒有做交換的動作則表 示已經排序完成，所以只做了n-1次比較，時間複雜 度為O(n)。 2. 由於氣泡排序為相鄰兩者相互比較交換，並不會更 改其原本排列的順序，所以是穩定排序法。 3.只需一個額外的空間，所以空間複雜度為最佳。 4.此排序法適用於資料量小或有部份資料已經過排序。

15 範例程式：ch08_01.c 執行結果：

16 範例程式：ch08_02.c 執行結果：

17 選擇排序法 選擇排序法可使用兩種方式排序，一為在所有的資料中，當由大至小排序，則將最大值放入第一位置；若由小至大排序時，則將最大值放入位置末端。 例如當N筆資料需要由大至小排序時，首先以第一個位置的資料，依次向2、3、4 …N個位置的資料作比較。 如果資料大於或等於其中一個位置，則兩個位置的資料不變；若小於其中一個位置，則兩個位置的資料互換。

18 排序法的演算流程 首先找到此數列中最小值後與第一個元素交換。

19 接著從第二個值找起，找到此數列中(不包含第一個)的最小值，再和第二個值交換。
接著從第三個值找起，找到此數列中(不包含第一、二個)的最小值，再和第三個值交換。 最後從第四個值找起，找到此數列中(不包含第一、二、三個)的最小值，再和第四個值交換，則此排序完成。

20 選擇法分析 1. 無論是最壞清況、最佳情況及平均情況都需要找到 最大值(或最小值)，因此其比較次數為：(n-1)+(n-2)
+(n-3)+…+3+2+1= 次；時間複雜度為O(n2) 2. 由於選擇排序是以最大或最小值直接與最前方未排序 的鍵值交換，資料排列順序很有可能被改變，故不是 穩定排序法。 3. 只需一個額外的空間，所以空間複雜度為最佳。 4. 此排序法適用於資料量小或有部份資料已經過排序。

21 範例程式：ch08_03.c 執行結果：

22 插入排序法 插入排序法(Insert Sort)是將陣列中的元素，逐一與已排序好的資料作比較，再將該陣列元素插入適當的位置。如以下說明：
由小到大排序： 原始值：

23 插入法分析 1. 最壞及平均清況需比較(n-1)+(n-2)+(n-3)+…+3+2+1 = 次；時間複雜度為O(n2)，最好情況時間複雜
2. 插入排序是穩定排序法。 3. 只需一個額外的空間，所以空間複雜度為最佳。 4. 此排序法適用於大部份資料已經過排序或已排序資 料庫新增資料後進行排序。 5.插入排序法會造成資料的大量搬移，所以建議在鏈結 串列上使用。

24 範例程式：ch08_04.c 執行結果：

25 謝耳排序法 「謝耳排序法」是D. L. Shell 在1959年7月所發明的一種排序法，而該排序法直接以發明者命名。
其排序法的原理有點像是插入排序法，但它可以減少資料搬移的次數。 排序的原則是將資料區分成特定間隔的幾個小區塊，以插入排序法排完區塊內的資料後再漸漸減少間隔的距離。

26 謝耳法分析 1.任何情況的時間複雜度均為O(n3/2)。 2.謝耳排序法和插入排序法一樣，都是穩定排序。
3.只需一個額外空間，所以空間複雜度是最佳。 4.此排序法適用於資料大部份都已排序完成的情況。

27 範例程式：ch08_05.c 執行結果：

28 合併排序法 合併排序法(Merge Sort)的工作原理乃是針對已排序好的二個或二個以上的檔案，經由合併的方式，將其組合成一個大的且已排序好的檔案。 底下是數列3,1,4,7,5,9,6,2合併排序法的的排序過程：

29 條列方式的步驟 將N個長度為1的檔案合併成N/2個已排序妥當且 長度為2的檔案。 2. 將N/2個長度為2的檔案合併成N/4個已排序妥當
且長度為4的檔案。 3. 將N/4個長度為4的檔案合併成N/8個已排序妥當 且長度為8的檔案。 4. 將N/2i-1個長度為2i-1的檔案合併成N/2i個已排序 妥當且長度為2i的檔案。

30 合併排序法： 1. 合併排序法n筆資料一般需要約log2n次處理， 每次處理的時間複雜度為O(n)，所以合併排序
法的最佳情況、最差情況及平均情況複雜度為 O(nlogn)。 2. 由於在排序過程中需要一個與檔案大小同樣的 額外空間，故其空間複雜度O(n)。 3. 是一個穩定(stable)的排序方式。

31 快速排序法 快速排序法(Quick Sort)又稱分割交換排序法，是目前公認最佳的排序法。
假設有n筆記錄R1,R2,R3…Rn，其鍵值為k1,k2,k3…kn。快速排序法的步驟如下： 1. 取K為第一筆鍵值。 2. 由左向向找出一個鍵值Ki使得Ki>K。 3. 由右向左找出一個鍵值Kj使得Kj<K。 4. 若i<j則Ki與Kj交換，並繼續步驟的執行。 5. 若ij則將K與Kj交換，並以j為基準點將資料分為左右兩 部份。並以遞迴方式分別為左右兩半進行排序，直至 完成排序。

32 快速法分析 在最快及平均情況下，時間複雜度為O(nlog2n)。 最壞情況就是每次挑中的中間值不是最大就是最 小，其時間複雜度為O(n2)。
2. 快速排序法不是穩定排序法。 3. 在最差的情況下，空間複雜度為O(n)，而最佳情況 為O(log2n)。 4. 快速排序法是平均執行時間最快的排序法。

33 範例程式：ch08_06.c 執行結果：

34 堆積排序法 堆積(Heap Sort)是一種特殊的二元樹，可分為最大堆積樹及最小堆積樹兩種。 最大堆積樹滿足以下3個條件：
最小堆積樹則具備以下3個條件： 1.它是一個完整二元樹。 2.所有節點的值都大於或等於它左右子節點的值。 3.樹根是堆積樹中最大的。 1.它是一個完整二元樹。 2.所有節點的值都小於或等於它左右子節點的值。 3.樹根是堆積樹中最小的。

35 堆積的基礎-最大堆積 在堆積的節點中，最大值是根節點9，所有子節點的資料都等於或比父節點小，這種堆積稱為「最大堆積」（Max Heap），如下圖所示：

36 堆積的基礎-最小堆積 反過來，如果根節點的資料是最小，所有子節點的資料都等於或比父節點大，稱為「最小堆積」（Min Heap），如下圖所示：

37 建立最大堆積-實作 最大堆積是一棵完整二元樹，除了最高階層外，它是一棵完滿二元樹（Full Binary Tree），在實作上可以使用陣列來儲存最大堆積，如下圖所示：

38 建立最大堆積-索引計算 heap[]陣列儲存堆積資料，heap_len是目前堆積的元素數，索引值是從1開始，索引值0並沒有使用，此時堆積節點的索引值計算，如下所示： 右子節點索引 = 父節點索引 * 2 + 1 左子節點索引 = 父節點索引 * 2 父節點索引 = 子節點索引 / 2

39 建立最大堆積-插入節點(說明) 在最大堆積插入節點，首先將節點插入heap[]陣列的最後，也就是插入成為二元樹的葉節點。
然後與父節點進行比較，往上一一和其父節點比較，就可以將二元樹調整成為堆積。

40 建立最大堆積-插入節點(圖例1) 左邊的二元樹插入節點9，首先插入在陣列heap_len+1的索引位置，然後與其父節點5比較，因為比較大，所以對調，如下圖所示：

41 建立最大堆積-插入節點(圖例2) 因為節點9比較大，所以交換，最後和根節點8進行比較，比較大所以交換，最後就可以重建成堆積。函數shiftUp()就可以向上調整節點來重建堆積。

42 建立最大堆積-取出最大節點(說明) 從堆積取出最大節點，以最大堆積來說，就是根節點，同樣的，當刪除根節點後，就需要重新調整來建立堆積。

43 建立最大堆積-取出最大節點(圖例) 首先刪除根節點9，並且將它取代成最後一個節點5，然後從上至下，比較其子節點，因為比左子節點小，所以交換，然後再與子節點比較，比左子節6小，所以交換即可完成堆積的重建。

44 堆積法分析 在所有情況下，時間複雜度均為O (nlogn)。 堆積排序法不是穩定排序法。 只需要一額外的空間，空間複雜度為O (1)。

45 範例程式：ch08_07.c 執行結果：

46 基數排序法 基數排序法(Radix Sort)依比較的方向可分為最有效鍵優先(Most Significant Digit First:MSD)和最無效鍵優先(Least Significant Digit First:LSD)兩種。 MSD法是從最左邊的位數開始比較，而LSD則是從最右邊的位數開始比較。 底下的範例我們以LSD將三位數的整數資料來加以排序，它是依個位數、十位數、百位數來進行排序。

47 原始資料： 步驟一：把每個整數依其個位數字放到串列中： 26 95 7 34 60 168 171 259 372 45 88 133
1 2 3 4 5 6 7 8 9 資料 60 171 372 133 34 95 45 26 168 88 59 259

48 步驟二：再依其十位數字，依序放到串列中：
合併後成為： 步驟二：再依其十位數字，依序放到串列中： 60 171 372 133 34 95 45 7 168 88 59 259 十位數字 1 2 3 4 5 6 7 8 9 資料 133 34 45 59 259 60 168 171 372 88 95

49 步驟二：再依其百位數字，依序放到串列中：
合併後成為： 步驟二：再依其百位數字，依序放到串列中： 7 133 34 45 59 259 60 168 171 372 88 95 百位數字 1 2 3 4 5 6 7 8 9 資料 34 45 59 60 88 95 133 168 171 259 372

50 最後合併即完成排序： 基數法分析： 7 34 45 59 60 88 95 133 168 171 259 372 在所有情況下，時間複雜度均為O(nlogpk)，k是原始 資料的最大值。 2. 基數排序法是穩定排序法。 3. 基數排序法會使用到很大的額外空間來存放串列資 料，其空間複雜度為O(n*p)， n是原始資料的個數，p 是資料字元數；如上例中，資料的個數n=12，字元數 p=3。 4. 若n很大，p固定或很小，此排序法將很有效率。

51 範例程式：ch08_08.c 執行結果：

52 外部排序法 外部儲存裝置又可依照存取方式分為兩種方式，如循序存取(如磁帶)或隨機存取(如磁碟)。
要循序存取的檔案就像是串列一樣，我們必須事先走訪整個串列才有辦法進行排序。 而隨機存取的檔案就像是陣列，資料存取方便，所以相對的排序也會比循序存取快一些。 最常使用的就是合併排序法，它適用於循序存取的檔案。

53 直接合併排序法 直接合併排序法(Direct Merge Sort)是外部儲存裝置最常用的排序方法。它可以分為兩個步驟：
1.將欲排序的檔案分為幾個可以載入記憶體空間大 小的小檔案，再使用內部排序法將各檔案內的資 料排序。 2.將第一步驟所建立的小檔案每二個合併成一個檔 案。兩兩合併後，把所有檔案合併成一個檔案後 就可以完成排序了。

54 範例程式：ch08_09.c 以下的程式是直接把兩個已經排序好的檔案合併與排序成一個檔案。 執行結果：

55 範例程式：ch08_10.c 執行結果：

56 k路合併法(k-Way Merge) 它所需要的時間儘需logkn，也就是處理輸出入時間減少許多，排序的速度也因此可以加快。
首先我門來描述利用3路合併(3-way merge)來處理27個行程(Runs)的示意圖：

57 多相合併法(Polyphase Merge)
它可以使用少於2k個磁碟，卻能正確無誤地執行k-way合併。以下示範了如何進行多相合併。 下圖共有21個runs，使用2-way合併及3個磁帶T1、T2、T3來進行合併，假設這21個行程(已排序完畢，且令其長度為1)的表示方為Sn，其中S為行程大小，n為長度相同run的個數。 例如8個runs且長度為2，可表示成28。

58 2-way及3個磁碟的多項合併 Phase T1 T2 T3 合併狀況說明 1 113 18 empty 起始分佈情況 2 15 28
度變成2 3 35 23 將T15個長度為1的行程和T35個長度為2的行 程，合併到T2，其長度變成3 4 53 32 將T23個長度為3的行程和T33個長度為2的行 程,合併到T1，其長度變成5 5 51 82 將T12個長度為5的行程和T22個長度為3的行 程,合併到T3，其長度變成8 6 131 81 將T11個長度為5的行程和T31個長度為8的行 程，合併到T2，其長度變成13 7 211 將T21個長度為13的行程和T31個長度為8的 行程，合併到T1，其長度變成21