Visual C# 常用排序演算法（四）：快速排序原理、分區過程與遞迴實作

編輯：關於C語言

基本思想

分治法：選取基準值，將陣列分為左右兩區 (左 ≤ 基準 ≤ 右)，遞迴處理子區。

分區過程示範

初始：[49, 38, 65, 97, 76, 13, 27, 49]

單趟分區交換步驟：

第1次交換: [27, 38, 65, 97, 76, 13, 49, 49]
第2次交換: [27, 38, 49, 97, 76, 13, 65, 49]
第3次交換: [27, 38, 13, 97, 76, 49, 65, 49]
第4次交換: [27, 38, 13, 49, 76, 97, 65, 49]

分區結果：[27, 38, 13] 49 [76, 97, 65, 49]

遞迴處理子區，最終有序：13, 27, 38, 49, 49, 65, 76, 97

C# 遞迴實作

private static void QuickSort(ref double[] array, int left, int right)
{
    int pivot = left;
    bool scanRight = true, scanLeft = true;
    
    while (scanRight || scanLeft)
    {
        scanRight = false; scanLeft = false;
        
        // 從右向左掃描：找小於基準的元素
        for (int i = right; i > pivot; i--)
        {
            if (array[i] < array[pivot])
            {
                ExchangeValue(ref array[i], ref array[pivot]);
                pivot = i;
                scanRight = true;
                break;
            }
        }
        
        // 從左向右掃描：找大於基準的元素
        for (int i = left; i < pivot; i++)
        {
            if (array[i] > array[pivot])
            {
                ExchangeValue(ref array[i], ref array[pivot]);
                pivot = i;
                scanLeft = true;
                break;
            }
        }
    }
    
    // 遞迴處理左右子區
    if (right - left > 0)
    {
        if (pivot != left)  QuickSort(ref array, left, pivot - 1);
        if (pivot != right) QuickSort(ref array, pivot + 1, right);
    }
}

private static void ExchangeValue(ref double a, ref double b)
{
    double t = a; a = b; b = t;
}