PHP 快速排序三大演算法實現與效能對比：從教科書到工程化優化

快速排序是面試與工程常考核心。本文實現並對比三種 PHP 版本：簡單易懂但空間換時間、單向掃描（Lomuto 分區）、雙向掃描（Hoare 分區），深度剖析最壞情況、空間複雜度與實際基準測試。

方法一：函數式風格（空間換時間，教學用）

function quick_sort_v1(array $array): array {
    if (count($array) <= 1) return $array;
    $key = $array[0];
    $left = $right = [];
    for ($i = 1; $i < count($array); $i++) {
        if ($array[$i] >= $key) $right[] = $array[$i];
        else $left[] = $array[$i];
    }
    return array_merge(quick_sort_v1($left), [$key], quick_sort_v1($right));
}

• 時間：平均 O(n log n)，最壞 O(n²)（已有序陣列）
• 空間：O(n log n) 額外陣列 + 遞歸棧
• 優點：代碼極簡、不可變風格、函數式友好
• 缺點：大量陣列複製與合併，PHP 實際效能最差

方法二：Lomuto 單向掃描（原地分區，教科書經典）

function quick_sort_v2(array &$array, int $start, int $end): void {
    if ($start >= $end) return;
    $mid = $start;
    for ($i = $start + 1; $i <= $end; $i++) {
        if ($array[$i] < $array[$mid]) {
            $mid++;
            [$array[$i], $array[$mid]] = [$array[$mid], $array[$i]];
        }
    }
    [$array[$start], $array[$mid]] = [$array[$mid], $array[$start]];
    quick_sort_v2($array, $start, $mid - 1);
    quick_sort_v2($array, $mid + 1, $end);
}

• 分區邏輯：$mid 指向「小於基準區」尾部，掃描到更小元素時擴展區間並交換。
• 最壞 O(n²)：全相等元素導致每次分區僅縮減 1 個元素。
• 空間：O(log n) 遞歸棧（原地交換）

方法三：Hoare 雙向掃描（工程首選，抗退化）

function quick_sort_v3(array &$array, int $start, int $end): void {
    if ($end <= $start) return;
    $key = $array[$start];
    $left = $start;
    $right = $end;
    while ($left < $right) {
        while ($left < $right && $array[$right] > $key) $right--;
        $array[$left] = $array[$right];          // 關鍵：右值覆蓋左值（左值已備份在 $key）
        while ($left < $right && $array[$left] < $key) $left++;
        $array[$right] = $array[$left];          // 左值覆蓋右值
    }
    $array[$right] = $key;                       // 基準歸位
    quick_sort_v3($array, $start, $right - 1);
    quick_sort_v3($array, $right + 1, $end);
}

Hoare 分區三大精髓解析

1. 為何左先動？ 基準值備份在 $key，左位置已「空出」，可安全被右值覆蓋。若右先動，左值未備份會丟失。
2. 為何不可省略 $array[$right] = $key？ 極端情況 [5,2]：$left=0, $right=1，循環結束時 $left=$right=0，若不寫回 $key，陣列變 [2,2] 錯誤。
3. 嚴格 < / > 而非 <= / >=：相等元素不交換，避免全相等陣列退化為 O(n²) 且產生 n 次無意義交換。

效能基準測試（10 萬隨機整數，PHP 8.2）

工程化建議

• 生產代碼直接用 sort()/usort()：C 實現、高度優化、穩定性經實戰驗證。
• 教學/面試/特殊約束：採用 Hoare 雙向掃描（v3），並加入隨機化基準選取避免最壞情況：

  $pivotIdx = mt_rand($start, $end);
  [$array[$start], $array[$pivotIdx]] = [$array[$pivotIdx], $array[$start]];
  

• 小陣列閾值優化：if ($end - $start < 16) { insertion_sort(...); return; }
• 尾遞歸消除：手動改寫為迭代棧，防止深度遞歸棧溢出。

擴展閱讀

• 《算法導論》第 7 章：Quicksort 完整證明
• PHP 內核源碼 ext/standard/array.c 中的 php_array_sort 實現
• Timsort 混合排序原理（Python/Java/PHP 8+ 內建採用）

理解三種分區策略的本質差異，不僅能應付面試，更能在需要自定義排序邏輯（如多鍵排序、外部排序）時做出正確架構決策。