《演算法圖鑑》第二章：排序
繼《演算法圖鑑》第一章：資料結構 發布後，已經過了兩週，近期週末期間活動稍多又碰上補班，所以才遲遲沒有更新 Medium 內容。
何謂排序 ( Sort )？
意指將資料 ( data ) 由小到大或由大到小重新排列。
排序是基本問題，接著將針對書中介紹的各式演算法做心得整理。
氣泡排序 ( Bubble Sort )
- 氣泡排序 ( Bubble Sort ) 是依序反覆進行「將相鄰的兩個元素倆倆相比後，依據大小重新排列」，直到資料完全是由小到大或由大到小排列。
氣泡排序要多少執行時間？
氣泡排序的比較次數會隨著回合數遞減，例如第一回合 ( n - 1 ) 次、第二回合 ( n - 2 ) 次，一直到第 ( n - 1 ) 回的 1 次。所以比較的次數與排列順序無關，只跟資料的數量有關。
最極端的時間：由小到大排列，且完全不必重新排列 ; 反之，若資料一樣但是由大到小排列時，每次比較後都需要做對調，執行時間會變成 O(n²)。
選擇排序 ( Selection Sort )
- 選擇排序 ( Selection Sort ) 是反覆進行「搜尋數列中的最小 / 大值，將它與最左邊的數對調」，直到資料完全是由小到大或由大到小排列。其中搜尋數列中最小 / 大值的方法為線性搜尋。
選擇排序要多少執行時間？
因為使用線性搜尋，選擇排序的比較次數會隨著回合數遞減，例如第一回合 ( n — 1 ) 次、第二回合 ( n — 2 ) 次，一直到第 ( n — 1 ) 回的 1 次。所以比較的次數與排列順序無關，只跟資料的數量有關，這與氣泡排序相同。
選擇排序的執行時間與氣泡排序一樣會是 O(n²)。
插入排序 ( Insertion Sort )
- 插入排序法 ( Insertion Sort ) 是從數列左邊開始，往右依序排序下去。執行過程中將會將數分為已排序及未排序，已排序的數依序排列於左側，尚未排序的數則在已排序數右邊。每回合由未排序中的第一個數與已排序的數做比較，並插入到已排序中的適當位置。
插入排序要多少執行時間？
若數的原始排法都與排序後的數列相反，插入排序的執行時間最糟會與氣泡排序及選擇排序一樣為 O(n²)。
堆積排序 ( Heap Sort )
- 由小排到大 ⇒ Min Heap; 由大排到小 ⇒ Max Heap
- Max Heap: 在每一個子樹中，根 ( root ) 之「數值」要比兩個子節點的「數值」還要大，見圖 ( a )。
- Min Heap:在每一個子樹中，根 ( root ) 之「數值」要比兩個子節點的「數值」還要小，見圖 ( b )。
參考資料：
堆積排序要多少執行時間？
堆積排序最初要將 n 個數儲存到堆積中的時間是 O(n log n)。雖然是一個一個追加數到空的堆積中，但是堆積的高小於 log2(n)，所以每一次追加所需時間為 O(log n)。
每回合取出最大/小值，再重新排列堆積，所需時間為 O(log n) 。當回合數為 n 時，整體時間即為 O(n log n)。
到目前為止，跟氣泡排序、選擇排序和插入排序的 O(n²) 相比，堆積排序處理速度最快。但資料結構會相對複雜，建置維護則也隨之變得複雜。
合併排序 ( Merge Sort )
- 合併排序 ( Merge Sort )，將要排序的數列分割成兩個長度相近的數列，直到無法再分割時，再合併各組數列。合併時勢將已經排序過的兩個數列合併成一個排序完成的數列。反覆進行一樣的操作，直到全部的數列合併成一個數列。
合併排序要多少執行時間？
數的分割不需要耗費時間。要合併兩數列時，只需反覆比較第一個數，並將較小的數移至上一層中，所以執行時間跟兩個數列的長度有關。
同一階層中合併的執行時間，取決於該層的數有多少個。
不管哪一層都是 n 個數，所以每一層的執行時間是 O(n)，n 個數在被合併成一個數列之前被對半分的層數為 log2(n)，所以整體的執行時間是 O(n log n) ，與堆積排序一樣。
快速排序 ( Quicksort )
- 快速排序( Quicksort ) 是從數列中，隨機選擇一個數作為基準，接著將剩下的數分為「比基準值小的數」和「比基準值大的數」兩個群組，只要排序完這兩個群組裡的數，即可完成整體排序。
- 快速排序是分治法 ( Divide and Conquer ) 的一種。就是將原問題拆分成兩個子問題，再分別解決兩個子問題。
- 這樣在演算法內部又使用相同演算法的情況，稱為「遞迴 ( Recursive ) 」。
快速排序要多少執行時間？
為了分解出子問題而選擇基準值時，若每次都選擇會讓兩個子問題大小是原問題一半的基準值，快速排序的時間與合併排序會變成相同，為 O(n log n) 。
