C# 排序演算法實作：快速排序

快速排序由 C.A.R. Hoare 於 1962 年提出，採用分治法策略，平均時間複雜度 O(n log n)，是實務中最常用的高效排序演算法之一。本文詳解其核心邏輯、分區策略與 C# 實作細節。

核心思想：分治法

1. 分解：選取基準值，將陣列分為「小於基準」與「大於基準」兩個子區間，基準值歸位。
2. 求解：遞迴對左右子區間進行快速排序。
3. 合併：原地排序無需額外合併步驟。

分區演算法 (Hoare 分區法)

本範例採用雙指針向中間掃描：

• 左指針 i 從左向右找第一個 ≥ 基準值的元素。
• 右指針 j 從右向左找第一個 ≤ 基準值的元素。
• 若 i < j 交換兩元素，繼續掃描；否則分區完成，返回 j 作為分界點。

C# 實作程式碼

public static class QuickSort
{
    public static void Sort(int[] arr) => Sort(arr, 0, arr.Length - 1);

    private static void Sort(int[] arr, int left, int right)
    {
        if (left < right)
        {
            int pivot = arr[(left + right) / 2]; // 取中間元素為基準
            int i = left - 1, j = right + 1;
            while (true)
            {
                while (arr[++i] < pivot) ;
                while (arr[--j] > pivot) ;
                if (i >= j) break;
                Swap(arr, i, j);
            }
            Sort(arr, left, i - 1);
            Sort(arr, j + 1, right);
        }
    }

    private static void Swap(int[] arr, int i, int j)
    {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

// 測試
static void Main()
{
    int[] data = { 20, 41, 27, 14, 16, 1, 8, 55, 9, 35, 22, 14 };
    QuickSort.Sort(data);
    Console.WriteLine("快速排序結果：" + string.Join(", ", data));
}

複雜度與特性

優化策略 (生產級實作常用)

1. 三數取中法：選取左、中、右三者中位數作為基準，避免最差情況。
2. 隨機化基準：隨機選取基準，期望時間複雜度 O(n log n)。
3. 小區間改用插入排序：當區間長度 < 16 時切換至插入排序，減少遞迴開銷。
4. 尾遞迴優化 / 迴圈實作：手動模擬堆疊避免堆疊溢位。
5. 三向切分：處理大量重複鍵值時將陣列分為 <、=、> 三段 (Dijkstra 荷蘭國旗問題)。

.NET 內建排序

Array.Sort / List<T>.Sort 採用 Introspective Sort (Introsort)：快速排序 + 堆積排序 (深度過深時切換) + 插入排序 (小區間)，兼具平均效能與最差情況保證。實務開發請直接使用內建方法。