PHP 快速排序演算法：遞迴與迭代兩種實作詳解

雖然 PHP 內建 sort() 等排序函式效能優異，但在高併發或特定演算法面試場景下，掌握快速排序的遞迴與迭代實作仍具重要價值。本文提供兩種完整實作供參考學習。

遞迴法實作

採用分治策略，選取基準值將陣列分為左右兩部分，遞迴排序後合併。

/*** 遞迴法實現的快速排序 */
function quicksort($seq) {
    if (count($seq) <= 1) {
        return $seq;
    }
    $k = $seq[0];
    $x = array();
    $y = array();
    for ($i = 1; $i < count($seq); $i++) {
        if ($seq[$i] <= $k) {
            $x[] = $seq[$i];
        } else {
            $y[] = $seq[$i];
        }
    }
    $x = quicksort($x);
    $y = quicksort($y);
    return array_merge($x, array($k), $y);
}

迭代法實作

使用堆疊模擬遞迴過程，避免遞迴深度過大導致堆疊溢位，適合大量資料排序。

/*** 迭代法的快速排序 */
function quicksortx(&$seq) {
    $stack = array($seq);
    $sort = array();
    while ($stack) {
        $arr = array_pop($stack);
        if (count($arr) <= 1) {
            if (count($arr) == 1) {
                $sort[] = &$arr[0];
            }
            continue;
        }
        $k = $arr[0];
        $x = array();
        $y = array();
        $_size = count($arr);
        for ($i = 1; $i < $_size; $i++) {
            if ($arr[$i] <= $k) {
                $x[] = &$arr[$i];
            } else {
                $y[] = &$arr[$i];
            }
        }
        !empty($y) && array_push($stack, $y);
        array_push($stack, array($arr[0]));
        !empty($x) && array_push($stack, $x);
    }
    return $sort;
}

測試程式碼

/*** 產生隨機陣列進行測試 */
for ($i = 0; $i < 5; $i++) {
    $testArr[] = mt_rand(0, 100);
}
var_dump($testArr);
var_dump(quicksort($testArr));
var_dump(quicksortx($testArr));

效能比較與建議

• 遞迴法程式碼簡潔易懂，但受限於 PHP 遞迴深度限制（預設 100-200 層）
• 迭代法無遞迴深度限制，記憶體使用較穩定，適合大型資料集
• 實際專案建議優先使用內建 sort()/usort()，效能經 C 層優化遠超使用者空間實作