萬盛學電腦網

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

PHP 快速排序三種實作比較:簡單版、Lomuto 分區、Hoare 雙向掃描經典算法

快速排序是經典分治算法,PHP 實作有多種分區策略。本文展示三種版本:簡單易懂但空間換時間、算法導論 Lomuto 單向掃描、Hoare 雙向掃描經典原地排序,並分析最壞情況、空間複雜度與實際效能差異。

版本一:簡單版(陣列分割 + 合併)

直觀但每層遞迴建立新陣列,空間複雜度 O(n log n),最壞 O(n²)。

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

// 測試
$arr = [3, 6, 8, 10, 1, 2, 1];
print_r(quick_sort_simple($arr));
?>

版本二:Lomuto 分區(單向掃描,算法導論標準)

原地排序,空間 O(log n) 遞迴棧。最壞情況(已排序/全相等)退化 O(n²)。

<?php
function quick_sort_lomuto(array &$arr, int $low, int $high): void {
    if ($low >= $high) return;
    
    $pivotIndex = $low;
    for ($i = $low + 1; $i <= $high; $i++) {
        if ($arr[$i] < $arr[$pivotIndex]) {
            $pivotIndex++;
            [$arr[$i], $arr[$pivotIndex]] = [$arr[$pivotIndex], $arr[$i]];
        }
    }
    [$arr[$low], $arr[$pivotIndex]] = [$arr[$pivotIndex], $arr[$low]];
    
    quick_sort_lomuto($arr, $low, $pivotIndex - 1);
    quick_sort_lomuto($arr, $pivotIndex + 1, $high);
}

// 使用
$arr = [3, 6, 8, 10, 1, 2, 1];
quick_sort_lomuto($arr, 0, count($arr) - 1);
print_r($arr);
?>

版本三:Hoare 雙向掃描(經典原地分區)

左右指標向中間掃描交換,處理相等元素時仍交換,最壞情況仍保持 O(n log n)。

<?php
function quick_sort_hoare(array &$arr, int $low, int $high): void {
    if ($low >= $high) return;
    
    $pivot = $arr[$low];
    $left  = $low;
    $right = $high;
    
    while ($left < $right) {
        while ($left < $right && $arr[$right] > $pivot) $right--;
        $arr[$left] = $arr[$right];
        
        while ($left < $right && $arr[$left] < $pivot) $left++;
        $arr[$right] = $arr[$left];
    }
    
    $arr[$left] = $pivot;  // 關鍵:將基準值放回最終位置
    
    quick_sort_hoare($arr, $low, $left - 1);
    quick_sort_hoare($arr, $left + 1, $high);
}

// 使用
$arr = [3, 6, 8, 10, 1, 2, 1];
quick_sort_hoare($arr, 0, count($arr) - 1);
print_r($arr);
?>

關鍵細節深度解析

為什麼 Hoare 版本左右迴圈不可互換?

基準值 $pivot 保存在變數中,左側位置 $arr[$low] 已被覆蓋。必須先從右向左找較小值填左坑,再從左向右找較大值填右坑。若互換,左坑會被右側較大值填入,導致基準值丟失。

為什麼 $arr[$right] = $pivot 不可省略?

考慮兩元素陣列 [5, 2]:

  1. $pivot=5, $left=0, $right=1
  2. 右掃描:$arr[1]=2 不大於 5,停在 1
  3. $arr[0] = $arr[1] → 陣列變 [2, 2]
  4. 左掃描:$left=0 條件失效
  5. 若省略最後賦值,陣列變 [2, 2] 錯誤
  6. 執行賦值 $arr[1] = 5 → 正確 [2, 5]

效能與選擇建議

版本時間複雜度(平均)最壞情況空間複雜度穩定性推薦場景
簡單版O(n log n)O(n²)O(n log n)不穩定教學、小資料、函數式風格
LomutoO(n log n)O(n²)O(log n)不穩定教學、嵌入式、資料隨機
HoareO(n log n)O(n log n)*O(log n)不穩定通用、生產環境、含重複值

* Hoare 版本在全相等元素時仍交換,避免退化,但增加交換開銷。

PHP 實際應用建議

  • 實際專案直接使用 sort()/usort(),底層實作為高度優化的 Quicksort/Mergesort 混合
  • 需自訂比較邏輯時用 usort($arr, fn($a,$b) => $a <=> $b) (PHP 7+ 太空船運算子)
  • 手寫排序僅用於演算法學習、特殊約束環境、面試考核

理解三種分區策略的權衡,能幫助您在面試、教學、特殊場景下做出正確選擇。

copyright © 萬盛學電腦網 all rights reserved