您现在的位置：程式碼之家 >> 編程語言 > >> 網頁程式設計 >> PHP 程式設計 >> PHP 相關知識

PHP 冒泡排序演算法實作與優化變體完整教學

編輯：PHP 相關知識

前言

冒泡排序是最基礎的排序演算法之一，雖然時間複雜度 O(n²) 不適合大量資料，但其原理直觀、程式碼簡潔，是演算法入門必學，且在「資料量小」、「近乎有序」、「教學示範」場景仍有實用價值。本文提供標準版、優化版、雙向冒泡（雞尾酒排序）、遞迴版等多種實作，並分析效能特徵。

核心原理

重複遍歷陣列，比較相鄰元素，順序錯誤則交換
每輪遍歷將最大（或最小）元素「冒泡」到末端
第 i 輪結束後，後 i 個元素已確定為最大值，無需再比較
若某輪未發生任何交換，代表已有序，可提前結束

1. 標準版冒泡排序

<?php

/**
 * 冒泡排序（標準版，由小到大）
 * @param array $arr 參考傳遞，直接修改原陣列
 * @return void
 */
function bubbleSort(array &$arr): void
{
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        // 最後 i 個元素已排好序，無需比較
        for ($j = 0; $j < $n - 1 - $i; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                // 交換
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
                // 或傳統寫法：
                // $tmp = $arr[$j];
                // $arr[$j] = $arr[$j + 1];
                // $arr[$j + 1] = $tmp;
            }
        }
    }
}

// 測試
$data = [64, 34, 25, 12, 22, 11, 90];
bubbleSort($data);
echo "Sorted: " . implode(', ', $data) . "\n";
// Output: 11, 12, 22, 25, 34, 64, 90

2. 優化版：提前結束旗標

若某輪遍歷完全沒有交換，說明陣列已有序，直接跳出。

function bubbleSortOptimized(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]];
                $swapped = true;
            }
        }
        // 本輪無交換，已有序
        if (!$swapped) break;
    }
}

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

最後一次交換的位置之後的元素必然已有序，下一輪只需遍歷到該位置。

function bubbleSortLastSwap(array &$arr): void
{
    $n = count($arr);
    $lastSwap = $n - 1;
    
    while ($lastSwap > 0) {
        $currentLastSwap = 0;
        for ($j = 0; $j < $lastSwap; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
                $currentLastSwap = $j;
            }
        }
        $lastSwap = $currentLastSwap;
    }
}

4. 雙向冒泡排序（雞尾酒排序 / Cocktail Shaker Sort）

奇數輪從左向右冒泡最大值，偶數輪從右向左冒泡最小值，減少「烏龜」（小數值在右側需一步步移動到左邊）的移動次數。

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

5. 遞迴版冒泡排序（教學用）

function bubbleSortRecursive(array &$arr, int $n = null): void
{
    $n ??= count($arr);
    // 基礎情況
    if ($n <= 1) return;
    
    // 一輪冒泡，將最大值移到索引 n-1
    for ($i = 0; $i < $n - 1; $i++) {
        if ($arr[$i] > $arr[$i + 1]) {
            [$arr[$i], $arr[$i + 1]] = [$arr[$i + 1], $arr[$i]];
        }
    }
    
    // 遞迴處理前 n-1 個元素
    bubbleSortRecursive($arr, $n - 1);
}

6. 泛型比較器版本（支援自定義排序邏輯）

/**
 * 通用冒泡排序
 * @param array $arr
 * @param callable $cmp 比較函式：回傳 true 表示 $a 應在 $b 之前
 */
function bubbleSortGeneric(array &$arr, callable $cmp): void
{
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $swapped = false;
        for ($j = 0; $j < $n - 1 - $i; $j++) {
            // $cmp($a, $b) == true 表示順序正確，false 表示需交換
            if (!$cmp($arr[$j], $arr[$j + 1])) {
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
                $swapped = true;
            }
        }
        if (!$swapped) break;
    }
}

// 使用範例
$users = [
    ['name' => 'Alice', 'age' => 28],
    ['name' => 'Bob', 'age' => 22],
    ['name' => 'Charlie', 'age' => 35],
];

// 依年齡升序
bubbleSortGeneric($users, fn($a, $b) => $a['age'] <= $b['age']);
// 依名稱長度降序
bubbleSortGeneric($users, fn($a, $b) => strlen($a['name']) >= strlen($b['name']));

效能分析與比較

變體	最好情況	平均情況	最壞情況	空間複雜度	穩定性	適用場景
標準版	O(n²)	O(n²)	O(n²)	O(1)	穩定	教學、極小資料
優化版 (flag)	O(n)	O(n²)	O(n²)	O(1)	穩定	近乎有序資料
記錄最後交換	O(n)	O(n²)	O(n²)	O(1)	穩定	部分有序資料
雞尾酒排序	O(n)	O(n²)	O(n²)	O(1)	穩定	雙向移動需求
PHP sort()	O(n log n)	O(n log n)	O(n log n)	O(log n)	不穩定	生產環境通用

實測效能對比（10,000 筆隨機整數）

<?php
function benchmark(string $name, callable $sort, array $data): void
{
    $copy = $data;
    $start = microtime(true);
    $sort($copy);
    $elapsed = (microtime(true) - $start) * 1000;
    echo sprintf("%-25s: %8.2f ms\n", $name, $elapsed);
}

$data = range(1, 10000);
shuffle($data);

benchmark('bubbleSort', 'bubbleSort', $data);           // ~1200 ms
benchmark('bubbleSortOptimized', 'bubbleSortOptimized', $data); // ~1100 ms
benchmark('bubbleSortLastSwap', 'bubbleSortLastSwap', $data);   // ~900 ms
benchmark('cocktailSort', 'cocktailSort', $data);       // ~850 ms
benchmark('PHP sort()', 'sort', $data);                 // ~2 ms  (!)

// 結論：PHP 內建 sort() (QuickSort/HeapSort 混合) 快 500 倍以上

何時在生產環境使用冒泡排序？

資料量極小（< 50 筆）：常數因子低，反而比 QuickSort 快。
近乎有序資料：優化版最好情況 O(n)，適合「即時排行榜」每次新增一筆重排。
記憶體極度受限：O(1) 原地排序，無遞迴堆疊開銷。
教學/面試/測試：展示演算法思維。

最佳實踐建議

<?php
// 實際專案：永遠優先使用內建函式
// 1. 索引陣列排序
sort($arr);           // 升序，重建索引
rsort($arr);          // 降序

// 2. 關聯陣列保持鍵值
asort($arr);          // 值升序
arsort($arr);         // 值降序
ksort($arr);          // 鍵升序
krsort($arr);         // 鍵降序

// 3. 自定義比較
usort($arr, fn($a, $b) => $a['score'] <=> $b['score']); // PHP 7+ 太空船運算子
uasort($arr, ...);    // 保持鍵值
uksort($arr, ...);    // 依鍵排序

// 4. 多欄位排序
array_multisort(
    array_column($users, 'age'), SORT_ASC,
    array_column($users, 'name'), SORT_DESC,
    $users
);

冒泡排序是演算法世界的「Hello World」，理解其運作機制、優化思路、變體設計，能建立扎實的演算法直覺。但記住：生產環境請直接使用 PHP 內建排序函式，它們經過 C 層優化、處理邊界情況、支援多種排序模式，是效能與可靠性的最佳選擇。