雖 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));
| 指標 | 遞歸版 | 迭代版 |
|---|---|---|
| 時間複雜度 | 平均 O(n log n),最壞 O(n²) | 同 |
| 空間複雜度 | O(log n) 棧幀 + O(n) 新陣列 | O(n) 顯式棧 + O(n) 結果 |
| PHP 遞歸深度限制 | 受 xdebug.max_nesting_level (默認 256) 限制,大數組會棧溢出 | 無遞歸,無此限制 |
| 記憶體分配 | 大量 array_merge 產生中間陣列 | 引用傳遞 &$val 減少拷貝 |
| 實際效能 | 中小數組尚可 | 大數組更穩定 |
if ($len < 15) return insertionSort($arr);,減少遞歸開銷。&$arr,雙指針 i/j 原地交換,避免創建 $left/$right 新陣列。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 回調的比較器開銷、記憶體分配模式,做出正確優化決策。