PHP 快速排序演算法：遞迴版、迭代版、三向切分優化與效能測試

快速排序是平均 O(n log n) 的不穩定排序，PHP 內建 sort() 已高度優化 (Timsort)，但在教學、特定資料結構、嵌入式環境仍需手寫。本文提供遞迴版、迭代版 (模擬堆疊)、三向切分 (荷蘭國旗問題) 三種實作，並附效能基準測試與避坑指南。

1. 經典遞迴版 (Lomuto 分區)

function quickSortRecursive(array &$arr, int $low = 0, int $high = null): void
{
    if ($high === null) $high = count($arr) - 1;
    if ($low >= $high) return;

    $pivotIndex = partition($arr, $low, $high);
    quickSortRecursive($arr, $low, $pivotIndex - 1);
    quickSortRecursive($arr, $pivotIndex + 1, $high);
}

function partition(array &$arr, int $low, int $high): int
{
    $pivot = $arr[$high]; // 選最後一個為基準
    $i = $low - 1;

    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] <= $pivot) {
            $i++;
            [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]]; // PHP 7.1+ 解構賦值交換
        }
    }
    [$arr[$i + 1], $arr[$high]] = [$arr[$high], $arr[$i + 1]];
    return $i + 1;
}

2. 迭代版 (自維護堆疊，避免遞迴深度限制)

function quickSortIterative(array &$arr): void
{
    $stack = [ [0, count($arr) - 1] ];

    while ($stack) {
        [$low, $high] = array_pop($stack);
        if ($low >= $high) continue;

        $pivotIndex = partition($arr, $low, $high);

        // 先壓入較大分區，減少堆疊最大深度 (尾端優化)
        $leftSize = $pivotIndex - $low;
        $rightSize = $high - $pivotIndex;

        if ($leftSize > $rightSize) {
            if ($leftSize > 1) $stack[] = [$low, $pivotIndex - 1];
            if ($rightSize > 1) $stack[] = [$pivotIndex + 1, $high];
        } else {
            if ($rightSize > 1) $stack[] = [$pivotIndex + 1, $high];
            if ($leftSize > 1) $stack[] = [$low, $pivotIndex - 1];
        }
    }
}

3. 三向切分版 (Dutch National Flag，大量重複鍵極快)

function quickSort3Way(array &$arr, int $low = 0, int $high = null): void
{
    if ($high === null) $high = count($arr) - 1;
    if ($low >= $high) return;

    $lt = $low;
    $gt = $high;
    $pivot = $arr[$low]; // 選第一個
    $i = $low;

    while ($i <= $gt) {
        if ($arr[$i] < $pivot) {
            [$arr[$lt], $arr[$i]] = [$arr[$i], $arr[$lt]];
            $lt++;
            $i++;
        } elseif ($arr[$i] > $pivot) {
            [$arr[$i], $arr[$gt]] = [$arr[$gt], $arr[$i]];
            $gt--;
        } else {
            $i++;
        }
    }

    // 遞迴處理 < pivot 和 > pivot 區間
    quickSort3Way($arr, $low, $lt - 1);
    quickSort3Way($arr, $gt + 1, $high);
}

效能基準測試 (PHP 8.2, 10 萬元素)

關鍵優化技巧

1. 基準選擇：三數取中 (首、中、尾) 或隨機選擇，避免已排序資料退化 O(n²)。
2. 小區間切換插入排序：長度 < 15-20 時改用插入排序，減少遞迴開銷。
3. 尾端遞迴優化：迭代版先處理較小分區，堆疊深度限制在 O(log n)。
4. 就地交換：PHP 陣列為有序映射，交換元素涉及鍵值重建，效能較 C 陣列差數量級。

何時在 PHP 專案中手寫排序？

• 排序自訂物件集合 (實作 Comparator 介面)。
• 需保持原陣列參考 (內建 sort() 會重建索引)。
• 教學示範、演算法面試、嵌入式 PHP (無標準庫)。
• 一般業務邏輯請直接用 sort()、usort()、array_multisort()。

現代 PHP 排序最佳實踐

 $a->priority <=> $b->priority); // 太空船運算子

// 多鍵排序
array_multisort(
    array_column($arr, 'category'), SORT_ASC,
    array_column($arr, 'price'), SORT_DESC,
    $arr
);

理解快速排序變體原理有助於電腦科學素養，但生產環境請優先使用 PHP 內建高度優化的排序函式，僅在特定約束下手寫演算法。