C# 快速排序演算法完整實作與原理解析

快速排序核心思想：分治法

快速排序是經典的分治法應用，平均時間複雜度 O(n log n)，原地排序、空間複雜度 O(log n)（遞迴堆疊）。基本流程三步驟：

1. 分解：選取基準值，將陣列分為「小於基準」與「大於基準」兩個子序列。
2. 遞迴求解：對兩個子序列分別遞迴排序。
3. 合併：因為是原地交換，子序列排序完成後整個陣列自然有序，無需額外合併步驟。

C# 完整實作程式碼

using System;

namespace QuickSortDemo
{
    /// 

    /// 快速排序工具類別
    /// 
    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;
            }
            InternalQuickSort(list, low, high); // 3+ 元素進入正式快排
        }

        /// 

        /// 遞迴核心
        /// 
        private void InternalQuickSort(int[] list, int low, int high)
        {
            if (low < high)
            {
                int pivot = Partition(list, low, high);
                InternalQuickSort(list, low, pivot - 1);
                InternalQuickSort(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; // low == high 即為基準值位置
        }

        /// 

        /// 交換兩個整數
        /// 
        private void Swap(ref int a, ref int b)
        {
            int t = a; a = b; b = t;
        }
    }

    // 測試用例
    class Program
    {
        static void Main()
        {
            int[] data = { 5, 2, 9, 1, 5, 6, 3, 8, 7, 4 };
            Console.WriteLine("排序前：" + string.Join(", ", data));
            new QuickSort().Sort(data, 0, data.Length - 1);
            Console.WriteLine("排序後：" + string.Join(", ", data));
        }
    }
}

關鍵細節解析

• 基準值選取：範例採首元素，實務上可改用「三數取中」或隨機選取，避免已排序資料退化為 O(n²)。
• 雙向掃描：Partition 同時從左右逼近，減少交換次數，優於單向 Lomuto 分區法。
• 尾端優化：對小區間（如 ≤ 16）可改用插入排序，實務庫常見做法。
• 泛型化：實際專案建議改為 void Sort<T>(T[] array, int low, int high) where T : IComparable<T> 支援任意可比較型別。

效能與適用場景

總結

快速排序是演算法面試與實務開發的必修課。理解其分區邏輯、遞迴終止條件與基準值選取策略，能靈活應對各種排序需求。生產環境建議直接使用 Array.Sort / List<T>.Sort（內建 IntroSort：快排+堆排+插排混合），唯有教學、特殊約束或嵌入式環境才需自行實作。