PHP 快速排序算法實現：遞歸版與原地分區版對比

算法簡介

快速排序採用分治策略，平均時間複雜度 O(n log n)，是實踐中最高效的通用排序算法之一。本文展示兩種 PHP 實現：遞歸數組拼接版（易理解）和 原地分區版（節省內存，接近標準庫實現）。

版本一：遞歸數組拼接（教學友好）

<?php
function quicksort($arr) {
    if (count($arr) <= 1) return $arr; // 基線條件

    $pivot = $arr[0]; // 基準值
    $left = $right = [];

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

    // 遞歸排序左右子數組並合併
    return array_merge(quicksort($left), [$pivot], quicksort($right));
}

// 測試
$arr = [5, 3, 8, 2, 5, 9, 7, 2, 1, 4, 0];
print_r(quicksort($arr));
?>

特點：代碼簡潔，符合數學定義，但每次遞歸創建新數組，空間複雜度 O(n log n)，大數據時內存開銷大。

版本二：原地分區（內存高效）

<?php
/**
 * 原地快速排序
 * @param int $left 左邊界索引
 * @param int $right 右邊界索引
 * @param array &$arr 參考傳遞數組，直接修改原數組
 */
function quickSort($left, $right, &$arr) {
    $l = $left;
    $r = $right;
    $pivot = $arr[(($left + $right) / 2) | 0]; // 取中間元素為基準，位運算取整
    $temp = 0;

    while ($l < $r) {
        // 從左向右找第一個 >= pivot 的元素
        while ($arr[$l] < $pivot) $l++;
        // 從右向左找第一個 <= pivot 的元素
        while ($arr[$r] > $pivot) $r--;

        if ($l >= $r) break;

        // 交換
        $temp = $arr[$l];
        $arr[$l] = $arr[$r];
        $arr[$r] = $temp;

        // 優化：若交換後等於基準值，移動指針避免死循環
        if ($arr[$l] == $pivot) $r--;
        if ($arr[$r] == $pivot) $l++;
    }

    // 指針相遇時錯開
    if ($l == $r) {
        $l++;
        $r--;
    }

    // 遞歸處理左右區間
    if ($left < $r) quickSort($left, $r, $arr);
    if ($right > $l) quickSort($l, $right, $arr);
}

// 測試
$arr = [9, 8, 17, 6, 26, 4, 33, 2, 1];
quickSort(0, count($arr) - 1, $arr);
print_r($arr);
?>

特點：通過引用傳遞 &$arr 直接在原數組上操作，空間複雜度 O(log n)（遞歸棧），適合大數據量。基準值選取中間元素，一定程度上緩解有序數組最壞情況。

性能對比與建議

生產環境最佳實踐

1. 優先使用內置函數：sort($arr)、rsort($arr) 等基於 C 實現的 QuickSort / MergeSort 混合算法，性能最優。
2. 若需自定義比較邏輯，使用 usort($arr, fn($a,$b) => $a <=> $b)（PHP 7+ 太空船操作符）。
3. 自行實現時，考慮三數取中法選基準、小區間切換插入排序、尾遞歸優化等工程化手段。