C# 實現四大經典排序演算法：泡沫、快速、選擇、插入排序完整代碼與解析

前言

排序演算法是程式設計的基礎內功。雖然實務多用 List.Sort() 或 LINQ OrderBy，但理解經典演算法原理有助於面試、效能調優與解決特定約束問題。本文提供 C# 實作與關鍵點解析。

1. 泡沫排序

原理：相鄰元素兩兩比較，大的往後「冒泡」。每趟確定一個最大值位置。引入 flag 優化：若某趟無交換則提前結束。

public void Sort(int[] numArr)
{
    for (int i = 1; i < numArr.Length; i++)
    {
        bool flag = false;
        for (int j = numArr.Length - 1; j >= i; j--)
        {
            if (numArr[j] < numArr[j - 1])
            {
                Swap(numArr, j, j - 1);
                flag = true;
            }
        }
        if (!flag) return;
    }
}

複雜度：O(n²)；穩定；原地排序。

2. 快速排序

原理：分治法。選基準值，將陣列分為「小於基準」與「大於基準」兩子區間，遞歸排序。此處採雙指針單向掃描版本。

public static void Sort(int[] numArr) => Sort(numArr, 0, numArr.Length - 1);

private static void Sort(int[] numArr, int left, int right)
{
    if (left < right)
    {
        int pivot = numArr[(left + right) / 2];
        int i = left - 1, j = right + 1;
        while (true)
        {
            while (numArr[++i] < pivot) ;
            while (numArr[--j] > pivot) ;
            if (i >= j) break;
            Swap(numArr, i, j);
        }
        Sort(numArr, left, i - 1);
        Sort(numArr, j + 1, right);
    }
}

複雜度：平均 O(n log n)，最壞 O(n²)；不穩定；原地排序（遞歸堆疊 O(log n)）。

補充：文中另附 Hoare 分區經典寫法（Partition 回傳樞軸最終位置），邏輯等價但細節不同。

3. 選擇排序

原理：每趟從未排序區選出最小值，換到有序區末尾。

public static void Sort(int[] numArray)
{
    for (int i = 0; i < numArray.Length - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < numArray.Length; j++)
            if (numArray[j] < numArray[min]) min = j;
        Swap(numArray, i, min);
    }
}

複雜度：O(n²)；不穩定；原地排序；交換次數最少 (O(n))。

4. 插入排序

原理：維護有序前綴，將下一元素插入適當位置（從後向前挪移）。

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

複雜度：O(n²)；穩定；原地排序；近似有序資料極快 (O(n))。

效能與選用指南

結語

「演算法是程式的靈魂」。雖然日常開發少見手寫排序，但掌握其權衡能讓你在關鍵時刻做出正確技術選型。建議動手實作、追蹤變數變化，體會「巧妙解決問題的純粹快樂」。