程式碼實作
<?php
$arr = [345, 4, 17, 6, 52, 16, 58, 69, 32, 8, 234];
$n = count($arr);
for ($i = 1; $i < $n; $i++) {
for ($j = $n - 1; $j >= $i; $j--) {
if ($arr[$j] < $arr[$j - 1]) {
// 交換
[$arr[$j - 1], $arr[$j]] = [$arr[$j], $arr[$j - 1]]; // PHP 7.1+ 解構賦值
}
}
}
print_r($arr);
// [4, 6, 8, 16, 17, 32, 52, 58, 69, 234, 345]
?>
演算法原理
- 雙重迴圈：外層控制趟數 (共 n-1 趟)，內層從尾部往前比較相鄰元素
- 每趟將最小元素「浮」到前端 (或最大元素沉到尾端)
- 第 i 趟結束後，前 i 個位置已確定為最小的 i 個元素
複雜度分析
| 指標 | 複雜度 | 說明 |
|---|
| 時間 (最好) | O(n) | 已排序陣列，加入 swapped 標記可提早結束 |
| 時間 (平均/最差) | O(n²) | 逆序或隨機陣列 |
| 空間 | O(1) | 原地排序，僅需常數額外空間 |
| 穩定性 | 穩定 | 相等元素相對順序不變 |
優化版：提早結束旗標
<?php
function bubbleSortOptimized(array &$arr)
{
$n = count($arr);
for ($i = 1; $i < $n; $i++) {
$swapped = false;
for ($j = $n - 1; $j >= $i; $j--) {
if ($arr[$j] < $arr[$j - 1]) {
[$arr[$j - 1], $arr[$j]] = [$arr[$j], $arr[$j - 1]];
$swapped = true;
}
}
if (!$swapped) break; // 本趟無交換 = 已排序完成
}
}
?>
實務建議
- 教學/極小資料集 (n < 50) 可用
- 生產環境 嚴禁 使用 O(n²) 排序，請直接用
sort() / usort() (內建 QuickSort/MergeSort 混合，O(n log n))
- 面試常考：手寫冒泡、快排、合併排序、堆排序原理與複雜度比較
