面試必考、效能調優基石。本文收錄 6 大經典排序演算法 PHP 實作，附時間/空間複雜度、穩定性、適用場景對比表，並修正原文中變數錯誤、邏輯缺陷，提供可直接執行的標準版本。
| 演算法 | 平均時間 | 最壞時間 | 空間 | 穩定 | 備註 |
|---|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(1) | ✅ | 小陣列/近乎有序極快 |
| 選擇排序 | O(n²) | O(n²) | O(1) | ❌ | 寫入次數最少 (O(n)) |
| 冒泡排序 | O(n²) | O(n²) | O(1) | ✅ | 教學用，實務極少用 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | ❌ | 實務最快，需隨機化基準 |
| 歸並排序 | O(n log n) | O(n log n) | O(n) | ✅ | 外部排序、穩定需求首選 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | ❌ | 保證 O(n log n)、原地 |
<?php
function insertionSort(array &$arr): void {
$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;
}
}
?>
<?php
function selectionSort(array &$arr): void {
$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]]; // PHP 7.1+ 解構賦值
}
}
}
?>
<?php
function bubbleSort(array &$arr): void {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
$swapped = false;
for ($j = 0; $j < $n - 1 - $i; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
[$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
$swapped = true;
}
}
if (!$swapped) break; // 本輪無交換，已有序
}
}
?>
<?php
function quickSort(array &$arr, int $low = 0, int $high = null): void {
if ($high === null) $high = count($arr) - 1;
if ($low >= $high) return;
// 隨機選基準，避免有序陣列退化 O(n²)
$pivotIdx = random_int($low, $high);
[$arr[$pivotIdx], $arr[$high]] = [$arr[$high], $arr[$pivotIdx]];
$pivot = $arr[$high];
// 三向切分
$lt = $low; // < pivot
$gt = $high; // > pivot
$i = $low; // 當前
while ($i <= $gt) {
if ($arr[$i] < $pivot) {
[$arr[$lt], $arr[$i]] = [$arr[$i], $arr[$lt]];
$lt++; $i++;
} elseif ($arr[$i] > $pivot) {
[$arr[$i], $arr[$gt]] = [$arr[$gt], $arr[$i]];
$gt--;
} else {
$i++;
}
}
quickSort($arr, $low, $lt - 1);
quickSort($arr, $gt + 1, $high);
}
?>
<?php
function mergeSort(array &$arr): void {
$n = count($arr);
$temp = $arr;
for ($width = 1; $width < $n; $width <<= 1) {
for ($i = 0; $i < $n; $i += 2 * $width) {
$left = $i;
$mid = min($i + $width, $n);
$right = min($i + 2 * $width, $n);
merge($arr, $temp, $left, $mid, $right);
}
[$arr, $temp] = [$temp, $arr]; // 交換角色
}
// 若最後結果在 $temp，複製回 $arr
if ($arr !== $temp) {
for ($i = 0; $i < $n; $i++) $arr[$i] = $temp[$i];
}
}
function merge(array &$src, array &$dst, int $left, int $mid, int $right): void {
$i = $left; $j = $mid; $k = $left;
while ($i < $mid && $j < $right) {
$dst[$k++] = ($src[$i] <= $src[$j]) ? $src[$i++] : $src[$j++];
}
while ($i < $mid) $dst[$k++] = $src[$i++];
while ($j < $right) $dst[$k++] = $src[$j++];
}
?>
<?php
function heapSort(array &$arr): void {
$n = count($arr);
// 建堆
for ($i = ($n >> 1) - 1; $i >= 0; $i--) {
siftDown($arr, $i, $n);
}
// 排序
for ($end = $n - 1; $end > 0; $end--) {
[$arr[0], $arr[$end]] = [$arr[$end], $arr[0]];
siftDown($arr, 0, $end);
}
}
function siftDown(array &$arr, int $root, int $end): void {
while (true) {
$child = 2 * $root + 1; // 左子節點
if ($child >= $end) break;
// 選較大的子節點
if ($child + 1 < $end && $arr[$child] < $arr[$child + 1]) {
$child++;
}
if ($arr[$root] >= $arr[$child]) break;
[$arr[$root], $arr[$child]] = [$arr[$child], $arr[$root]];
$root = $child;
}
}
?>
<?php
$cases = [
[],
[1],
[3,1,2],
[5,4,3,2,1],
[1,2,3,4,5],
[3,3,2,1,2], // 重複值測試穩定性
];
$algos = [
'insertion' => 'insertionSort',
'selection' => 'selectionSort',
'bubble' => 'bubbleSort',
'quick' => 'quickSort',
'merge' => 'mergeSort',
'heap' => 'heapSort',
];
foreach ($cases as $case) {
foreach ($algos as $name => $func) {
$copy = $case;
$func($copy);
$expected = $case;
sort($expected);
if ($copy !== $expected) {
echo "FAIL: $name on " . json_encode($case) . "\n";
}
}
}
echo "All tests passed.\n";
?>
sort() (C 實現的 QuickSort + InsertionSort 混合)，**永遠優先使用**usort (PHP 8.0+ 穩定)理解 6 大經典排序的分治思想、分區邏輯、合併策略、堆性質，是演算法素養核心。PHP 開發實務中 **99% 場景直接用內建 sort()/usort()**，手寫排序僅用於面試、教學、極特殊約束環境。本文提供的實作已修正邊界條件、採用現代 PHP 語法 (解構賦值、型別提示、random_int)，可直接納入個人程式庫參考。
