排序演算法完整指南

在程式設計的世界裡，排序算法扮演著舉足輕重的角色。讓我們一起深入探討四種經典的排序方法：快速排序、選擇排序、氣泡排序和插入排序。

快速排序法

快速排序法是一種常用的排序算法，由英國計算機科學家東尼·霍爾(Tony Hoare)於1960年提出。它的主要特點是:

效率高：在大多數情況下，它比其他排序算法更快。
原地排序：不需要額外的存儲空間。
分治法：採用「分而治之」的策略來解決問題。

快速排序法的工作原理

想像你有一堆數字卡片需要按照從小到大的順序排列。快速排序法的基本思路是:

**選擇基準值(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)（因為遞迴調用堆疊的深度）。

實現方式

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

基準值選擇

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

分區策略

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

代碼複雜度

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

效率

方法1：由於創建新陣列，在大規模數據時可能較慢。
方法2：不創建新陣列，通常在大規模數據時更高效。

快速排序的效能考量

快速排序法的平均時間複雜度是 O(n log n)，這使它在大多數情況下比其他排序算法更快。然而，在最壞的情況下(例如，當數列已經排序時)，它的時間複雜度可能退化到 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]));

小結

選擇排序法雖然效率不是最佳，但它的實現簡單且易於理解，特別適合小規模數據的排序。它的一個重要特點是交換次數最少，這在某些特定場景下可能是有利的。

氣泡排序法

氣泡排序法（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 = 0;
        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 !== 0);
    
    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 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(1)
氣泡排序	O(1)
插入排序	O(1)

特點比較

快速排序

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

選擇排序

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

氣泡排序

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

插入排序

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

如何選擇合適的排序算法

當數據規模小（n < 50）時：
- 選擇排序或氣泡排序都是可以接受的選擇
- 程式碼簡單，易於實現和維護
當數據規模大時：
- 快速排序是最好的選擇
- 效能優勢明顯
當數據接近排序好時：
- 優化後的氣泡排序效果好
- 時間複雜度接近 O(n)
當空間有限時：
- 選擇排序或氣泡排序較好
- 只需要 O(1) 的額外空間
當資料持續輸入時：
- 插入排序是最佳選擇
- 可以即時維護已排序的序列
當需要穩定排序時：
- 插入排序和氣泡排序都是好選擇
- 保持相等元素的相對順序不變

總結

透過本文，我們深入了解了四種經典的排序算法：

快速排序：效能最優，但實現複雜，適合大規模資料排序
選擇排序：簡單穩定，交換次數少，適合小規模資料
氣泡排序：最易理解，在接近排序的資料上表現良好
插入排序：簡單直觀，適合處理接近排序或持續輸入的資料

選擇合適的排序算法時，需要綜合考慮以下因素：

資料規模大小
可用的記憶體空間
資料的初始排序狀態
是否需要穩定排序
是否有資料持續輸入
實現的複雜度要求

每種排序算法都有其適用場景，理解它們的特點和原理，能幫助我們在實際應用中做出最佳選擇。對於初學者來說，建議按照氣泡排序、插入排序、選擇排序、快速排序的順序學習，這樣可以循序漸進地理解排序算法的概念和優化思路。

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

排序演算法完整指南

快速排序法

快速排序法的工作原理

運作示例

JavaScript 實現

實現方法比較

空間複雜度

實現方式

基準值選擇

分區策略

代碼複雜度

效率

快速排序的效能考量

小結

選擇排序法

選擇排序法的工作原理

運作示例

JavaScript 實現

小結

氣泡排序法

氣泡排序法的工作原理

運作示例

JavaScript 實現

小結

插入排序法

插入排序法的工作原理

運作示例

JavaScript 實現

插入排序的效能分析

時間複雜度

空間複雜度

優化方式

小結

四種排序算法的綜合比較

時間複雜度比較

空間複雜度比較

特點比較

快速排序

選擇排序

氣泡排序

插入排序

如何選擇合適的排序算法

總結