C# 快速排序演算法完整實作：分治策略與原地分區深度解析

演算法核心思想

快速排序採用分治法，平均時間複雜度 O(n log n)，空間複雜度 O(log n)（遞迴堆疊）。

三步驟流程

1. 分解：選擇基準值，將陣列分為「≤基準」與「≥基準」兩個子陣列
2. 解決：遞迴排序兩個子陣列
3. 合併：原地排序無需額外合併步驟

完整程式碼實作

public class QuickSort
{
    public void Sort(int[] list, int low, int high)
    {
        if (high <= low) return;           // 0 或 1 元素
        if (high == low + 1)               // 2 元素直接比較
        {
            if (list[low] > list[high])
                Swap(ref list[low], ref list[high]);
            return;
        }
        QuickSortRecursive(list, low, high);
    }

    private void QuickSortRecursive(int[] list, int low, int high)
    {
        if (low < high)
        {
            int pivot = Partition(list, low, high);
            QuickSortRecursive(list, low, pivot - 1);
            QuickSortRecursive(list, pivot + 1, high);
        }
    }

    private int Partition(int[] list, int low, int high)
    {
        int pivot = list[low]; // 選首元素為基準
        while (low < high)
        {
            // 從右向左找第一個 < pivot
            while (low < high && list[high] >= pivot) high--;
            if (low != high) Swap(ref list[low++], ref list[high]);

            // 從左向右找第一個 > pivot
            while (low < high && list[low] <= pivot) low++;
            if (low != high) Swap(ref list[low], ref list[high--]);
        }
        return low; // 基準最終位置
    }

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

關鍵設計決策分析

基準值選擇策略

分區演算法變體

• Hoare 分區（本實作）：雙向掃描、交換次數少、基準值最終位置需額外處理
• Lomuto 分區：單向掃描、程式碼簡單、交換次數多
• 三向切分：大量重複鍵值時極佳（Dutch National Flag）

效能優化建議

1. 小陣列切換插入排序：if (high - low < 16) InsertionSort(...)
2. 尾遞迴消除：迴圈處理較大分區，遞迴處理較小分區
3. 隨機化基準：Swap(ref list[low], ref list[random.Next(low, high+1)])
4. 平行化：Parallel.Invoke(() => Sort(left), () => Sort(right))（大陣列）

泛型化擴展

public static void QuickSort(T[] array, int low, int high) 
    where T : IComparable
{
    // 將比較 list[high] >= pivot 改為 list[high].CompareTo(pivot) >= 0
    // Swap 保持不變
}

測試驗證

var arr = new[] { 5, 2, 8, 1, 9, 3, 7, 4, 6 };
new QuickSort().Sort(arr, 0, arr.Length - 1);
// 結果: 1 2 3 4 5 6 7 8 9

總結

快速排序是實務中最高效的通用排序演算法之一，掌握其分區邏輯與優化技巧對效能敏感系統開發至關重要。

1. 上一篇文章： C# 動態釋放與續約 IP 位址（WMI 實作）
2. 下一篇文章： C# 泛型集合 List<T> 完整指南：動態容量、索引器與效能特性

關於C語言

C語言易忘細節：i++ 與 ++i 的本質區別及心理調適

C語言易忘細節：i++ 與 ++i 的本質區別及心理調適 C

C語言檔案讀寫：feof() 判斷檔案結束的正確用法與陷阱避坑

C語言檔案讀寫：feof() 判斷檔案結束的正確用法與陷阱避

Windows Forms 選單設計完全指南 (6)：為表單新增選單

四、為表單新增選單 4.1 新增主選單 .NET 的 Sy

C# 基本運算 (一)：算術、指派、遞增遞減與字串串接

C# 運算子三種：一元、二元、三元。所謂二元即參與運算變數有