排序演算法完整指南

四種排序演算法的核心差異就是複雜度與穩定性的取捨，這也是面試最常考的切入點。以下逐一拆解快速排序、選擇排序、氣泡排序、插入排序的工作原理與 JavaScript 實作。

快速排序法

快速排序法由英國計算機科學家東尼·霍爾（Tony Hoare）於 1960 年提出，主要特點：

效率高：平均情況下比其他 O(n²) 演算法快得多。
原地排序：in-place 版本不需要額外的儲存空間（遞迴堆疊除外）。
分治法：採用「分而治之」的策略，將問題拆解為更小的子問題。

快速排序法的工作原理

快速排序法的基本思路：

**選擇基準值(Pivot)**：從這堆卡片中選一張作為基準卡。
**分區(Partition)**：將其他卡片與基準卡比較，分成三組:
- 比基準值小的數
- 等於基準值的數
- 比基準值大的數
**遞迴(Recursion)**：對「小於」和「大於」的兩組重複步驟1和2，直到每組只剩一張卡片或沒有卡片為止。
合併：將所有排序好的小組按順序連接起來，得到最終排序結果。

運作示例

假設我們有以下數列需要排序: [64, 34, 25, 12, 22, 11, 90]

選擇基準值(我們選擇中間的數 25):
1
2
[64, 34, 25, 12, 22, 11, 90]
^

分區:

1
2
3

小於25: [12, 22, 11]
等於25: [25]
大於25: [64, 34, 90]

對 [12, 22, 11] 和 [64, 34, 90] 重複這個過程:

對 [12, 22, 11] 排序:
1
2
3
小於12: [11]
等於12: [12]
大於12: [22]
對 [64, 34, 90] 排序:
1
2
3
小於64: [34]
等於64: [64]
大於64: [90]
最後，將所有結果合併:
1
[11, 12, 22, 25, 34, 64, 90]

JavaScript 實作

// 方法1：使用額外空間的快速排序
function quickSort1(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter(x => x < pivot);
  const middle = arr.filter(x => x === pivot);
  const right = arr.filter(x => x > pivot);

  return [...quickSort1(left), ...middle, ...quickSort1(right)];
}

// 方法2：原地（in-place）快速排序
function quickSort2(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right);
    quickSort2(arr, left, pivotIndex - 1);
    quickSort2(arr, pivotIndex + 1, right);
  }
  return arr;
}

function pivot(arr, start = 0, end = arr.length - 1) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

  let pivot = arr[start];
  let swapIdx = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
    }
  }
  swap(arr, start, swapIdx);
  return swapIdx;
}

// 測試
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log("原始陣列:", arr);
console.log("方法1排序後:", quickSort1([...arr]));
console.log("方法2排序後:", quickSort2([...arr]));

實作方法比較

空間複雜度

方法1：使用額外的陣列來儲存左、中、右三部分，空間複雜度為O(n)。
方法2：直接在原陣列上進行操作，平均空間複雜度為 O(log n)（遞迴呼叫堆疊深度）；但方法2 以第一個元素為 pivot，對已排序或完全反序的資料遞迴深度退化為 O(n)，最壞空間複雜度亦為 O(n)。

實作方式

方法1：使用過濾器（filter）建立新的子陣列。
方法2：使用交換（swap）操作在原陣列中重新排列元素。

基準值選擇

方法1：選擇中間元素作為基準。
方法2：選擇第一個元素作為基準。

分區策略

方法1：透過過濾直接生成左、中、右三個部分。
方法2：透過一次遍歷和交換操作，將小於基準的元素移到左邊。

程式碼複雜度

方法1：程式碼較簡潔，易於理解。
方法2：程式碼稍複雜，但更接近傳統的快速排序實作。

效率

方法1：由於建立新陣列，在大規模資料時可能較慢。
方法2：不建立新陣列，通常在大規模資料時更有效率。

快速排序的效能考量

快速排序法的平均時間複雜度是 O(n log n)，在大多數情況下比其他排序演算法更快。然而在最壞情況下（例如資料已排序且每次都選到最大或最小 pivot），時間複雜度退化到 O(n²)。

效率很大程度上取決於基準值的選擇。常見的選擇方法有:

選擇第一個元素
選擇最後一個元素
選擇中間的元素
隨機選擇

其中，隨機選擇通常能提供較好的平均性能。

小結

快速排序的關鍵在於基準值的選擇：隨機 pivot 能有效迴避 O(n²) 的最壞情況，這也是各語言標準函式庫實作時普遍採用的做法。

選擇排序法

選擇排序法（Selection Sort）是一種簡單直觀的排序演算法，每輪從未排序部分找出最小值並放到正確位置。

選擇排序法的工作原理

選擇排序的基本步驟是：

找出數列中最小的數字
將它與第一個位置的數字交換
在剩下的數字中找出最小的數字
將它與第二個位置的數字交換
重複這個過程，直到所有數字都排序完成

運作示例

假設我們要對以下數列進行排序：[64, 34, 25, 12, 22, 11, 90]

第一輪：找到最小值 11 並與第一個位置交換

1 2	[64, 34, 25, 12, 22, 11, 90] -> [11, 34, 25, 12, 22, 64, 90] ^ ^

第二輪：在剩餘數字中找到最小值 12 並與第二個位置交換

1 2	[11, 34, 25, 12, 22, 64, 90] -> [11, 12, 25, 34, 22, 64, 90] ^ ^

持續這個過程直到排序完成。

JavaScript 實作

function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let minIndex = i;
        
        // 在未排序部分找最小值
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // 如果找到更小的值，進行交換
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    return arr;
}

// 測試
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log("排序後:", selectionSort([...arr]));

小結

選擇排序最大的特點是交換次數固定為 O(n)，若寫入成本極高（例如 EEPROM），這個特性就有實際價值。代價是比較次數固定 O(n²)，無論資料初始狀態如何都不會更快。需要注意，選擇排序是不穩定排序——相等元素的相對順序可能改變。

氣泡排序法

氣泡排序法（Bubble Sort）是最簡單的排序演算法之一。每輪比較後，當前最大的元素會像氣泡一樣逐步「浮」到數列尾端。

氣泡排序法的工作原理

氣泡排序的基本步驟是：

比較相鄰的兩個數字
如果第一個比第二個大，就交換它們的位置
對每一對相鄰元素進行同樣的操作
每一輪比較後，最大的數字會"浮"到最後的位置
重複這個過程，直到沒有需要交換的元素

運作示例

假設要排序：[64, 34, 25, 12, 22, 11, 90]

第一輪比較：

[64, 34, 25, 12, 22, 11, 90]
 ^  ^
[34, 64, 25, 12, 22, 11, 90]
    ^  ^
[34, 25, 64, 12, 22, 11, 90]
       ^  ^

...以此類推

JavaScript 實作

function bubbleSort(arr) {
    let swapped;
    do {
        swapped = false;
        for (let i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                swapped = true;
            }
        }
    } while (swapped);
    
    return arr;
}

// 優化版本：記錄最後一次交換的位置
function bubbleSortOptimized(arr) {
    let lastSwap;
    let len = arr.length - 1;
    
    do {
        lastSwap = -1;
        for (let i = 0; i < len; i++) {
            if (arr[i] > arr[i + 1]) {
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                lastSwap = i;
            }
        }
        len = lastSwap;
    } while (lastSwap !== -1);
    
    return arr;
}

// 測試
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log("基本氣泡排序:", bubbleSort([...arr]));
console.log("優化氣泡排序:", bubbleSortOptimized([...arr]));

小結

氣泡排序最大的優點是偵測「已排序」的能力：若某一輪完全沒有交換，就可以提前結束。優化版進一步縮短每輪掃描範圍，實際比較次數在接近排序的資料上會大幅減少。

插入排序法

插入排序法（Insertion Sort）的概念源自於人們整理撲克牌的方式。想像你手上的撲克牌：一手拿著已經排序好的牌，另一手拿著待排序的牌，每次將一張新牌插入到已排序的牌堆中適當的位置。

插入排序法的工作原理

將第一個元素視為已排序的子陣列
取出下一個元素，在已排序的子陣列中從後向前掃描
如果掃描到的元素大於新元素，則將該元素向後移動一個位置
重複步驟3，直到找到合適的插入位置
將新元素插入到該位置
重複步驟2-5，直到所有元素都完成排序

運作示例

假設我們要對以下數列進行排序：[64, 34, 25, 12, 22, 11, 90]

初始狀態：

1 2	已排序 \| 未排序 [64] \| [34, 25, 12, 22, 11, 90]

處理 34：
1
[34, 64] | [25, 12, 22, 11, 90]
處理 25：
1
[25, 34, 64] | [12, 22, 11, 90]
依此類推...

JavaScript 實作

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let current = arr[i];
        let j = i - 1;
        
        // 將較大的元素向後移動
        while (j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        // 插入當前元素
        arr[j + 1] = current;
    }
    
    return arr;
}

// 優化版本：使用二分搜尋找插入位置
function insertionSortWithBinarySearch(arr) {
    for (let i = 1; i < arr.length; i++) {
        let current = arr[i];
        
        // 使用二分搜尋找到插入位置
        let left = 0;
        let right = i - 1;
        
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (arr[mid] > current) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        // 移動元素並插入
        for (let j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = current;
    }
    
    return arr;
}

// 測試
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log("基本插入排序:", insertionSort([...arr]));
console.log("二分搜尋插入排序:", insertionSortWithBinarySearch([...arr]));

插入排序的效能分析

時間複雜度

最佳情況：O(n)，當資料已經排序好時
平均情況：O(n²)
最壞情況：O(n²)，當資料完全反序時

空間複雜度

O(1)，只需要一個額外變數來儲存當前處理的元素

優化方式

二分搜尋最佳插入位置：
- 將線性搜尋改為二分搜尋，比較次數從 O(n) 降到 O(log n)
- 但移動元素的次數不變，整體時間複雜度仍是 O(n²)，因為元素位移才是主要開銷
跳躍式插入：
- 先比較間隔較大的元素
- 逐步縮小間隔
- 類似希爾排序的概念

小結

插入排序在三個情境特別有用：小規模資料（快取局部性佳、實際速度往往勝過理論複雜度更低的演算法）、幾乎已排序的資料（最佳情況 O(n)）、以及資料持續輸入的串流場景（每筆新資料插入已排序序列即可）。

四種排序演算法的綜合比較

時間複雜度與穩定性比較

演算法	最佳情況	平均情況	最壞情況	穩定性
快速排序	O(n log n)	O(n log n)	O(n²)	不穩定
選擇排序	O(n²)	O(n²)	O(n²)	不穩定
氣泡排序	O(n)	O(n²)	O(n²)	穩定
插入排序	O(n)	O(n²)	O(n²)	穩定

空間複雜度比較

演算法	空間複雜度
快速排序	O(log n) 平均；O(n) 最壞
選擇排序	O(1)
氣泡排序	O(1)
插入排序	O(1)

特點比較

快速排序

優點：
- 平均效能最佳
- 實際應用中最常用
- 適合大規模資料
缺點：
- 實作較複雜
- 在最壞情況下效能不佳
- 遞迴實作可能導致堆疊溢出

選擇排序

優點：
- 實作簡單
- 交換次數最少
- 適合小規模資料
缺點：
- 效能固定為 O(n²)
- 不適合大規模資料

氣泡排序

優點：
- 最容易理解和實作
- 最適合接近排序好的資料
缺點：
- 效率較低
- 交換次數多
- 不適合大規模資料

插入排序

優點：
- 實作簡單直觀
- 對於近乎排序的資料非常高效
- 可以處理資料串流（即時輸入的資料）
- 穩定排序
缺點：
- 平均效能為 O(n²)
- 不適合大規模資料
- 對完全反序的資料效能最差

如何選擇合適的排序演算法

資料規模小（n < 50）：插入排序通常最佳——快取局部性好、常數係數小、穩定；若寫入成本極高則選擇排序（交換次數固定最少）。
資料規模大：快速排序，搭配隨機 pivot 可有效迴避最壞情況。
資料接近排序好：優化版氣泡排序或插入排序，時間複雜度接近 O(n)。
空間有限：選擇排序、氣泡排序或插入排序，空間複雜度均 O(1)。
資料持續輸入（串流）：插入排序，每筆新資料直接插入已排序序列。
需要穩定排序：插入排序或氣泡排序。

總結

演算法	穩定	交換次數	適合場景
快速排序	否	O(n log n) 均攤	大規模通用
選擇排序	否	O(n) 固定	寫入成本高
氣泡排序	是	O(n²)	教學、接近排序的小資料
插入排序	是	O(n²)	小規模、串流、接近排序

初學者建議按氣泡 → 插入 → 選擇 → 快速的順序學習，難度逐步遞增，每一步都有前一步的概念做基礎。

經典排序演算法指南：快速、選擇、氣泡與插入排序

排序演算法完整指南

快速排序法

快速排序法的工作原理

運作示例

JavaScript 實作

實作方法比較

空間複雜度

實作方式

基準值選擇

分區策略

程式碼複雜度

效率

快速排序的效能考量

小結

選擇排序法

選擇排序法的工作原理

運作示例

JavaScript 實作

小結

氣泡排序法

氣泡排序法的工作原理

運作示例

JavaScript 實作

小結

插入排序法

插入排序法的工作原理

運作示例

JavaScript 實作

插入排序的效能分析

時間複雜度

空間複雜度

優化方式

小結

四種排序演算法的綜合比較

時間複雜度與穩定性比較

空間複雜度比較

特點比較

快速排序

選擇排序

氣泡排序

插入排序

如何選擇合適的排序演算法

總結