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

快速排序是改良版氣泡排序，採分治法：選取基準值將陣列分為兩部分，左側小於基準、右側大於基準，遞迴排序子陣列。平均時間複雜度 O(n log n)，空間複雜度 O(log n)。

完整實作程式碼

public class QuickSort {
    /// 
交換兩個整數
    private void Swap(ref int left, ref int right) {
        int temp = left;
        left = right;
        right = temp;
    }
    
    /// 
快速排序主邏輯
    /// 待排序陣列
    /// 起始索引
    /// 結束索引
    public void Sort(int[] list, int low, int high) {
        if (high <= low) return;
        
        // 兩個元素直接比較交換
        if (high == low + 1) {
            if (list[low] > list[high]) Swap(ref list[low], ref list[high]);
            return;
        }
        
        // 選取中間元素作為基準，避免已排序陣列最差情況
        int mid = (low + high) >> 1;
        int pivot = list[mid];
        Swap(ref list[low], ref list[mid]); // 基準移至最左
        
        int left = low + 1;
        int right = high;
        
        do {
            // 從左向右找第一個 >= pivot 的元素
            while (left <= right && list[left] < pivot) left++;
            // 從右向左找第一個 < pivot 的元素
            while (list[right] >= pivot) right--;
            
            if (left < right) Swap(ref list[left], ref list[right]);
        } while (left < right);
        
        // 將基準放到正確位置
        list[low] = list[right];
        list[right] = pivot;
        
        // 遞迴排序左右子陣列
        if (low + 1 < right) Sort(list, low, right - 1);
        if (right + 1 < high) Sort(list, right + 1, high);
    }
}

使用範例

int[] data = { 64, 34, 25, 12, 22, 11, 90 };
QuickSort qs = new QuickSort();
qs.Sort(data, 0, data.Length - 1);
// 結果：11, 12, 22, 25, 34, 64, 90

關鍵優化點

1. 三數取中法：實務上建議取 low、mid、high 三者中位數作為基準
2. 小陣列切換插入排序：元素數 < 10 時改用插入排序
3. 尾端遞迴優化：將較大分區用遞迴、較小分區用迴圈
4. 隨機化基準：防止惡意輸入導致 O(n²)

效能比較

.NET 內建 Array.Sort 採用內省排序，結合快速排序、堆積排序與插入排序，實務上直接使用即可。