快速排序是經典分治算法,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));
?>
原地排序,空間 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);
?>
左右指標向中間掃描交換,處理相等元素時仍交換,最壞情況仍保持 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);
?>
基準值 $pivot 保存在變數中,左側位置 $arr[$low] 已被覆蓋。必須先從右向左找較小值填左坑,再從左向右找較大值填右坑。若互換,左坑會被右側較大值填入,導致基準值丟失。
$arr[$right] = $pivot 不可省略?考慮兩元素陣列 [5, 2]:
$pivot=5, $left=0, $right=1$arr[1]=2 不大於 5,停在 1$arr[0] = $arr[1] → 陣列變 [2, 2]$left=0 條件失效[2, 2] 錯誤$arr[1] = 5 → 正確 [2, 5]| 版本 | 時間複雜度(平均) | 最壞情況 | 空間複雜度 | 穩定性 | 推薦場景 |
|---|---|---|---|---|---|
| 簡單版 | O(n log n) | O(n²) | O(n log n) | 不穩定 | 教學、小資料、函數式風格 |
| Lomuto | O(n log n) | O(n²) | O(log n) | 不穩定 | 教學、嵌入式、資料隨機 |
| Hoare | O(n log n) | O(n log n)* | O(log n) | 不穩定 | 通用、生產環境、含重複值 |
* Hoare 版本在全相等元素時仍交換,避免退化,但增加交換開銷。
sort()/usort(),底層實作為高度優化的 Quicksort/Mergesort 混合usort($arr, fn($a,$b) => $a <=> $b) (PHP 7+ 太空船運算子)理解三種分區策略的權衡,能幫助您在面試、教學、特殊場景下做出正確選擇。