| 演算法 | 平均時間複雜度 | 最壞時間複雜度 | 空間複雜度 | 穩定性 | PHP 實作建議 |
|---|---|---|---|---|---|
| 氣泡排序 | O(n²) | O(n²) | O(1) | 穩定 | 教學/極小資料 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不穩定 | 教學/理解分治法 |
| 內建 sort() | O(n log n) | O(n log n) | O(1) | 不穩定 | 生產環境首選 |
<?php
/**
* 氣泡排序:相鄰比較,大者沉底 (遞增)
* @param array $arr 參考傳遞,原地排序
* @return array 排序後陣列 (同一參考)
*/
function bubbleSort(array &$arr): array
{
$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;
}
return $arr;
}
// 測試
$data = [23, 14, 35, 28, 45, 98, 12, 19, 1, 78];
echo "原始: " . implode(',', $data) . "\n";
bubbleSort($data);
echo "氣泡: " . implode(',', $data) . "\n";
// 輸出: 1,12,14,19,23,28,35,45,78,98
?>
<?php
/**
* 快速排序:分治法,選基準值分區
* @param array $arr
* @return array 新排序陣列 (非原地)
*/
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));
}
// 原地快速排序 (進階,節省記憶體)
function quickSortInPlace(array &$arr, int $low = 0, int $high = null): void
{
if ($high === null) $high = count($arr) - 1;
if ($low >= $high) return;
$pivot = partition($arr, $low, $high);
quickSortInPlace($arr, $low, $pivot - 1);
quickSortInPlace($arr, $pivot + 1, $high);
}
function partition(array &$arr, int $low, int $high): int
{
$pivotValue = $arr[$high];
$i = $low - 1;
for ($j = $low; $j < $high; $j++) {
if ($arr[$j] <= $pivotValue) {
$i++;
[$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
}
}
[$arr[$i + 1], $arr[$high]] = [$arr[$high], $arr[$i + 1]];
return $i + 1;
}
// 測試
$data = [23, 14, 35, 28, 45, 98, 12, 19, 1, 78];
$sorted = quickSort($data);
echo "快速: " . implode(',', $sorted) . "\n";
// 輸出: 1,12,14,19,23,28,35,45,78,98
?>
<?php
$arr = [23, 14, 35, 28, 45, 98, 12, 19, 1, 78];
sort($arr); // 遞增,重新索引
rsort($arr); // 遞減,重新索引
asort($arr); // 遞增,保持鍵值關聯
ksort($arr); // 鍵名遞增
usort($arr, fn($a, $b) => $a <=> $b); // 自訂比較 (太空船運算子 PHP 7+)
// 多維陣列排序
$users = [
['name'=>'A', 'age'=>30],
['name'=>'B', 'age'=>25],
];
usort($users, fn($a, $b) => $a['age'] <=> $b['age']);
// 或 array_multisort
array_multisort(array_column($users, 'age'), SORT_ASC, $users);
?>
理解氣泡排序 (O(n²)) 與快速排序 (O(n log n) 平均) 的原理,是演算法基礎訓練。**實務開發請直接使用 PHP 內建 sort()、usort()、array_multisort()**,它們基於 C 實作的混合排序 (Timsort/QuickSort 混合),效能極佳且經過充分測試。手寫排序僅供教學、面試或極特殊需求 (如自訂比較器無法用 usort 表達) 時使用。