跳至內容
English
Algorithm PUBLISHED UPDATED

認識演算法：各種比較排序

在 認識演算法：啟程 這篇文章中，我們初步了解了什麼是演算法，以及如何好的設計演算法和評估它的效率等，接下來我們需要深入細節去認識和分析各種常見的演算法。本篇會聚焦在認識常見的「比較排序」相關演算法。

比較排序這一類型的演算法有一個共同特點是，它們完全依賴比較兩個元素（aia_i 和 aja_j）的相對大小（例如 ai≤aja_i \leq a_j 或 ai>aja_i > a_j）來獲得排序資訊。演算法不能「偷看」元素的實際數值，也不能用任何其他方式來獲取順序。

用簡單的比喻來理解，可以想像有一堆重量不同的石頭，但我們手邊只有一個天秤。我們無法讀取石頭上標示的克數，因此唯一能做的就是把任意兩顆石頭放到天秤上，看看哪邊比較重。所有比較排序法，就像是只用這個天秤來給所有石頭排序的策略。

了解什麼是比較排序後，下面我們會開始正式的介紹各種比較排序類型的演算法。

以下是本篇文章的目錄：

  1. 插入排序(Insertion Sort)
  2. 合併排序(Merge Sort)
  3. 堆積排序(Heapsort)
  4. 快速排序(Quicksort)
  5. 引入「隨機化」版本的快速排序
  6. 小結

插入排序(Insertion Sort)

插入排序演算法的實作邏輯模擬了整理撲克牌的過程，也就是逐一拿起未排序的牌，並將它插入到手中已排序牌組的正確位置。

插入排序在特定場景下具有高效性，且它是一種模擬人類直覺思維的排序方式，因此非常容易理解與實作。從上述的說明中可以推知插入排序的價值在於它的簡單性和在小型或近乎排序的資料集上的高效表現。但相反的，在處理大規模、無序的資料時，插入排序的二次增長執行時間使它不是一個好的選擇。

插入排序完整的實作邏輯和步驟

插入排序的核心邏輯是將陣列分為兩個部分：一個是已排序的子陣列，另一個是未排序的子陣列。演算法會依序從未排序部分取出元素，然後在已排序部分中找到正確的位置並插入。

用虛擬碼表示如下：

INSERTION-SORT(A, n)
1 for i = 2 to n
2   key = A[i]
3   // 將 A[i] 插入已排序的子陣列 A[1:i-1] 中
4   j = i - 1
5   while j > 0 and A[j] > key
6     A[j+1] = A[j]
7     j = j - 1
8   A[j+1] = key

使用 JavaScript 撰寫插入排序演算法

/**
 * 使用插入排序演算法對陣列進行原地排序 (in-place sort)。
 * @param {number[]} arr - 要排序的數字陣列。
 * @returns {number[]} - 返回排序後的同一個陣列。
 */
function insertionSort(arr) {
  // 陣列的長度
  const n = arr.length;

  // 外部迴圈從第二個元素開始，因為第一個元素自身已構成一個已排序的子陣列。
  // 這對應虛擬碼中的 "for i = 2 to n"。
  // 在 0-based 索引中，這意味著從索引 1 開始。
  for (let i = 1; i < n; i++) {
    // `key` 是當前要插入到已排序部分的元素。
    // 這對應虛擬碼中的 "key = A[i]"。
    let key = arr[i];

    // `j` 指向已排序子陣列的最後一個元素。
    // 這對應虛擬碼中的 "j = i - 1"。
    let j = i - 1;

    // 將已排序子陣列中比 `key` 大的元素向右移動一個位置。
    // 這對應虛擬碼中的 "while j > 0 and A[j] > key"。
    // 注意，在 0-based 索引中，條件 j > 0 變為 j >= 0。
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }

    // 將 `key` 插入到正確的位置。
    // 這對應虛擬碼中的 "A[j + 1] = key"。
    arr[j + 1] = key;
  }

  // 返回排序後的陣列
  return arr;
}

以下也提供無註解的乾淨版本：

function insertionSort(arr) {
  const n = arr.length;

  for (let i = 1; i < n; i++) {
    let key = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }

    arr[j + 1] = key;
  }

  return arr;
}

插入排序的效率分析

經過嚴謹的數學證明，插入排序在最差情況下的執行時間為 Θ(n2)\Theta(n^2)；在最好情況下的執行時間為 Θ(n)\Theta(n)；在平均情況下的執行時間為 Θ(n2)\Theta(n^2)。

以下我們用比較直觀的理解進行說明：

合併排序(Merge Sort)

合併排序是一種分治法(divide-and-conquer) 演算法(關於分治法，認識演算法：啟程 這篇文章中的 演算法設計策略 段落有撰寫相關說明)，它將待排序的序列遞迴地(recursively)分成兩半，直到每個子序列只剩一個元素，然後再將這些已排序的子序列兩兩合併，最終組合成一個完全排序的序列。

在演算法設計中，存在多種解決問題的策略，而合併排序所使用的「分治法」是一種非常強大的設計技巧。相較於插入排序所使用的「增量法」(incremental method)，分治法提供了一種截然不同的思路，這種思路設計出來的演算法通常在效率上有著顯著的提升，尤其是在處理大規模資料時。

這也帶來合併排序的其中一項優勢就是更優的時間複雜度——高效性。合併排序在最差情況下的執行時間為 Θ(nlg⁡n)Θ(n \lg n)。相比之下，插入排序在最差情況下的執行時間為 Θ(n2)Θ(n^2)。對數函數 (lg⁡n)(\lg n) 的增長速度遠慢於線性函數 (n)(n)，因此當輸入的資料量 nn 變得非常大時，合併排序的效率會遠遠勝過插入排序。

合併排序還有另一項優勢是適用於所有情況——穩定性。不同於插入排序的執行時間會根據輸入資料的已排序程度而劇烈變化——從最好情況的 Θ(n)Θ(n) 到最差情況的 Θ(n2)Θ(n^2)，合併排序在最好、最差及平均情況下的執行時間都是 Θ(nlg⁡n)Θ(n \lg n)。這使得它的效能是可預測且穩定的。

合併排序雖然擁有高效性和穩定性的優勢，但它在實作時需要額外的陣列空間，因此在空間效率上不如插入排序(Insertion Sort)，以及下面段落將會介紹到的堆積排序(Heapsort)和快速排序(Quicksort)。

合併排序完整的實作邏輯和步驟

合併排序的實作邏輯完美體現了「分治法」的三個核心步驟：分解(Divide)、征服(Conquer) 和 合併(Combine)。

整個演算法我們可以用一個主要的遞迴程序——負責遞迴地分解與征服，以及一個輔助的合併程序——負責關鍵的合併步驟來組成。

首先，主要的遞迴程序用虛擬碼表示如下：

MERGE-SORT(A, p, r)
1  if p >= r  // 如果子陣列只有零個或一個元素，則直接返回
2    return
3  q = floor((p + r) / 2)  // 計算中點，將陣列一分為二
4  MERGE-SORT(A, p, q)  // 遞迴排序左半邊
5  MERGE-SORT(A, q + 1, r)  // 遞迴排序右半邊
6  MERGE(A, p, q, r)  // 將已排序的左右兩半合併

這個函式的作用是遞迴地將陣列對半分割，直到子陣列只剩一個元素。

再來，輔助的合併程序用虛擬碼表示如下：

MERGE(A, p, q, r)
1  n_L = q - p + 1  // 計算左邊子陣列的長度
2  n_R = r - q  // 計算右邊子陣列的長度
3  let L[0 : n_L - 1] and R[0 : n_R - 1] be new arrays
4  for i = 0 to n_L - 1  // 將 A[p:q] 的內容複製到 L
5    L[i] = A[p + i]
6  for j = 0 to n_R - 1  // 將 A[q+1:r] 的內容複製到 R
7    R[j] = A[q + j + 1]

8  i = 0  // i 是 L 中最小剩餘元素的索引
9  j = 0  // j 是 R 中最小剩餘元素的索引
10 k = p  // k 是 A 中等待被填入位置的索引

11 // 當 L 和 R 都還有未合併的元素時
12 while i < n_L and j < n_R
13   if L[i] <= R[j]
14     A[k] = L[i]
15     i = i + 1
16   else
17     A[k] = R[j]
18     j = j + 1
19   k = k + 1

20 // 如果 L 或 R 其中一個已經合併完畢，將另一個剩餘的元素全部複製到 A 的尾部
21 while i < n_L
22   A[k] = L[i]
23   i = i + 1
24   k = k + 1
25 while j < n_R
26   A[k] = R[j]
27   j = j + 1
28   k = k + 1

這個函式是合併排序的核心，負責將兩個已排序的相鄰子陣列 A[p:q] 和 A[q+1:r] 合併成一個單一的、已排序的子陣列 A[p:r]。

使用 JavaScript 撰寫合併排序演算法

/**
 * 主要遞迴函式：MERGE-SORT
 * 使用分治法對 arr[left...right] 進行排序
 * @param {number[]} arr - 要排序的目標陣列
 * @param {number} left - 子陣列的起始索引
 * @param {number} right - 子陣列的結束索引
 */
function mergeSort(arr, left, right) {
  // 1. 基本情況 (Base Case)：遞迴的終止條件
  // 如果 left >= right，代表子陣列只有一個或零個元素，已經是排序狀態
  if (left >= right) {
    return;
  }

  // 2. 分解 (Divide)：找到子陣列的中間點
  // 為了避免 (left + right) 可能造成的整數溢位，使用 left + floor((right - left) / 2) 更為穩健
  const mid = left + Math.floor((right - left) / 2);

  // 3. 征服 (Conquer)：遞迴地對左右兩個子陣列進行排序
  mergeSort(arr, left, mid);      // 排序左半邊
  mergeSort(arr, mid + 1, right); // 排序右半邊

  // 4. 合併 (Combine)：將兩個已排序的子陣列合併回來
  merge(arr, left, mid, right);
}

/**
 * 輔助合併函式：MERGE
 * 將 arr[left...mid] 和 arr[mid+1...right] 這兩個已排序的子陣列合併
 * @param {number[]} arr - 目標陣列
 * @param {number} left - 左邊子陣列的起始索引 (0-based)
 * @param {number} mid - 分割點索引
 * @param {number} right - 右邊子陣列的結束索引
 */
function merge(arr, left, mid, right) {
  // --- 準備階段 ---
  // 計算左右兩個子陣列的長度
  const n1 = mid - left + 1; // 對應虛擬碼的 n_L
  const n2 = right - mid;    // 對應虛擬碼的 n_R

  // 建立新的臨時陣列 L 和 R
  let L = new Array(n1);
  let R = new Array(n2);

  // 使用迴圈將資料從原始陣列複製到臨時陣列中
  for (let i = 0; i < n1; i++) {
    L[i] = arr[left + i];
  }
  for (let j = 0; j < n2; j++) {
    R[j] = arr[mid + 1 + j];
  }

  // --- 合併階段 ---
  // 初始化三個索引指標
  let i = 0; // 指向 L 陣列的目前元素
  let j = 0; // 指向 R 陣列的目前元素
  let k = left; // 指向原始陣列 arr 中，下一個要被填入的位置

  // 核心合併迴圈：不斷比較 L 和 R 的頂部元素，將較小者放入 arr
  while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
      arr[k] = L[i];
      i++; // L 的指標向後移動
    } else {
      arr[k] = R[j];
      j++; // R 的指標向後移動
    }
    k++; // arr 的寫入指標向後移動
  }

  // --- 處理剩餘元素 ---
  // 當上述迴圈結束，代表 L 或 R 其中之一已完全合併
  // 以下兩個 while 迴圈只會有一個被執行

  // 如果 L 還有剩餘元素，將它們全部複製到 arr 的尾部
  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }

  // 如果 R 還有剩餘元素，將它們全部複製到 arr 的尾部
  while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
  }
}

以下也提供無註解的乾淨版本：

function mergeSort(arr, left, right) {
  if (left >= right) {
    return;
  }

  const mid = left + Math.floor((right - left) / 2);

  mergeSort(arr, left, mid);
  mergeSort(arr, mid + 1, right);

  merge(arr, left, mid, right);
}

function merge(arr, left, mid, right) {
  const n1 = mid - left + 1;
  const n2 = right - mid;

  let L = new Array(n1);
  let R = new Array(n2);

  for (let i = 0; i < n1; i++) {
    L[i] = arr[left + i];
  }
  for (let j = 0; j < n2; j++) {
    R[j] = arr[mid + 1 + j];
  }

  let i = 0;
  let j = 0;
  let k = left;

  while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
      arr[k] = L[i];
      i++;
    } else {
      arr[k] = R[j];
      j++;
    }
    k++;
  }

  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }

  while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
  }
}

合併排序的效率分析

經過嚴謹的數學證明，合併排序在最差情況、最好情況與平均情況下的執行時間均為 Θ(nlg⁡n)Θ(n \lg n)。

這裡會用比較直觀的方式來進行說明，我們可以想像它的遞迴過程形成了一棵「遞迴樹」(recursion tree)。

  1. 樹的高度(遞迴深度)：演算法每次都將問題規模切成兩半(n -> n/2 -> n/4 ...)，直到問題規模變成 1。這個過程就像不斷地問「需要對 n 除以多少次 2 才能得到 1？」，這個次數正好就是以 2 為底的對數，即 lg⁡n\lg n。所以，這棵遞迴樹的高度大約是 lg⁡n\lg n 層（嚴格來說是 lg⁡n+1\lg n + 1 層）。

  2. 每層的工作量：在遞迴樹的每一層，雖然子問題的數量加倍了，但每個子問題的規模都減半了。例如，第一層是將兩個大小為 n/2n/2 的子陣列合併，總工作量是 c⋅(n/2)+c⋅(n/2)=c⋅nc \cdot (n/2) + c \cdot (n/2) = c \cdot n。第二層是將四個大小為 n/4n/4 的子陣列合併，總工作量是 4⋅(c⋅n/4)=c⋅n4 \cdot (c \cdot n/4) = c \cdot n。你會發現，在樹的每一層，合併操作的總工作量都是一個與 nn 成正比的常數，我們稱之為 Θ(n)Θ(n)。

  3. 總工作量：既然樹的高度是 Θ(lg⁡n)Θ(\lg n)，而每一層的工作量都是 Θ(n)Θ(n)，那麼總工作量自然就是將這兩者相乘，得到 Θ(nlg⁡n)Θ(n \lg n)。

簡單來說，合併排序的效率來源於它巧妙地將排序工作分散到 lg⁡n\lg n 個層級中，並且確保每個層級的總工作量都保持在 nn 的規模。

堆積排序(Heapsort)

堆積排序是一種利用堆積(Heap)這個資料結構的特性，先將待排序的陣列重構成一個最大堆積(Max-Heap)，然後反覆將堆積中的最大元素——也就是根節點——取出並放到陣列末端，最終達成排序的演算法。

堆積排序結合了合併排序和插入排序的優點，是一個兼具效率與空間效益的演算法。在時間效率上，堆積排序的時間複雜度為 O(nlg⁡n)O(n \lg n)，這與合併排序一樣，是基於比較模型的排序演算法中，漸進最佳(asymptotically optimal) 的效率。在空間效率上，堆積排序是一種原地排序(in-place sorting) ，這意味著在排序過程中，它只需要常數個額外的儲存空間，這一點與插入排序相似，但優於需要額外陣列空間的合併排序。

然而，在實際應用中，一個好的快速排序(Quicksort)——下面段落會介紹——實作，在平均情況下通常比堆積排序更快。雖然快速排序的最差情況時間複雜度是 Θ(n2)\Theta(n^2)，不如堆積排序穩定，但它的平均效能和常數因子通常更優越。

堆積排序完整的實作邏輯和步驟

整個堆積排序演算法可以分解為三個核心程序，它們環環相扣，共同完成了排序任務。

首先，第一個核心程序的目的是維持最大堆積特性，這個程序是堆積排序的基石，它的任務是「修正」一個可能不符合最大堆積特性的小區域。用虛擬碼表示如下：

MAX-HEAPIFY(A, i)
  // 計算左右子節點的索引
1 l = LEFT(i)
2 r = RIGHT(i)

  // 找出目前節點、左子節點、右子節點三者中值最大者的索引
3 if l ≤ A.heap-size and A[l] > A[i]
4   largest = l
5 else largest = i
6 if r ≤ A.heap-size and A[r] > A[largest]
7   largest = r

  // 如果最大者不是目前節點，則交換並遞迴向下修正
8 if largest ≠ i
9   exchange A[i] with A[largest]
10  MAX-HEAPIFY(A, largest)

再來，第二個核心程序的目的是建立最大堆積，這個程序的任務是將一個完全無序的陣列，轉變成一個完整的最大堆積。用虛擬碼表示如下：

BUILD-MAX-HEAP(A)
1 A.heap-size = A.length
2 for i = floor(A.length / 2) down to 1
3   MAX-HEAPIFY(A, i)

最後一個是堆積排序的主程序，它利用已經建好的最大堆積來進行排序。用虛擬碼表示如下：

HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i = A.length down to 2
3   exchange A[1] with A[i]
4   A.heap-size = A.heap-size - 1
5   MAX-HEAPIFY(A, 1)

總結來說，堆積排序的邏輯是：先花費一些成本（BUILD-MAX-HEAP）將陣列「組織化」，然後利用這種組織好的結構——最大堆積，在每一次迭代中都能以很小的代價（MAX-HEAPIFY）找到當前剩餘元素中的最大值，並將它歸位。

使用 JavaScript 撰寫堆積排序演算法

/**
 * 主程序：HEAPSORT
 * @param {number[]} arr - 待排序的數字陣列。
 * @returns {number[]} - 排序後的陣列。
 */
function heapsort(arr) {
  // 獲取陣列的長度，這也是初始堆積的大小
  const n = arr.length;

  // ==========================================================
  // 步驟一: 建立最大堆積 (Build Max-Heap)
  // 這個過程會將無序的陣列重構成一個最大堆積，
  // 確保陣列中的最大元素位於索引 0 的位置。
  // ==========================================================
  buildMaxHeap(arr, n);

  // ==========================================================
  // 步驟二: 迭代排序
  // 重複地從堆積中取出最大元素，並將其放置到陣列的末端。
  // ==========================================================
  // 迴圈從最後一個元素開始，直到第二個元素 (索引 1)。
  for (let i = n - 1; i > 0; i--) {
    // 將堆積的根節點 (當前最大值，位於 arr[0])
    // 與當前堆積的最後一個元素 (位於 arr[i]) 進行交換。
    // 這樣，本次迭代找到的最大值就被放到了它排序後的最終位置。
    [arr[0], arr[i]] = [arr[i], arr[0]];

    // 交換後，新的根節點可能會違反最大堆積特性。
    // 因此，我們需要在縮小後的堆積上 (大小從 n 變為 i)，
    // 對根節點(索引 0)執行 maxHeapify，以恢復最大堆積特性。
    maxHeapify(arr, i, 0);
  }

  return arr;
}

/**
 * 核心程序二：建立最大堆積(BUILD-MAX-HEAP)
 * @param {number[]} arr - 要轉換的陣列。
 * @param {number} n - 堆積的大小 (陣列長度)。
 */
function buildMaxHeap(arr, n) {
  // **** 索引轉換關鍵 ****
  // 在 1-based 索引中，最後一個非葉節點是 floor(n/2)。
  // 在 0-based 索引中，它對應的索引是 Math.floor(n / 2) - 1。
  const lastNonLeafNode = Math.floor(n / 2) - 1;

  // 從最後一個非葉節點開始，由下而上、由右至左地對每個節點執行 maxHeapify。
  // 這樣可以保證當處理節點 i 時，它的子樹都已經是最大堆積。
  for (let i = lastNonLeafNode; i >= 0; i--) {
    maxHeapify(arr, n, i);
  }
}

/**
 * 核心程序一：維持最大堆積特性(MAX-HEAPIFY)
 * 假設節點 i 的子樹都已經是最大堆積，此函數確保以 i 為根的樹也是最大堆積。
 * @param {number[]} arr - 儲存堆積的陣列。
 * @param {number} n - 當前堆積的大小 (注意：在排序階段會變小)。
 * @param {number} i - 當前要進行 heapify 操作的節點索引 (根)。
 */
function maxHeapify(arr, n, i) {
  // 初始化 largest 為當前節點 i
  let largest = i;

  // **** 索引轉換關鍵 ****
  // 1-based: LEFT(i) = 2i, RIGHT(i) = 2i + 1
  // 0-based: LEFT(i) = 2i + 1, RIGHT(i) = 2i + 2
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  // 檢查左子節點是否存在 (left < n)，以及其值是否大於當前 largest 的值
  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }

  // 檢查右子節點是否存在 (right < n)，以及其值是否大於當前 largest 的值
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }

  // 如果 largest 的索引已經不是原本的 i，代表子節點中有比父節點更大的值
  if (largest !== i) {
    // 交換父節點和這個更大的子節點的值
    [arr[i], arr[largest]] = [arr[largest], arr[i]];

    // 由於交換了值，原本值較小的元素被換到了子節點的位置，
    // 這可能會破壞該子樹的最大堆積特性。
    // 因此，需要對被交換的子節點 (新的索引是 largest) 進行遞迴的 maxHeapify 操作。
    maxHeapify(arr, n, largest);
  }
}

以下也提供無註解的乾淨版本：

function heapsort(arr) {
  const n = arr.length;

  buildMaxHeap(arr, n);

  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    maxHeapify(arr, i, 0);
  }

  return arr;
}

function buildMaxHeap(arr, n) {
  const lastNonLeafNode = Math.floor(n / 2) - 1;
  for (let i = lastNonLeafNode; i >= 0; i--) {
    maxHeapify(arr, n, i);
  }
}

function maxHeapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    maxHeapify(arr, n, largest);
  }
}

堆積排序的效率分析

經過嚴謹的數學證明，堆積排序在最差情況、最好情況與平均情況下的執行時間均為 Θ(nlg⁡n)\Theta(n \lg n)。

這裡會用比較直觀的方式來進行說明，我們可以將堆積排序的成本想像成兩個階段：

  1. 初始整理成本(BUILD-MAX-HEAP)：這個階段的任務是將完全無序的陣列，整理成一個最大堆積。直覺上可能會認為這需要 O(nlg⁡n)O(n \lg n) 的時間，因為似乎要對 n 個元素都做類似「插入」的動作。但實際上，我們可以證明這個過程其實非常的高效，只需要 O(n)O(n) 的線性時間。這是因為堆積結構中，絕大多數的節點（約一半）都是葉節點，它們不需要任何調整。而越往上的節點，雖然調整成本越高，但數量卻越少。最終加總起來，總成本只與 n 成正比。

  2. 重複取出最大值的成本(HEAPSORT 主迴圈)：這個階段是演算法的核心。它會重複執行 n-1 次「取出最大值 -> 放到陣列末端 -> 維護堆積」的循環。每一次取出最大值——也就是根節點——後，都需要呼叫一次 MAX-HEAPIFY 來修正堆積結構，確保下一次還能找到次大值。這個修正的成本與堆積的高度成正比，而一個 n 個元素的堆積，其高度約為 lg⁡n\lg n。因此，可以看作是執行了約 n 次、每次成本為 lg⁡n\lg n 的操作，總成本自然就是 O(nlg⁡n)O(n \lg n)。

總成本：整個演算法的總時間 = 初始整理成本 + 重複取值成本 = O(n)+O(nlg⁡n)O(n) + O(n \lg n)。在漸進分析中，高階項會主導結果，因此最終的時間複雜度為 O(nlg⁡n)O(n \lg n)。

快速排序(Quicksort)

快速排序使用的策略思維和合併排序一樣，是一種分治法(divide-and-conquer) 演算法，它會選擇一個「樞軸(pivot)」元素，並將陣列分割成兩部分，使得一部分的元素都小於或等於樞軸，另一部分的元素都大於或等於樞軸，然後再對這兩部分遞迴地進行排序。

快速排序之所以會成為一種重要且被廣泛應用的排序演算法，是因為它在平均情況下的表現極為出色，並且具有一些其他演算法所沒有的實作優勢。包括：

但它還是有一些劣勢存在，包含：

快速排序完整的實作邏輯和步驟

如同上面有提過，快速排序和合併排序一樣是採用分治法策略的排序演算法，因此我們也可以用分治法的思維來思考實作步驟。

首先，分割(Divide) 步驟是快速排序最關鍵的部分，我們可以將此步驟包成一個子程序，並將此程序取名為PARTITION。PARTITION的實作邏輯用虛擬碼表示如下：

PARTITION(A, p, r)
1  x = A[r]
2  i = p - 1
3  for j = p to r - 1
4    if A[j] <= x
5      i = i + 1
6      exchange A[i] with A[j]
7  exchange A[i + 1] with A[r]
8  return i + 1

再來，征服(Conquer) 步驟就是快速排序演算法的主程序，用虛擬碼表示如下：

QUICKSORT(A, p, r)
1  if p < r
2    q = PARTITION(A, p, r)
3    QUICKSORT(A, p, q - 1)
4    QUICKSORT(A, q + 1, r)

這裡主要在做的事情是透過遞迴呼叫 QUICKSORT 演算法，分別對低側子陣列 A[p..q-1] 和高側子陣列 A[q+1..r] 進行排序。

最後的合併(Combine) 步驟非常簡單：什麼都不用做。因為當兩個子陣列被遞迴地排序完成後，由於樞軸 A[q] 已經在正確的位置，整個陣列 A[p..r] 自然也就完成了排序。

使用 JavaScript 撰寫快速排序演算法

/**
 * 一個使用者友善的包裝函式，用於啟動快速排序程序。
 * 它處理帶有正確索引的初始呼叫。
 * @param {Array<number>} arr 要排序的陣列。
 * @returns {Array<number>} 已排序的陣列（就地排序）。
 */
function quickSort(arr) {
  if (!Array.isArray(arr)) {
    throw new Error("Input must be an array.");
  }
  // 初始呼叫以從索引 0 到 length - 1 排序整個陣列。
  quickSortRecursive(arr, 0, arr.length - 1);
  return arr;
}

/**
 * 主程序
 * @param {Array<number>} arr 要排序的陣列。
 * @param {number} p 要排序的子陣列起始索引。
 * @param {number} r 要排序的子陣列結束索引。
 */
function quickSortRecursive(arr, p, r) {
  // 遞歸的基礎情況：如果子陣列有 1 個或 0 個元素，它已經排序好了。
  if (p < r) {
    // 分割陣列並取得樞紐的最終索引 'q'。
    // arr[q] 現在處於其正確的排序位置。
    const q = partition(arr, p, r);

    // 遞歸排序樞紐之前的元素（低端）。
    quickSortRecursive(arr, p, q - 1);

    // 遞歸排序樞紐之後的元素（高端）。
    quickSortRecursive(arr, q + 1, r);
  }
}

/**
 * 核心程序：PARTITION
 * @param {Array<number>} arr 包含子陣列的陣列。
 * @param {number} p 子陣列的起始索引。
 * @param {number} r 子陣列的結束索引（也是樞紐的初始索引）。
 * @returns {number} 分割後樞紐的新索引。
 */
function partition(arr, p, r) {
  // 選取最後一個元素作為樞紐。
  const pivot = arr[r];

  // 'i' 是「低端」（元素 <= 樞紐）中最後一個元素的索引。
  // 它從 p-1 開始，因為最初低端是空的。
  let i = p - 1;

  // 從起始位置（p）到樞紐前一個元素（r-1）遍歷子陣列。
  for (let j = p; j < r; j++) {
    // 如果目前元素小於或等於樞紐...
    if (arr[j] <= pivot) {
      // 它屬於低端。
      // 增加 'i' 為這個新元素在低端騰出空間。
      i++;
      // 將目前元素（arr[j]）與高端的第一個元素（arr[i]）交換。
      swap(arr, i, j);
    }
  }

  // 迴圈結束後，樞紐仍在 arr[r]。
  // 我們將它與 arr[i + 1] 的元素交換，該元素是大於樞紐的第一個元素。
  // 這將樞紐置於其最終排序位置。
  swap(arr, i + 1, r);

  // 回傳樞紐的新索引。
  return i + 1;
}

/**
 * 輔助函式：用於交換陣列中的兩個元素。
 * @param {Array<number>} arr 該陣列。
 * @param {number} i 第一個元素的索引。
 * @param {number} j 第二個元素的索引。
 */
function swap(arr, i, j) {
  // 交換過程中需要一個臨時變數來存放其中一個值。
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

以下也提供無註解的乾淨版本：

function quickSort(arr) {
  if (!Array.isArray(arr)) {
    throw new Error("Input must be an array.");
  }
  quickSortRecursive(arr, 0, arr.length - 1);
  return arr;
}

function quickSortRecursive(arr, p, r) {
  if (p < r) {
    const q = partition(arr, p, r);
    quickSortRecursive(arr, p, q - 1);
    quickSortRecursive(arr, q + 1, r);
  }
}

function partition(arr, p, r) {
  const pivot = arr[r];
  let i = p - 1;

  for (let j = p; j < r; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(arr, i, j);
    }
  }

  swap(arr, i + 1, r);
  return i + 1;
}

function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

快速排序的效率分析

經過嚴謹的數學證明，快速排序在最差情況下的執行時間為 Θ(n2)\Theta(n^2)；在最好情況下的執行時間為 Θ(nlg⁡n)\Theta(n \lg n)；在平均情況——或隨機化版本——下的執行時間為 Θ(nlg⁡n)\Theta(n \lg n)。

總結來說，快速排序的效率完全取決於 PARTITION 程序所做的分割是否平衡。這裡會用比較直觀的方式來進行說明：

引入「隨機化」版本的快速排序

相較於快速排序，隨機化版本的快速排序在分割陣列前，不總是選擇固定位置的元素——例如最後一個——作為基準點(pivot)，而是從當前的子陣列中「隨機」挑選一個元素作為基準點。

要理解隨機化版本的價值，我們必須先了解原始確定性快速排序的弱點。

原始快速排序的挑戰：最差情況

快速排序演算法的核心精神是分治法。它的效率高度依賴於每一次的「分割」(partitioning) 是否平衡。

一個會觸發這種最差情況的典型例子，就是對一個「已經排序好」的陣列執行快速排序。如果演算法總是選擇最後一個元素作為基準點，那麼每次分割都會是最差情況。

隨機化：打破特定輸入的魔咒

引入隨機化的主要動機，是為了避免演算法的效能被特定的輸入模式所左右。在原始版本中，只要有人知道了你的基準點選擇策略——例如：總是選最後一個元素——他就可以刻意構造一個會觸發最差效能的輸入資料，這被稱為「殺手級對手」(killer adversary)。

隨機化透過在分割前隨機選擇基準點，打破了輸入順序與執行效能之間的強烈關聯。這帶給了它一項優勢：避免最差情況的系統性發生，因為基準點是隨機選擇的，任何一種特定的輸入——無論是已排序、逆向排序或特殊排列——都不會穩定地觸發最差情況。雖然在理論上，隨機版本還是有可能運氣極差，連續選中最差的基準點，導致 Θ(n2)\Theta(n^2) 的時間，但這種情況發生的機率極小。在所有可能的隨機選擇下，它的「期望」或「平均」執行時間是高效的 O(nlg⁡n)O(n \lg n)。

由於隨機化版本快速排序優異的平均效能和原地排序(in-place)特性，它在實務上非常受歡迎，許多軟體庫都選擇它作為預設的排序演算法。

總結來說，隨機化快速排序是一種策略，它犧牲了對「最好情況輸入」的確定性，來換取在「任何輸入」下都能有非常高的機率獲得接近最好情況的效能。

隨機化版本快速排序完整的實作邏輯和步驟

相較於標準快速排序，隨機化版本的快速排序會在分割步驟進行關鍵修改，用虛擬碼表示如下：

RANDOMIZED-PARTITION(A, p, r)
1  i = RANDOM(p, r)
2  exchange A[r] with A[i]
3  return PARTITION(A, p, r)

最後是主程序的虛擬碼表示如下：

RANDOMIZED-QUICKSORT(A, p, r)
1  if p < r
2    q = RANDOMIZED-PARTITION(A, p, r)
3    RANDOMIZED-QUICKSORT(A, p, q - 1)
4    RANDOMIZED-QUICKSORT(A, q + 1, r)

這個流程確保了基準點的選擇是隨機的，從而使得分割的平衡性在平均情況下得到保證。

使用 JavaScript 撰寫隨機化版本快速排序演算法

/**
 * 主要的 RANDOMIZED-QUICKSORT 程序。
 * 就地排序子陣列 arr[p..r]。
 * @param {Array<number>} arr 要排序的陣列。
 * @param {number} p 要排序的子陣列的起始索引。
 * @param {number} r 要排序的子陣列的結束索引。
 */
function randomizedQuicksort(arr, p, r) {
    // 遞迴的基本情況：如果子陣列有 1 個或 0 個元素，它已經排序好了。
    if (p < r) {
        // 分割陣列並取得樞紐的最終索引 q。
        const q = randomizedPartition(arr, p, r);

        // 遞迴地排序兩個產生的子陣列。
        // 處理樞紐左側的子問題。
        randomizedQuicksort(arr, p, q - 1);
        // 處理樞紐右側的子問題。
        randomizedQuicksort(arr, q + 1, r);
    }
}

/**
 * RANDOMIZED-PARTITION 程序。
 * 它會隨機選擇一個樞紐，然後呼叫標準的分割程序。
 * @param {Array<number>} arr 該陣列。
 * @param {number} p 起始索引。
 * @param {number} r 結束索引。
 * @returns {number} 隨機選擇的樞紐的最終索引。
 */
function randomizedPartition(arr, p, r) {
    // 1. 在 p 到 r（包含）之間選擇一個隨機索引。
    const randomIndex = Math.floor(Math.random() * (r - p + 1)) + p;

    // 2. 將隨機選擇的元素與最後一個元素（arr[r]）交換。
    // 這會將我們的隨機樞紐放置在 partition() 函式預期的位置。
    swap(arr, randomIndex, r);

    // 3. 呼叫標準的分割程序。
    return partition(arr, p, r);
}

/**
 * 核心程序：PARTITION
 * 它會以 arr[r] 作為樞紐，對子陣列 arr[p..r] 進行分割。
 * @param {Array<number>} arr 要被分割的陣列。
 * @param {number} p 子陣列的起始索引。
 * @param {number} r 子陣列的結束索引（也是樞紐的初始索引）。
 * @returns {number} 樞紐元素的最終索引。
 */
function partition(arr, p, r) {
    // 樞紐元素選擇為子陣列的最後一個元素。
    const pivot = arr[r];
    // i 是「小於或等於樞紐」分割區中最後一個元素的索引。
    let i = p - 1;

    // 從 p 到 r-1 迭代陣列。
    for (let j = p; j < r; j++) {
        // 如果目前元素小於或等於樞紐
        if (arr[j] <= pivot) {
            // 遞增 i 並交換 arr[i] 與 arr[j]。
            // 這會將較小的元素 arr[j] 移動到較小元素的分割區中。
            i++;
            swap(arr, i, j);
        }
    }

    // 迴圈結束後，從 p 到 i 的所有元素都 <= 樞紐。
    // 樞紐（原本位於 arr[r]）應該放置在這個分割區之後。
    // 因此我們將它與 arr[i + 1] 交換。
    swap(arr, i + 1, r);
    // 傳回樞紐的新索引。
    return i + 1;
}

/**
 * 輔助函式：用於交換陣列中的兩個元素。
 * @param {Array<number>} arr 該陣列。
 * @param {number} i 第一個元素的索引。
 * @param {number} j 第二個元素的索引。
 */
function swap(arr, i, j) {
  // 使用陣列解構進行簡潔的交換
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

以下也提供無註解的乾淨版本：

function randomizedQuicksort(arr, p, r) {
    if (p < r) {
      const q = randomizedPartition(arr, p, r);
      randomizedQuicksort(arr, p, q - 1);
      randomizedQuicksort(arr, q + 1, r);
    }
}

function randomizedPartition(arr, p, r) {
  const randomIndex = Math.floor(Math.random() * (r - p + 1)) + p;
  swap(arr, randomIndex, r);
  return partition(arr, p, r);
}

function partition(arr, p, r) {
  const pivot = arr[r];
  let i = p - 1;

  for (let j = p; j < r; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(arr, i, j);
    }
  }

  swap(arr, i + 1, r);

  return i + 1;
}

function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

隨機化版本快速排序的效率分析

經過嚴謹的數學證明，隨機化快速排序在最差情況下的執行時間為 Θ(n2)\Theta(n^2)；在最好情況下的執行時間為 Θ(nlg⁡n)\Theta(n \lg n)；在平均——或期望——情況下的執行時間為 Θ(nlg⁡n)\Theta(n \lg n)。

快速排序的效率取決於分割的平衡程度。一個「好」的分割是兩邊大小差不多，而一個「壞」的分割是兩邊大小極度不均。

在隨機化版本中，由於基準點是隨機挑選的，我們期望在整個排序過程中，「好」的分割和「壞」的分割會隨機出現。

直覺上，我們可以思考一種情況：假設「好」的分割(例如：完美地分成兩半)和「壞」的分割(例如：分成 0 和 n-1)交替出現。

  1. 第一次是「壞」的分割，成本是 Θ(n)\Theta(n)，產生了大小為 00 和 n−1n-1 的子問題。

  2. 第二次對大小為 n−1n-1 的子問題進行了「好」的分割，成本是 Θ(n−1)\Theta(n-1)，產生了兩個大小約為 (n−1)/2(n-1)/2 的子問題。

這兩次分割的總成本是 Θ(n)+Θ(n−1)=Θ(n)\Theta(n) + \Theta(n-1) = \Theta(n)。而產生的結果（兩個大小約為 n/2n/2 的子問題）與一次完美的「好」分割非常相似。這意味著，一次「壞」的分割的負面影響可以被緊隨其後的一次「好」的分割所「吸收」。

因為在隨機過程中，好的分割和壞的分割會混合出現，整體效果會趨近於持續進行好的分割。因此，平均執行時間會非常接近最好情況的 Θ(nlg⁡n)\Theta(n \lg n)。

小結

以上內容就是各種常見的「比較排序」相關演算法介紹。

在本篇的最後，有一個非常值得我們思考的問題：對於任何只能透過「兩兩比較」來排序的演算法，它最快能有多快？有沒有一個無法超越的速度底線？

這個問題已經有被證明過比較排序存在一個無法逾越的理論障礙。不論你設計的演算法多麼巧妙，只要它遵循「兩兩比較」的規則，那麼在最壞情況下，它的時間複雜度絕對不可能優於 O(nlog⁡n)O(n \log n)。

這也解釋了為什麼像合併排序(Merge Sort) 和堆積排序(Heapsort) 這麼重要。它們的最壞情況下的時間複雜度都是 O(nlog⁡n)O(n \log n)，正好達到了我們證明的理論下限。因此，我們稱它們是漸進最佳(asymptotically optimal) 的比較排序演算法。換句話說，你無法發明出在根本上更快的比較排序法了。

參考資料

Introduction to Algorithms, fourth edition

附錄

本文為系列文章，目前寫了五篇:

  1. 認識演算法：啟程
  2. 認識演算法：常用資料結構
  3. 認識演算法：各種比較排序
  4. 認識演算法：各種線性時間排序
  5. 認識演算法：選擇問題