PHP 冒泡排序算法深度解析：從基礎實現到優化變體與複雜度分析

算法原理

冒泡排序通過重複遍歷數組，比較相鄰元素並交換順序，使較大（或較小）元素逐漸「冒泡」到數組末端。雖時間複雜度為 O(n²)，但因原理直觀、代碼簡潔，是教學入門經典。

基礎實現（升序）

<?php
$arr = [345, 4, 17, 6, 52, 16, 58, 69, 32, 8, 234];
$n = count($arr);

// 外層控制遍歷輪數（需 n-1 輪）
for ($i = 1; $i < $n; $i++) {
    // 內層從末尾向前比較相鄰元素
    // 第 i 輪結束後，最後 i 個元素已有序，無需再比較
    for ($j = $n - 1; $j >= $i; $j--) {
        if ($arr[$j] < $arr[$j - 1]) {
            // 交換
            $temp = $arr[$j - 1];
            $arr[$j - 1] = $arr[$j];
            $arr[$j] = $temp;
        }
    }
}

print_r($arr);
// 結果：[4, 6, 8, 16, 17, 32, 52, 58, 69, 234, 345]

圖解執行過程（以 [3, 1, 4, 2] 為例）

優化變體

1. 標誌位優化（提前終止）

function bubbleSortOptimized(array &$arr): void
{
    $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]]; // PHP 7.1+ 解構賦值交換
                $swapped = true;
            }
        }
        // 本輪無交換，說明已有序
        if (!$swapped) break;
    }
}

效果： 最好情況（已有序）時間複雜度降為 O(n)。

2. 雞尾酒排序 / 雙向冒泡排序

function cocktailSort(array &$arr): void
{
    $left = 0;
    $right = count($arr) - 1;
    while ($left < $right) {
        // 正向：將最大值移到右端
        for ($i = $left; $i < $right; $i++) {
            if ($arr[$i] > $arr[$i + 1]) {
                [$arr[$i], $arr[$i + 1]] = [$arr[$i + 1], $arr[$i]];
            }
        }
        $right--;

        // 反向：將最小值移到左端
        for ($i = $right; $i > $left; $i--) {
            if ($arr[$i] < $arr[$i - 1]) {
                [$arr[$i], $arr[$i - 1]] = [$arr[$i - 1], $arr[$i]];
            }
        }
        $left++;
    }
}

優勢： 減少「烏龜」（小值在右端需慢速左移）問題，實際運行約快 20-30%。

複雜度分析

PHP 內建排序對比

<?php
$arr = [345, 4, 17, 6, 52, 16, 58, 69, 32, 8, 234];

// 1. sort() - 快速排序（C 實現，極快）
sort($arr);
// 2. asort() - 保持鍵值關聯
// 3. usort() - 自定義比較
usort($arr, fn($a, $b) => $a <=> $b); // PHP 7+ 太空船操作符

// 性能對比（10萬隨機整數）
// 冒泡排序：~15-30 秒
// sort()：~0.01 秒
// 差距：3-4 個數量級！

何時使用冒泡排序？

• ✅ 教學演示、面試考察、極小數據集（< 50 元素）
• ✅ 近乎有序數組（配合標誌位優化）
• ✅ 內存極度受限環境（嵌入式、無庫環境）
• ❌ 所有生產環境業務代碼

生產環境排序最佳實踐

1. 首選內建函數： sort()、rsort()、asort()、ksort() — C 級性能，經過大規模驗證
2. 複雜對象排序： usort($arr, fn($a, $b) => $a['priority'] <=> $b['priority'])
3. 多字段排序： array_multisort() 或 usort 組合邏輯
4. 大數據外部排序： 分塊排序 + 歸併（MapReduce 思想）