PHP 冒泡排序演算法深度解析與優化實作

演算法概念

冒泡排序是最基礎的比較排序演算法。核心思想：重複遍歷陣列，比較相鄰元素，若順序錯誤則交換。每輪遍歷會將最大（或最小）元素「浮」至陣列末端，故得名。

基本實作

<?php
function bubbleSort(array $arr): array
{
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = 0; $j < $len - 1 - $i; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                // 交換
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $tmp;
            }
        }
    }
    return $arr;
}

// 測試
$data = [5, 1, 4, 7, 2, 8, 3];
echo "排序前：" . implode(', ', $data) . "<br>";
$sorted = bubbleSort($data);
echo "排序後：" . implode(', ', $sorted);

執行過程逐步演示

以 [5, 1, 4, 7] 為例：

共需 n-1 輪，每輪比較次數遞減，最終完成排序。

優化版：加入「已排序旗標」

若某輪遍歷完全無交換，代表陣列已有序，可提前結束。

function bubbleSortOptimized(array $arr): array
{
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        $swapped = false;
        for ($j = 0; $j < $len - 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;
}

進階優化：記錄最後交換位置

下一輪只需比較到上輪最後交換的位置，進一步減少比較次數。

function bubbleSortAdvanced(array $arr): array
{
    $len = count($arr);
    $lastSwap = $len - 1;
    for ($i = 0; $i < $len - 1; $i++) {
        $swapped = false;
        $newLastSwap = 0;
        for ($j = 0; $j < $lastSwap; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
                $swapped = true;
                $newLastSwap = $j;
            }
        }
        $lastSwap = $newLastSwap;
        if (!$swapped) break;
    }
    return $arr;
}

複雜度分析

實務建議

• 教學/面試：必須手寫基本版與優化版，理解雙層迴圈邊界條件。
• 實際專案：絕不使用冒泡排序。PHP 內建 sort()、usort() 採用 QuickSort/MergeSort 混合演算法（Timsort），效能極佳且穩定。
• sort($arr); // 索引重排
• asort($arr); // 保持鍵值關聯
• usort($arr, fn($a, $b) => $a <=> $b); // 自訂比較（太空船運算子 PHP 7+）

總結

冒泡排序雖簡單直觀，但 O(n²) 複雜度使其僅適合極小資料量（< 50 筆）或教學場合。掌握其優化思路（旗標、縮小邊界）有助於理解演算法改進的通用模式。實務開發請直接使用語言內建排序函式。