排序的相關知識 排序(Sorting)是指將一群資料，按特定規則調換位置，使資料具有某種次序關係(遞增或遞減)。

Presentation on theme: "排序的相關知識 排序(Sorting)是指將一群資料，按特定規則調換位置，使資料具有某種次序關係(遞增或遞減)。"— Presentation transcript:

1 排序的相關知識 排序(Sorting)是指將一群資料，按特定規則調換位置，使資料具有某種次序關係(遞增或遞減)。 例如資料庫內可針對某一欄位進行排序，而此欄位稱為「鍵(key)」，欄位裡面的值我們稱之為「鍵值(value)」。

2 排序資料的移動方式 在排序的過程中，資料的移動方式可分為「直接移動」及「邏輯移動」兩種。
「直接移動」是直接交換儲存資料的位置，而「邏輯移動」並不會移動資料儲存位置，僅改變指向這些資料的輔助指標的值。 兩者間優劣在於直接移動會浪費許多時間進行資料的更動，而邏輯移動只要改變輔助指標指向的位置就能輕易達到排序的目的。

3 排序的好處 1.資料較容易閱讀。 2.資料較利於統計及整理。 3.可大幅減少資料搜尋的時間。

4 排序的分類 排序依執行時所使用的記憶體可分為： 內部排序：排序的資料量小，可以完全在記憶體內進行排序。
外部排序：排序的資料量無法直接在記憶體內進行排序，而必須使用到輔助記憶體(如硬碟)。

5 排序演算法的分析 排序演算法的好壞可由以下幾點決定： 演算法是否穩定 時間複雜度（Time complexity）
空間複雜度（Space complexity）

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

7 時間複雜度 當資料量相當大時，排序演算法所花費的時間就顯得相當重要。
排序演算法的時間複雜度可分為最好情況(Best Case)、最壞情況(Worst Case)及平均情況(Average Case)。最好情況就是資料已完成排序，例如原本資料已經完成遞增排序了，如果再進行一次遞增排序所使用的時間複雜度就是最好情況。 最壞情況是指每一鍵值均須重新排列，簡單的例子如原本為遞增排序重新排序成為遞減，就是最壞情況

8 空間複雜度 空間複雜度就是指演算法在執行過程所需付出的額外記憶體空間。
例如所挑選的排序法必須藉助遞迴的方式來進行，那麼遞迴過程中會使用到的堆疊就是這個排序法必須付出的額外空間。 另外，任何排序法都有資料對調的動作，資料對調就會暫時用到一個額外的空間，它也是排序法中空間複雜度要考慮的問題。排序法所使用到的額外空間愈少，它的空間複雜度就愈佳。例如氣泡法在排序過程中僅會用到一個額外的空間，在所有的排序演算法中，這樣的空間複雜度就算是最好的。

9 內部排序法 排序名稱 排序特性 簡單排序法 1.氣泡排序法(Bubble Sort) (1)穩定排序法
排序名稱 排序特性 簡單排序法 1.氣泡排序法(Bubble Sort) (1)穩定排序法 (2)空間複雜度為最佳，只需一個額外空間O(1) 2.選擇排序法(Selection Sort) (1)不穩定排序法 3.插入排序法(Insertion Sort) 4.謝耳排序法(Shell Sort) 高等排序法 1.快速排序法(Quick Sort) (2)空間複雜度最差O(n)最佳O(log2n) 2.堆積排序法(Heap Sort)

10 氣泡排序法 氣泡排序法又稱為交換排序法，是最簡單的排序法之一。將資料放在同一陣列中，由第一個元素開始，比較相鄰的陣列元素大小，若大小順序有誤，則對調後再進行下個元素的比較。如此掃瞄過一次之後就可確保最後一個元素是正確的。接著再進行第二次掃瞄，直到完成排序。

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

12 改良氣泡排序法 傳統氣泡排序法有個缺點是：不管資料是否已排序完成都會執行n*(n-1)/2次，而我們可以藉由在程式中加入一判斷式加以判斷何時可以提前中斷程式，又可得到正確的資料

13 選擇排序法 選擇排序法是從所有待排序的資料中找出最小(或最大)鍵值，將該筆記錄與第一筆記錄對調後，再從第二筆以後的資料中重覆做一樣的動作，直到完成排序為止。

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

15 插入排序法 插入排序法(Insert Sort)是將陣列中的元素，逐一與已排序好的資料作比較，再將該陣列元素插入適當的位置。

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

17 謝耳排序法 「謝耳排序法」其排序法的原理有點像是插入排序法，但它可以減少資料搬移的次數。排序的原則是將資料區分成特定間隔的幾個小區塊，以插入排序法排完區塊內的資料後再漸漸減少間隔的距離。

18 謝耳排序法分析 謝耳排序法和插入排序法一樣，都是穩定排序。 只需一個額外空間，所以空間複雜度是最佳。
此排序法適用於資料大部份都已排序完成的情況。

19 合併排序法 合併排序法(Merge Sort)的工作原理乃是針對已排序好的二個或二個以上的檔案，經由合併的方式，將其組合成一個大的且已排序好的檔案。底下是數列3,1,4,7,5,9,6,2合併排序法的的排序過程。 3、1、4、7、5、9、6、2 1、3、4、7、5、9、2、6 1、3、4、7、2、5、6、9 1、2、3、4、5、6、7、9 上面展示的合併排序法例子是一種最簡單的合併排序，又稱為2路(2-way)合併排序

20 合併排序法排序步驟 將N個長度為1的檔案合併成N/2個已排序妥當且長度為2的檔案。
將N/2i-1個長度為2i-1的檔案合併成N/2i個已排序妥當且長度為2i的檔案。

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

22 快速排序法 快速排序法又稱分割交換排序法，是目前公認最佳的排序法。它的原理和氣泡排序法一樣都是用交換的方式，不過它會先在資料中找到一個虛擬的中間值，把小於中間值的資料放在左邊而大於中間值的資料放在右邊，再以同樣的方式分別處理左右兩邊的資料，直到完成為止。

23 快速排序法的步驟 取K為第一筆鍵值 由左向右找出一個鍵值Ki使得Ki>K 由右向左找出一個鍵值Kj使得Kj<K
若i<j則Ki與Kj交換，並繼續步驟的執行 若ij則將K與Kj交換，並以j為基準點將資料分為左右兩部份。並以遞迴方式分別為左右兩半進行排序，直至完成排序。

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

25 堆積排序法 堆積排序法使用到了二元樹的技巧，它是利用堆積樹來完成排序。堆積是一種特殊的二元樹，可分為最大堆積樹及最小堆積樹兩種。 堆積排序法就是利用這種特性把堆積樹的樹根移走，再將剩下的節點重新建立堆積樹，重排一次就表示完成一個值的排序，直到剩最後一個節點時，排序也完成了。

26 最大堆積樹 它是一個完整二元樹。 所有節點的值都大於或等於它左右子節點的值。 樹根是堆積樹中最大的。

27 最小堆積樹 它是一個完整二元樹。 所有節點的值都小於或等於它左右子節點的值。 樹根是堆積樹中最小的。

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