書籍資訊

  • 書名：《圖解演算法：使用 C#》
  • 類型：演算法與排序觀念整理

這篇在講什麼

這一篇主要是在整理幾種經典排序法，包含：

  • 它們怎麼排
  • 時間複雜度大概落在哪裡
  • 哪些方法穩定
  • 哪些情況適合使用

排序前先看哪些指標

比較排序法時，我會先看四件事：

  • 最好、平均、最差時間複雜度
  • 空間複雜度
  • 是否穩定
  • 是否適合部分排序完成的資料

這四個維度通常比背流程更重要，因為它會直接影響你在實務上怎麼選。

基礎排序：氣泡、選擇、插入

氣泡排序 Bubble Sort

做法很直覺：

  • 從前往後比較相鄰元素
  • 如果順序錯了就交換
  • 每一輪都把較大的值往後推

特點是：

  • 好理解
  • 最差與平均通常是 O(n^2)
  • 幾乎只適合教學或很小的資料

選擇排序 Selection Sort

每一輪從未排序區間裡找最小值，放到前面。

特點是：

  • 實作簡單
  • 比較次數固定偏多
  • 時間複雜度通常也是 O(n^2)

插入排序 Insertion Sort

把資料想成「左邊已排序，右邊未排序」，每次拿一個新元素插進左邊的正確位置。

它的價值在於：

  • 資料量小時很實用
  • 幾乎已排序的情況下表現不錯
  • 穩定排序
public static void InsertionSort(int[] nums)
{
    for (int i = 1; i < nums.Length; i++)
    {
        int current = nums[i];
        int j = i - 1;

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

        nums[j + 1] = current;
    }
}

中階思路：Shell Sort

Shell Sort 可以看成是插入排序的加速版本。

核心想法是：

  • 先用較大的 gap 分組做局部排序
  • 再逐步縮小 gap
  • 最後 gap 變成 1，完成整體排序

它比單純插入排序更快，但效能會受到 gap 設計影響，所以常見於教學或特定場景，不是最通用的主力解法。

常見主力：快速排序與合併排序

快速排序 Quick Sort

快速排序的思路是分治：

  • 先選一個 pivot
  • 把小於 pivot 的放左邊，大於 pivot 的放右邊
  • 再遞迴處理左右兩邊

它常見的優點是：

  • 平均表現很好
  • 實務上常常很快
  • 平均時間複雜度通常是 O(n log n)

但也要記得：

  • 如果 pivot 選不好，最差可能退化到 O(n^2)
  • 標準版本通常不是穩定排序

合併排序 Merge Sort

合併排序也是分治：

  • 先把陣列切成兩半
  • 各自排好
  • 最後把兩個有序區間合併

它的特點是：

  • 時間複雜度穩定維持在 O(n log n)
  • 穩定排序
  • 需要額外空間做合併
public static int[] MergeSort(int[] nums)
{
    if (nums.Length <= 1)
    {
        return nums;
    }

    int mid = nums.Length / 2;
    int[] left = MergeSort(nums[..mid]);
    int[] right = MergeSort(nums[mid..]);

    return Merge(left, right);
}

private static int[] Merge(int[] left, int[] right)
{
    int[] result = new int[left.Length + right.Length];
    int i = 0, j = 0, k = 0;

    while (i < left.Length && j < right.Length)
    {
        if (left[i] <= right[j])
        {
            result[k++] = left[i++];
        }
        else
        {
            result[k++] = right[j++];
        }
    }

    while (i < left.Length)
    {
        result[k++] = left[i++];
    }

    while (j < right.Length)
    {
        result[k++] = right[j++];
    }

    return result;
}

非比較排序：基數排序

基數排序不是透過元素彼此比較大小，而是依照位數一輪一輪分配。

它適合：

  • 資料範圍可控
  • 位數有限
  • 想避免大量比較

但前提很明確：

  • 你得知道資料格式
  • 額外空間成本通常比較高

用樹的觀念排序：堆積排序

Heap Sort 先把資料整理成 Heap，再反覆取出最大值或最小值完成排序。

它的特點是：

  • 時間複雜度穩定在 O(n log n)
  • 不需要像 Merge Sort 那樣大量額外空間
  • 通常不是穩定排序

我自己的整理

如果只用一句話區分這些排序法，我會這樣記：

  • O(n^2) 基礎排序：好理解，但通常只適合小資料
  • Quick Sort：平均很快，實務常用
  • Merge Sort：穩定、好分析，但要多空間
  • Heap Sort：時間穩定，空間友善
  • Radix Sort：不走比較邏輯，適合特定資料型態

先記住的重點

  • 排序法不只比快慢，還要看穩定性與空間成本
  • 幾乎已排序的資料，插入排序可能比想像中有競爭力
  • Quick Sort 平均快，但最差情況不能忘
  • Merge Sort 的優勢是穩定且時間表現穩
  • 非比較排序不是萬能，它依賴資料分布與格式