萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 快速排序兩種實現:遞歸分治法與非遞歸棧模擬法,附基準測試與優化建議

雖 PHP 內建 sort()/usort() 基於 C 級 QuickSort 已極致優化,但理解快排原理、手寫實現是演算法面試與底層優化的必修課。本文提供遞歸版與迭代版完整代碼、複雜度分析、PHP 語言特性優化要點。

遞歸版:經典分治

function quickSortRecursive(array $arr): array {
    $len = count($arr);
    if ($len <= 1) return $arr;

    $pivot = $arr[0];
    $left = $right = [];

    for ($i = 1; $i < $len; $i++) {
        if ($arr[$i] <= $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }

    return array_merge(quickSortRecursive($left), [$pivot], quickSortRecursive($right));
}

迭代版:顯式棧模擬遞歸

function quickSortIterative(array &$arr): array {
    $stack = [$arr];
    $sorted = [];

    while ($stack) {
        $current = array_pop($stack);
        $len = count($current);

        if ($len <= 1) {
            if ($len === 1) $sorted[] = &$current[0]; // 引用避免拷貝
            continue;
        }

        $pivot = $current[0];
        $left = $right = [];

        for ($i = 1; $i < $len; $i++) {
            if ($current[$i] <= $pivot) $left[] = &$current[$i];
            else $right[] = &$current[$i];
        }

        // 棧先進後出:右 → 基準 → 左,保證左側先處理
        if ($right) array_push($stack, $right);
        array_push($stack, [$pivot]); // 基準作為單元素陣列
        if ($left) array_push($stack, $left);
    }
    return $sorted;
}

測試驗證

$test = [];
for ($i = 0; $i < 5; $i++) $test[] = mt_rand(0, 100);
var_dump($test);
var_dump(quickSortRecursive($test));
var_dump(quickSortIterative($test));

複雜度與 PHP 特性分析

指標遞歸版迭代版
時間複雜度平均 O(n log n),最壞 O(n²)同
空間複雜度O(log n) 棧幀 + O(n) 新陣列O(n) 顯式棧 + O(n) 結果
PHP 遞歸深度限制受 xdebug.max_nesting_level (默認 256) 限制,大數組會棧溢出無遞歸,無此限制
記憶體分配大量 array_merge 產生中間陣列引用傳遞 &$val 減少拷貝
實際效能中小數組尚可大數組更穩定

PHP 實戰優化關鍵點

  1. 基準點選擇:首元素極易遇到有序數組最壞情況,改用「三數取中」(首、中、尾中位數)或隨機基準。
  2. 小區間切換插入排序:if ($len < 15) return insertionSort($arr);,減少遞歸開銷。
  3. 原地分區:傳遞引用 &$arr,雙指針 i/j 原地交換,避免創建 $left/$right 新陣列。
  4. 尾遞歸優化:PHP 不支援 TCO,手寫迭代版等價於手動 TCO。
  5. 類型專用化:純整數陣列可用 SplFixedArray 減少內存開銷。

生產環境建議

直接使用 sort()/usort():C 實現、高度優化、支援自定義比較器、穩定排序(PHP 8+)。手寫快排僅用於教學、面試、特殊約束環境(如無標準庫的嵌入式 PHP)。

基準測試代碼片段

function benchmark(callable $sorter, array $data, int $runs = 10): float {
    $times = [];
    for ($i = 0; $i < $runs; $i++) {
        $copy = $data;
        $start = hrtime(true);
        $sorter($copy);
        $times[] = (hrtime(true) - $start) / 1e6; // ms
    }
    return array_sum($times) / $runs;
}

$data = range(1, 10000);
shuffle($data);
echo "Recursive: " . benchmark('quickSortRecursive', $data) . " ms\n";
echo "Iterative: " . benchmark('quickSortIterative', $data) . " ms\n";
echo "Native sort: " . benchmark('sort', $data) . " ms\n";

理解排序原理,不為造輪子,而是為在性能調優時能看懂 usort 回調的比較器開銷、記憶體分配模式,做出正確優化決策。

copyright © 萬盛學電腦網 all rights reserved