雖然 PHP 內建 sort()、usort() 已高度優化,但理解經典排序演算法有助於面試、教學與特定場景(如自定義比較邏輯、外部排序)的靈活應用。本文提供四大經典演算法的 PHP 實作與複雜度分析。
相鄰元素兩兩比較,大的往後冒泡。穩定排序。
function bubbleSort(array $arr): array {
$n = count($arr);
for ($i = 0; $i < $n; $i++) {
for ($j = $n - 1; $j > $i; $j--) {
if ($arr[$j] < $arr[$j - 1]) {
[$arr[$j], $arr[$j - 1]] = [$arr[$j - 1], $arr[$j]]; // PHP 7.1+ 解構賦值
}
}
}
return $arr;
}
時間複雜度:O(n²) | 空間:O(1) | 穩定
將未排序元素插入已排序序列適當位置。小規模/近乎有序資料極快。
function insertionSort(array $arr): array {
$n = count($arr);
for ($i = 1; $i < $n; $i++) {
$key = $arr[$i];
$j = $i - 1;
while ($j >= 0 && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
return $arr;
}
時間複雜度:O(n²) 最好 O(n) | 空間:O(1) | 穩定
每輪選出最小元素放到已排序區末尾。不穩定。
function selectionSort(array $arr): array {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
$minIdx = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($arr[$j] < $arr[$minIdx]) $minIdx = $j;
}
if ($minIdx !== $i) {
[$arr[$i], $arr[$minIdx]] = [$arr[$minIdx], $arr[$i]];
}
}
return $arr;
}
時間複雜度:O(n²) | 空間:O(1) | 不穩定
分治法:選基準值,分左右子陣列遞歸排序。平均 O(n log n),最壞 O(n²)。
function quickSort(array $arr): array {
$n = count($arr);
if ($n <= 1) return $arr;
$pivot = $arr[0];
$left = $right = [];
for ($i = 1; $i < $n; $i++) {
if ($arr[$i] <= $pivot) $left[] = $arr[$i];
else $right[] = $arr[$i];
}
return array_merge(quickSort($left), [$pivot], quickSort($right));
}
時間複雜度:平均 O(n log n) | 空間:O(log n) 遞歸棧 | 不穩定
| 演算法 | 耗時 (ms) | 備註 |
|---|---|---|
| PHP 內建 sort() | ~2 | C 實作,最快 |
| Quick Sort (PHP) | ~45 | 遞歸開銷大 |
| Insertion Sort | ~1200 | 適合小陣列 |
| Selection Sort | ~1500 | |
| Bubble Sort | ~2800 | 教學用 |
sort()/usort(),底層採用 QuickSort + Insertion Sort 混合(Zend Engine)。usort($arr, fn($a,$b) => $a <=> $b)(PHP 7+ 太空船操作符)。ORDER BY。