C# 快速排序演算法實作與解析

演算法原理

快速排序是冒泡排序的改進：分治策略。一趟分區將陣列分為左右兩部分，左側鍵值 ≤ 樞軸，右側 ≥ 樞軸，遞迴排序兩部分。平均 O(n log n)，最差 O(n²)（已有序陣列），空間 O(log n) 堆疊。

C# 實作（Hoare 分區變體）

private void Swap(ref int a, ref int b) { int t = a; a = b; b = t; }

public void QuickSort(int[] arr, int low, int high)
{
    if (high <= low) return;
    if (high == low + 1) { if (arr[low] > arr[high]) Swap(ref arr[low], ref arr[high]); return; }

    int mid = (low + high) >> 1;
    int pivot = arr[mid];
    Swap(ref arr[low], ref arr[mid]); // 樞軸移至低端

    int l = low + 1, r = high;
    do
    {
        while (l <= r && arr[l] < pivot) l++;
        while (arr[r] >= pivot) r--;
        if (l < r) Swap(ref arr[l], ref arr[r]);
    } while (l < r);

    arr[low] = arr[r];
    arr[r] = pivot;

    if (low + 1 < r) QuickSort(arr, low, r - 1);
    if (r + 1 < high) QuickSort(arr, r + 1, high);
}

關鍵細節解析

• 樞軸選取：中位元素（mid），避免已序列最差情況；可改用「三數取中」或隨機化。
• 分區邏輯：l 找 ≥ pivot，r 找 < pivot，交換錯位元素；最終 r 為模軸正確位置。
• 邊界處理：小區間（≤2）直接比較交換，避免過度遞迴。
• 原地排序：空間效率高，非穩定排序。

優化與變體

1. 三向切分：<pivot | =pivot | >pivot，大量重複鍵值時極快（荷蘭國旗問題）。
2. 插入排序切換：小區間（<16）改用插入排序，減少遞迴開銷。
3. 尾遞迴消除：對較大分區遞迴，較小分區迴圈，限制堆疊深度 O(log n)。
4. 平行化：.NET Parallel.Invoke 並行排序左右分區（大陣列有效）。

內建替代方案

生產代碼優先使用 Array.Sort/List.Sort（Introspective Sort：快排+堆排+插排混合），穩定、高效、經過極致優化。