C# 四大經典排序演算法實作：氣泡、選擇、插入、希爾排序完整教學

排序演算法是演算法入門的核心課題。本文以 C# 實作四種經典**比較型排序**：氣泡排序、選擇排序、插入排序、希爾排序，附上完整程式碼、運作原理圖解、時間/空間複雜度分析與實務應用場景。

複雜度總覽

1. 氣泡排序 - 相鄰交換，大值浮升

核心邏輯： 重複掃描陣列，比較相鄰元素，順序錯誤則交換。每輪將最大值「氣泡」到末端。優化：若某輪無交換，提前結束。

public static void BubbleSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]); // C# 7+ Tuple Swap
                swapped = true;
            }
        }
        if (!swapped) break; // 已有序，提前結束
    }
}

2. 選擇排序 - 選出最小，換到前端

核心邏輯： 將陣列分為「已排序區」與「未排序區」。每輪從未排序區找出最小值，與未排序區首位交換。交換次數固定 O(n)，適合寫入成本高的儲存體。

public static void SelectionSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[minIdx]) minIdx = j;
        
        if (minIdx != i)
            (arr[i], arr[minIdx]) = (arr[minIdx], arr[i]);
    }
}

3. 插入排序 - 像整理撲克牌

核心邏輯： 維護前段已排序，將下一張牌插入正確位置。最佳情況 (已排序) 僅 O(n) 比較、零移動。**實務上小陣列 (n < 50) 最快**，常作為快速排序/合併排序的基底案例。

public static void InsertionSort(int[] arr)
{
    for (int i = 1; i < arr.Length; i++)
    {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

4. 希爾排序 - 分組插入，縮小間距

核心邏輯： 插入排序的改良版。先按間距 (gap) 分組進行插入排序，逐步縮小 gap 至 1。經典間距序列：1, 4, 13, 40, 121... (h = 3h + 1) (Knuth 序列)，或 n/2, n/4, ..., 1 (Shell 原始)。

public static void ShellSort(int[] arr)
{
    int n = arr.Length;
    // Knuth 間距序列: 1, 4, 13, 40, ...
    int h = 1;
    while (h <= n / 3) h = h * 3 + 1; // 找到最大 gap < n/3

    while (h > 0)
    {
        // 對每個分組進行插入排序
        for (int i = h; i < n; i++)
        {
            int key = arr[i];
            int j = i;
            while (j >= h && arr[j - h] > key)
            {
                arr[j] = arr[j - h];
                j -= h;
            }
            arr[j] = key;
        }
        h /= 3; // 縮小間距
    }
}

效能實測 (參考：10 萬筆隨機整數)

// 環境: .NET 8, Release, i7-12700K
// 陣列長度: 100,000
BubbleSort:    ~12,000 ms  (極慢，僅供教學)
SelectionSort: ~ 1,800 ms
InsertionSort: ~ 1,500 ms  (隨機資料較慢)
ShellSort:     ~    15 ms  **快 100 倍!**
Array.Sort:    ~     8 ms  (Introsort: Quick + Heap + Insertion)

實務選型指南

C# 現代寫法小技巧

• Tuple 交換： (a, b) = (b, a); (C# 7+)，無需 temp 變數。
• 泛型化： 改用 T[] + IComparer<T> 即可支援任意類型。
• Span<T>： 避免陣列複製，支援 stackalloc 陣列排序。

結語

四大經典排序中，**希爾排序是唯一具備實務效能** 的 O(n²) 級演算法改良版。但實際開發中，**永遠優先使用 Array.Sort / LINQ**，除非你在寫嵌入式系統、教學示範、或面試白板題。理解它們的運作原理、優缺點與適用場景，才是演算法素養的核心價值。