排序算法是程序員必備基本功，PHP 雖內置 sort()、usort() 等高效函數，但理解底層原理對優化業務邏輯、面試、編寫擴展至關重要。本文匯總 7 種經典算法的 PHP 實現，包含時間/空間複雜度分析、穩定性說明、適用場景與優化建議。
| 算法 | 平均時間 | 最好情況 | 最壞情況 | 空間複雜度 | 穩定性 | 備註 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 穩定 | 教學用，實戰極少用 |
| 選擇排序 | O(n²) | O(n²) | O(n²) | O(1) | 不穩定 | 交換次數少 |
| 插入排序 | O(n²) | O(n) | O(n²) | O(1) | 穩定 | 小數組/近乎有序極快 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不穩定 | 實戰首選，PHP 內部採用 |
| 歸並排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 穩定 | 外部排序、鏈表排序首選 |
| 二分查找 | O(log n) | O(1) | O(log n) | O(1)/O(log n) | - | 需有序數組 |
/**
* 冒泡排序：相鄰元素兩兩比較，大的後移
* @param array $arr 引用傳遞排序
* @return void
*/
function bubble_sort(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]]; // PHP 7.1+ 解構賦值交換
$swapped = true;
}
}
if (!$swapped) break; // 本輪無交換，已有序
}
}
// 測試
$arr = [64, 34, 25, 12, 22, 11, 90];
bubble_sort($arr);
print_r($arr); // [11, 12, 22, 25, 34, 64, 90]
/**
* 歸並排序：分治法，遞歸分解再合併
* @param array $arr
* @return array 新排序數組（不修改原數組）
*/
function merge_sort(array $arr): array {
$len = count($arr);
if ($len <= 1) return $arr;
$mid = $len >> 1; // 位運算除以 2
$left = merge_sort(array_slice($arr, 0, $mid));
$right = merge_sort(array_slice($arr, $mid));
return merge($left, $right);
}
/**
* 合併兩個有序數組
*/
function merge(array $left, array $right): array {
$result = [];
$i = $j = 0;
$lLen = count($left);
$rLen = count($right);
while ($i < $lLen && $j < $rLen) {
$result[] = ($left[$i] <= $right[$j]) ? $left[$i++] : $right[$j++];
}
// 追加剩餘
while ($i < $lLen) $result[] = $left[$i++];
while ($j < $rLen) $result[] = $right[$j++];
return $result;
}
// 測試
$arr = [38, 27, 43, 3, 9, 82, 10];
print_r(merge_sort($arr)); // [3, 9, 10, 27, 38, 43, 82]
array_slice 複製開銷，傳遞索引範圍/**
* 快速排序：選取基準，分區，遞歸
* @param array $arr
* @return array
*/
function quick_sort(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(quick_sort($left), [$pivot], quick_sort($right));
}
// 三數取中優化版
function quick_sort_optimized(array $arr): array {
$n = count($arr);
if ($n <= 1) return $arr;
if ($n <= 16) return insertion_sort($arr); // 小數組用插入排序
// 三數取中選基準
$mid = $n >> 1;
$pivot = median_of_three($arr[0], $arr[$mid], $arr[$n - 1]);
$left = $right = $equal = [];
foreach ($arr as $v) {
if ($v < $pivot) $left[] = $v;
elseif ($v > $pivot) $right[] = $v;
else $equal[] = $v;
}
return array_merge(quick_sort_optimized($left), $equal, quick_sort_optimized($right));
}
function median_of_three($a, $b, $c) {
if (($a - $b) * ($c - $a) >= 0) return $a;
return (($b - $a) * ($c - $b) >= 0) ? $b : $c;
}
function insertion_sort(array $arr): array {
for ($i = 1, $n = count($arr); $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;
}
PHP 7+ 的 zend_qsort 採用三路快速排序（荷蘭國旗問題），針對大量重複鍵優化，並對小分區切換插入排序，非遞歸實現避免棧溢出。
/**
* 選擇排序：每輪選最小值放到已排序區末尾
* @param array $arr
* @return array
*/
function selection_sort(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;
}
/**
* 插入排序：將當前元素插入已排序區適當位置
* @param array $arr
* @return array
*/
function insertion_sort(array $arr): array {
$n = count($arr);
for ($i = 1; $i < $n; $i++) {
$key = $arr[$i];
$j = $i - 1;
// 向右移動大於 key 的元素
while ($j >= 0 && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
return $arr;
}
/**
* 二分查找遞歸版
* @param array $arr 有序數組
* @param int $low 低索引
* @param int $high 高索引
* @param mixed $target 目標值
* @return int|false 索引或 false
*/
function binary_search_recursive(array $arr, int $low, int $high, $target) {
if ($low > $high) return false;
$mid = (($low + $high) >> 1); // 位運算平均，防溢出
if ($arr[$mid] === $target) return $mid;
return $target < $arr[$mid]
? binary_search_recursive($arr, $low, $mid - 1, $target)
: binary_search_recursive($arr, $mid + 1, $high, $target);
}
/**
* 二分查找迭代版（推薦生產環境，無遞歸開銷）
*/
function binary_search_iterative(array $arr, $target) {
$low = 0;
$high = count($arr) - 1;
while ($low <= $high) {
$mid = (($low + $high) >> 1);
if ($arr[$mid] === $target) return $mid;
if ($target < $arr[$mid]) {
$high = $mid - 1;
} else {
$low = $mid + 1;
}
}
return false;
}
// 測試
$arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
var_dump(binary_search_iterative($arr, 23)); // int(5)
var_dump(binary_search_recursive($arr, 0, 9, 23)); // int(5)
| 場景 | 推薦方案 | 理由 |
|---|---|---|
| 一般業務排序 | sort()/rsort()/usort() | C 級實現、高度優化、支持自定義比較 |
| 關聯數組按值排序 | asort()/arsort() | 保持鍵值關係 |
| 關聯數組按鍵排序 | ksort()/krsort() | 保持鍵值關係 |
| 多字段複雜排序 | array_multisort() | 支持多維度、混合排序 |
| 學習/面試/特殊約束 | 手寫算法 | 理解原理、應對特殊需求（如外部排序、穩定性要求） |
| 海量數據外部排序 | 歸並排序 + 文件分塊 | 內存受限、磁順序讀寫 |
掌握經典排序算法的核心在於理解分治思想（快速/歸並）、增量構建（插入/選擇）、雙指針/縮小區間（二分）。PHP 開發中 99% 場景直接使用內置函數，但理解算法邊界（穩定性、空間換時間、小數組優化）能幫助你在性能調優、異常排查、系統設計中做出正確決策。建議將本文代碼封裝為 Algorithm\Sort 命名空間庫，配合 PHPUnit 單元測試，作為團隊技術資產沉澱。
