<?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 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
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 quickSort(array $arr): array {
if (count($arr) <= 1) return $arr;
$pivot = $arr[0];
$left = $right = [];
for ($i = 1; $i < count($arr); $i++) {
if ($arr[$i] < $pivot) {
$left[] = $arr[$i];
} elseif ($arr[$i] > $pivot) {
$right[] = $arr[$i];
}
// 等於 pivot 的不放入左右,避免重複值無限遞歸
}
return array_merge(quickSort($left), [$pivot], quickSort($right));
}
// 原地快排(節省記憶體,較複雜)
function quickSortInPlace(array &$arr, int $low, int $high): void {
if ($low < $high) {
$pi = partition($arr, $low, $high);
quickSortInPlace($arr, $low, $pi - 1);
quickSortInPlace($arr, $pi + 1, $high);
}
}
function partition(array &$arr, int $low, int $high): int {
$pivot = $arr[$high];
$i = $low - 1;
for ($j = $low; $j <= $high - 1; $j++) {
if ($arr[$j] < $pivot) {
$i++;
[$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
}
}
[$arr[$i + 1], $arr[$high]] = [$arr[$high], $arr[$i + 1]];
return $i + 1;
}
range(1, 3000) 打亂取 1600 元素(含重複值)| 算法 | 平均耗時 (ms) | 時間複雜度 | 空間複雜度 | 穩定性 | 備註 |
|---|---|---|---|---|---|
| 冒泡排序 | ~420 | O(n²) | O(1) | 穩定 | 教學用、極小資料可用 |
| 選擇排序 | ~180 | O(n²) | O(1) | 不穩定 | 交換次數最少 (O(n)) |
| 插入排序 | ~95 | O(n²) / 最好 O(n) | O(1) | 穩定 | **近乎有序資料極快** |
| 快速排序 (遞歸新陣列) | ~3.2 | O(n log n) | O(n log n) | 不穩定 | 實務最快,但記憶體較大 |
| 快速排序 (原地) | ~2.8 | O(n log n) | O(log n) | 不穩定 | 生產環境首選實作 |
| PHP 內建 sort() | ~0.4 | O(n log n) | O(1) | 不穩定 | **C 級實作,快 1000 倍** |
zend_hash_sort(),使用 **Zend QuickSort (混合插入排序優化)**,無函數呼叫開銷。| 場景 | 推薦方案 | 理由 |
|---|---|---|
| 一般業務排序 | sort() / usort() / asort() / ksort() | 效能最佳、穩定可靠、功能完整 |
| 自定義複雜比較 | usort($arr, fn($a,$b) => $a['score'] <=> $b['score']) | 太空船運算子 <=> 簡潔高效 |
| 多欄位排序 | array_multisort() | 支援多鍵、多順序、大小寫不敏感 |
| 超大資料集 (百萬+) | 資料庫 ORDER BY + 索引 | 推給資料庫層,利用索引避免全表掃描 |
| 串流/記憶體受限 | Generator + 外部排序 / 分塊排序合併 | 不一次載入全部資料 |
| 教學/面試/特殊約束 | 手寫快速排序 (原地版) | 展示算法理解、符合空間限制 |
PHP 8.1 將內建排序升級為 **Timsort**(Python/Java 同款),對**部分有序資料**極度友善,最好情況 **O(n)**,最壞 **O(n log n)**,穩定排序。實測近乎有序資料比 QuickSort 快 10-50 倍。
**永遠優先使用 PHP 內建排序函式 (sort/usort/array_multisort)**。理解四大基礎算法原理是為了面試、教學、極端約束場景;生產環境**不要手寫排序**,除非你在造輪子(如實現特定穩定排序、外部排序、分散式排序)。