排序演算法（一）
- 2020 年 4 月 8 日
- 筆記
數組排序演算法
數組排序演算法是一個經典的演算法問題，這類排序演算法非常多，比如我們熟知的冒泡排序、插入排序、快速排序等演算法。這篇文章主要說一下五種排序演算法：
- 冒泡排序
- 選擇排序
- 插入排序
- 快速排序
- 希爾排序
排序方式是從小到大排列。
還需要一個交換函數，它很有用，它接收一個數組，兩個數組的索引，通過索引交換對應元素的位置，在排序演算法中會多次用到：
function swap(array: any[], a: number, b: number): void{ var temp = array[a]; array[a] = array[b]; array[b] = temp; }
1. 冒泡排序
冒泡排序的思路是：比較所有相鄰的兩個項，如果第一個比第二個大，則交換它們。
程式碼：
function bubbleSort<T>(array: T[]): T[]{ var len: number = array.length; for(let i = 0;i < len;i ++){ for(let j = 0;j < len - 1;j ++){ if(array[j] > array[j + 1]) // 當前值比它下一個要大就交換 swap(array, j, j + 1); } } return array; }
假如有這樣一個數組：[2, 4, 7, 5, 6, 1, 3]，它第一輪（內層循環完畢一次）的冒泡排序過程為：
2 and 4: [2, 4, 7, 5, 6, 1, 3]; 4 and 7: [2, 4, 7, 5, 6, 1, 3]; 7 and 5(swap): [2, 4, 5, 7, 6, 1, 3]; 7 and 6(swap): [2, 4, 5, 6, 7, 1, 3]; 7 and 1(swap): [2, 4, 5, 6, 1, 7, 3]; 7 and 3(swap): [2, 4, 5, 6, 1, 3, 7];
一輪循環完畢後會發現，最大的元素被排到了最右端，冒泡排序的每一輪循環結束後都會有一個大的元素「冒泡」到右端，下面是每一輪的冒泡過程：
initial: [2, 4, 7, 5, 6, 1, 3]; // start: [2, 4, 5, 6, 1, 3, 7]; [2, 4, 5, 1, 3, 6, 7]; [2, 4, 1, 3, 5, 6, 7]; [2, 1, 3, 4, 5, 6, 7]; [2, 1, 3, 4, 5, 6, 7]; [1, 2, 3, 4, 5, 6, 7]; [1, 2, 3, 4, 5, 6, 7];
優化
上面的冒泡排序程式碼中，第二層的循環語句可以優化。
for(let i = 0;i < len;i ++){ for(let j = 0;j < len - 1;j ++){ if(array[j] > array[j + 1]) // 當前值比它下一個要大就交換 swap(array, j, j + 1); } }
每一輪循環我們都要比較相鄰的兩項，第一輪循環後最右邊的元素變成了最大的元素，第二輪循環時就沒有必要再與它做比較了（倒數第二個元素與倒數第一個元素）。而第三輪循環時，最後兩個元素已經排好，也沒必要在與這兩個元素作比較了。因此內層循環可以寫成：
// 只在前 len - 1 - i 個元素中作比較 for(let j = 0;j < len - 1 - i;j ++){ if(array[j] > array[j + 1]) // 當前值比它下一個要大就交換 swap(array, j, j + 1); }
2. 選擇排序
選擇排序的思路是：選擇出數組中最小的一個元素，然後把它放在第一位，接著找出數組中第二小的元素將其放在第二位。
這種排序方法我們很容易能想到，在日常生活中我們可以先挑小的，最後挑選大的。在數組中如何從眾多元素中選到小的元素然後放入指定的位置是個難題。
我們可以假定第一個元素就是最小的元素，然後將它與其他的元素對比，如果有其他的元素比它還要小，就把我們假定的最小元素變成這個元素，直到遍歷完整個數組，最後就能找到最小的元素了，然後將最小的元素與第一個元素調換位置就 OK 了！
實現程式碼：
function selectionSort<T>(array: T[]): T[]{ var len = array.length; var min: number; // 因為 min 要與後面的元素作比較，因此 i 應小於 len - 1，這樣 min 後面才有元素 for(let i = 0;i < len - 1;i ++){ // 讓 min = i，當前 n 個元素排好之後，就不再關注這前 n 個元素了 min = i; // 假定最小的元素就是數組中還沒有排序的第一個元素 for(let j = i + 1;j < len;j ++){ if(array[min] > array[j]){ // 設定的「最小」元素卻比其它元素大，就把更小的元素的索引賦給 min min = j; } } // 判斷 min 與 i 是不是相等，要是相等說明內層循環的條件語句沒有執行 // i 與 min 相等就不需要交換了，數組索引相同嘛 if(i !== min){ swap(array, i, min); } } return array; }
判斷一個排序演算法是不是選擇排序也很到判斷，選擇排序每一輪總會把最小的元素找到並排好，因此如果一個數組原來是 [2, 3, 7, 5, 1, 4]，那麼它每一輪的元素順序是：
initial: [2, 3, 7, 5, 1, 4] // start: 1: [1, 3, 7, 5, 2, 4]; // 1 與 2 交換（數組第一項就排好了，第一項不再參與排序） 2: [1, 2, 7, 5, 3, 4]; // 2 與 3 交換（數組前兩項就排好了，前兩項不再參與排序） 3: [1, 2, 3, 5, 7, 4]; // 3 與 7 交換（數組前三項就排好了，前三項不再參與排序） 4: [1, 2, 3, 4, 7, 5]; // 4 與 5 交換 ...... 5: [1, 2, 3, 4, 5, 7]; // 5 與 7 交換 ......
3. 快速排序
快速排序是一個很常用的排序演算法，它的複雜度很小。冒泡排序、選擇排序都是雙層循環排序演算法，它們的時間複雜度都是 O(n^2)，而快速排序的時間複雜度為 O(nlog(n))。
快速排序時間複雜度小，但其排序演算法比較複雜。這裡直接說一下思路，然後再解釋為什麼要這樣做。
快速排序在排序時會選定一個元素作為 主元，在排完一輪後，我們可以把這個主元放到排序好後的位置上。也就是說通過一輪排序，我們選定的這個元素就會找到數組排好序之後相應的位置。然後我們就不用再排它了。這如何做到呢？
假如我們有這麼一個數組：[6, 23, 36, 4, 29, 44, 11, 10, 66]，我們選定的主元是數組中間的元素：29。選好後，把這個主元與數組最後一個元素交換，把主元放到最後。
然後弄兩個指針，一個指針指向數組最左側，另一個指針指向主元的前一個元素。
quick-pointer
當把小於主元的元素都放到它左邊，大於主元的元素都放到它右邊，這樣主元的位置也就確定了。
這兩個指針的運動規則：首先判斷左側指針對應的值是不是小於主元，如果小於，指針就往右移動，直到移動到大於主元的位置並暫停。然後開始移動右側的指針，知道移動到這個元素小於主元暫停。然後交換左右指針的元素。交換完後重複之前的操作，開始移動左側指針…..
quick-swap
每次移動指針時，我們都要判斷兩個指針的位置,當左側指針的索引大於等於右側指針的索引時，就停止，說明我們已經把主元對應的位置找到了。
quick-position
然後主元與兩指針指向的元素，這時就會發現，主元左側的元素都小於等於它，主元右側的元素都大於等於它。
交換主元
這樣一個元素就確定了位置，如何把別的元素也確定出正確的位置呢？我們剩餘的元素分為較小的數組，繼續通過上面的方法來確定位置（可以使用遞歸）。快速排序運用了分而治之的思想，把複雜的長數組分割成小的數組來管理。
分而治之
選取主元
主元應如何選取呢？最簡單的做法就是選擇數組最右端的元素作為主元。直接選定最右端的值作為主元有可能這個值剛好是最大的元素或者最小的元素，這樣效率就會降低。
另一個選定主元的方法是抽出數組的最左邊的元素、中間元素、最右端的元素，然後讓它們作比較，誰是中間值就讓它作為主元。我們可以這麼寫：
// left: 最左端的索引值，right：最右端的索引值 function getMedian<T>(left: number, right: number): T{ // T 是數組中的元素 var center = Math.floor((left + right) / 2); if(array[left] > array[center]){ swap(array, left, center); // left 應比 center 值小，不然就交換 } if(array[center] > array[right]){ swap(array, center, right); } if(array[left] > array[right]){ swap(array, left, right); } // 交換完畢後，把中間的值移動到右端 // 把 center 對應的值移動到 right - 1 即可 // 這是因為經過上面交換演算法之後，right 索引對應的元素一定比 center 對應的值要大 // 因此 right 就不再需要操作了，它比主元要大，本來就應在主元右端 swap(array, center, right - 1); // 返回主元 return array[right - 1]; }
整體程式碼：
// 最外層的函數接收數組 function quickSort<T>(array: T[]): T[]{ quick(0, array.length - 1); // 調用 quick 核心函數 function getMedian(left: number, right: number): T{ var center: number = Math.floor((left + right) / 2); // 左側節點比中間節點值要大，需要交換 if(array[left] > array[center]){ swap(array, left, center); } // 左側節點比右側節點值要大，需要交換 if(array[left] > array[right]){ swap(array, left, right); } // 中間節點比右側節點值要大，需要交換 if(array[center] > array[right]){ swap(array, center, right); } // 別忘了交換，把主元與倒數第二個元素交換 swap(array, center, right - 1); return array[right - 1]; } // 快速排序演算法核心函數 function quick(left: number, right: number): void{ // quick 函數是個遞歸函數，需要有一個出口 if(left >= right) return; // left 等於 right 時表明 left 與 right 指向同一個元素 var provit: T = getMedian(left, right); // right - 1 是因為主元不在倒數第一的位置，而是在倒數第二的位置 var l: number = left, r: number = right - 1; if(l === r) return; // 如果 l 與 r 相等了，就不要再走下面的程式了，說明經過分割後的數組長度只有 2，getMedia 已經排好序了 while(true){ // 先加加是因為左右指針指向的第一項都不用再比了，左邊第一項必定小於主元，而右邊指針指向的是主元 // l 變數是用來找到左側大於主元的索引 while(array[++ l] < provit){}; // r 變數是用來找到右側小於主元的索引 while(array[-- r] > provit){}; if(l < r){ // 當 l 小於 r 時才做交換 swap(array, l, r); }else{ // 當 l 大於等於 r，說明 break; } } // 把主元放到正確的位置，right - 1 是主元的索引 // 之所以 l 索引的元素與主元交換 // 是因為 l 指向左側第一個大於主元的元素 // 交換後主元左側的元素就都是小於等於主元的了 swap(array, l, right - 1); // 遞歸，主元把數組分割成了兩部分，將這兩部分進行排序（除了主元之外，現在的 l 就指向主元） quick(left, l - 1); quick(l + 1, right); } return array; }
說一下 quick 函數中，if(l === r) return; 的含義。考慮這麼一個數組：[2, 4, 7, 5, 6, 1, 3]。通過上面的程式碼可以知道，經過 getMedain 函數交換後，變成了下面的順序：
// 3 是主元 [2, 4, 7, 1, 6, 3, 5]
如果去掉 if(l === r) 的判斷語句。第一輪排序的結果將是（3 被放入正確的位置）：
[2, 1, 7, 4, 6, 3, 5] // 3 與 7 交換 [2, 1, 3, 4, 6, 7, 5]
然後分割數組，3 左側就被分成了 [2, 1] 兩個元素的數組。然後對這個數組排序，經過 getMedain 函數排序後，這個數組將是已經排好的（在 getMedain 函數中，center 將等於 0，最後的 swap(array, center, right – 1); 其實就是自己交換自己），如果不加 if(l === r) 做判斷，就會走下面的循環，然後就會把本來排好序的 [1, 2] 又交換成 [2, 1]。
上面的方法比較麻煩，也可以不做比較，直接將數組的最後一項作為主元：
function quickSort<T>(array: T[]): T[]{ sort(0, array.length - 1); function sort(left: number, right: number){ if(left >= right) return; var l = left, r = right, pivot = array[r]; //把所有比主元小的數放在左邊大的數放在右邊 while(l < r){ while(l < r && array[l] <= pivot) l ++; // 將較大的值放在右邊，如果沒有比主元大的數就是將自己賦值給自己（i 等於 j） array[r] = array[l]; while(r > l && array[r] >= pivot) r -- ; // 將較小的值放在左邊，如果沒有找到比主元小的數就是將自己賦值給自己（i 等於 j） array[l] = array[r]; } // 將主元放至中央位置完成一次循環（這時候 j 等於 i ） array[l] = pivot; sort(left, l - 1); sort(l + 1, right); } return array; }
4. 插入排序
插入排序的思路：假定數組的第一項已經排好，我們從第二項開始，如果第二項元素比第一項元素要小，兩者交換；然後開始排列數組的第三項，第三項會與前兩項作比較，它是應插入第二項之前呢，還是插入第一項之前呢，還是原地不動（說明它比前兩項都大）？以此類推，第四項會與前面三項作比較。
實現程式碼：
function insertionSort<T>(array: T[]): T[]{ var len = array.length; var temp: T; // 臨時保存數組中的元素 for(let i = 1;i < len;i ++){ let j = i; // j 是為下面的 while 循環服務的 temp = array[i]; // 先保存當前的元素 // j > 0，不然 j - 1 沒有意義 while(j > 0 && array[j - 1] > temp){ // 如果當前的元素（temp）比它之前的元素（j - 1）要小 // 就把前面的元素賦給當前元素，相當於把前面的元素後移 array[j] = array[j - 1]; j -= 1; // 別忘了 j --，繼續與 temp 作比較 } // 比較完後，把臨時保存的元素插入 array[j] = temp; } return array; }
在插入排序演算法中，每一趟排序左側都會「冒」出比較小的元素，但不一定是最小的。以數組 [3, 5, 1, 4, 2] 為例：
initail: [3, 5, 1, 4, 2]; // start: [3, 5, 1, 4, 2]; // 第一趟，元素 5 比前面的任何元素都要大； [1, 3, 5, 4, 2]; // 第二趟，元素 1 比前面的任何元素都小（插入到最左側）； [1, 3, 4, 5, 2]; // 第三趟，元素 4 要比前面的 5 小，插入到 5 之前； [1, 2, 3, 4, 5]; // 第四趟：元素 2 與前面元素比較，它被插入到元素 1 之後。
5. 希爾排序
希爾排序是插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。在上面的插入排序中，有不好的一點，假如最小的元素卻在數組的最右端，那麼它就要把前面的元素一個一個都移動，最終插入到最左側，這顯然是很耗時的，希爾排序就是為了優化這樣的情況。
希爾排序的原理：首先確定一個增量，一般這個增量的初始值是數組長度的一半。增量表示原始數組要分成幾份（5 份），每一份中相鄰元素之間的索引相差 5。
shell-gap
被分成五份，分別是：(2,6,10) (7,3) (4,11) (1,9) (8,5)
如果分成三份，則是：
分三組
分別是：(2,1,3,5) (7,8,11,10) (4,6,9)
這樣不太好看，可以看成類似向量的形式，兩兩一組：
(2,1) (7,8) (4,6) (1,3) (8,11) (6,9) (3,5) (11,10)
例如：
原數組：[2, 7, 4, 1, 8, 6, 3, 11, 9, 5, 10]; 增量：5 分組：(2,6) (7,3) (4,11) (1,9) (8,5) (6,10); 即：(2,6,10) (7,3) (4,11) (1,9) (8,5) // 5 組 // 排序： 第一對：2 和 6 不需要交換； 第二對：7 和 3 需要交換：[2, 3, 4, 1, 8, 6, 7, 11, 9, 5, 10]; 第三對：4 和 11 不需要交換； 第四對：1 和 9 不需要交換； 第五對：8 和 5 需要交換：[2, 3, 4, 1, 5, 6, 7, 11, 9, 8, 10]; 第六對：6 和 10 不需要交換； --------------------------------------------------------- 增量變成 5 / 2 == 2 分組：(2,4) (3,1) (4,5) (1,6) (5,7) (6,11) (7,9) (11,8) (9,10) 即：(2,4,5,7,9,10) (3,1,6,11,8) // 兩組 // 排序（只說一下需要交換的組）： 第二對：3 和 1 交換：[2, 1, 4, 3, 5, 6, 7, 11, 9, 8, 10]; 第八對：11 和 8 交換：[2, 1, 4, 3, 5, 6, 7, 8, 9, 11, 10]; 11 和 8 是屬於第二組，對調完之後，還要判斷 8 之前的元素有沒有大於它的（3,1,6 都比它小，因此不需要交換） ---------------------------------------------------------- 增量：2 / 2 == 1 分組：(2,1) (1,4) (4,3) (3,5) (5,6) (6,7) (7,8) (8,9) (9,11) (11,10) 即：(2,1,4,3,5,6,7,8,9,11,10) // 一組 // 排序（只說一下需要交換的組）： 第三對：2 和 1 交換：[1, 2, 4, 3, 5, 6, 7, 8, 9, 11, 10]; 第三對：4 和 3 交換：[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10]; // 交換完之後，繼續判斷 3 之前的元素有沒有比它大的，顯然沒有 最後一對：11 和 10 交換：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]; // 交換完之後，繼續判斷 10 之前的元素有沒有比它大的，顯然沒有 // 排好啦
程式碼實現：
function shellSort<T>(array: T[]): T[]{ let len = array.length; // 設定增量 var gap = Math.floor(len / 2); // 增量最小等於 1，也就是普通的插入排序的增量 while (gap > 0) { for (var i = gap; i < len; i++) { var j = i - gap; // j 最小等於 0 while (j >= 0 && array[j] > array[gap + j]) { swap(array, j, gap + j); j -= gap; } } gap = Math.floor(gap / 2); } return array; }
如果把 gap 替換成 1，不再有最外層循環，其實就是一個普通的插入排序（增量是 1）。設置增量可以減少交換次數，在希爾排序中，可以將兩個距離很遠的元素直接交換而不需要一個一個的移動，到最後 gap 變成 1 時，需要移動的元素就變得很少了。你可以試驗一下，在最內層循環中都列印一下數組，會發現希爾排序要比插入排序的交換次數少。
對比
左邊是插入排序，右邊是希爾排序。
