PHP 實現經典排序算法：冒泡、希爾、選擇排序的代碼、複雜度與優化詳解

排序算法是計算機科學基石。本文提供三種經典排序的 PHP 實現，附帶時間複雜度分析、優化技巧與基準測試建議。

1. 冒泡排序 —— 入門教學首選

function bubbleSort(array $arr): array {
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        $swapped = false;
        // 內層每輪減少一個已排定的最大值
        for ($j = 0; $j < $len - $i - 1; $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;
}

• 時間複雜度：最好 O(n)（已有序），平均/最差 O(n²)
• 空間複雜度：O(1)
• 穩定性：穩定

2. 希爾排序 —— 插入排序的增量改進

function shellSort(array $arr): array {
    $len = count($arr);
    // 增量序列：Knuth 序列 (3^k - 1)/2 或簡單折半
    for ($gap = $len >> 1; $gap > 0; $gap >>= 1) {
        // 對每個分組進行插入排序
        for ($i = $gap; $i < $len; $i++) {
            $temp = $arr[$i];
            $j = $i;
            while ($j >= $gap && $arr[$j - $gap] > $temp) {
                $arr[$j] = $arr[$j - $gap];
                $j -= $gap;
            }
            $arr[$j] = $temp;
        }
    }
    return $arr;
}

• 時間複雜度：取決於增量序列，Knuth 序列 O(n^(3/2))，最好 O(n log n)
• 空間複雜度：O(1)
• 穩定性：不穩定

3. 選擇排序 —— 理論教學用

function selectionSort(array $arr): array {
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        $minIdx = $i;
        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$j] < $arr[$minIdx]) $minIdx = $j;
        }
        if ($minIdx !== $i) {
            [$arr[$i], $arr[$minIdx]] = [$arr[$minIdx], $arr[$i]];
        }
    }
    return $arr;
}

• 時間複雜度：恆定 O(n²)（無論數據分布）
• 空間複雜度：O(1)
• 穩定性：不穩定

基準測試代碼

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

$algos = ['bubbleSort', 'shellSort', 'selectionSort', 'sort']; // 內置 sort() 為 QuickSort 混合
foreach ($algos as $algo) {
    $copy = $data;
    $start = microtime(true);
    $algo($copy);
    $time = microtime(true) - $start;
    echo "$algo: ${time}s\n";
}

/* 典型輸出（機器相關）：
bubbleSort: 2.45s
selectionSort: 1.82s
shellSort: 0.012s
sort: 0.001s
*/

核心結論

進階：自定義比較器

// 多字段排序：先按 age 升序，再按 name 降序
usort($users, function($a, $b) {
    return [$a['age'], -strcmp($a['name'], $b['name'])] <=> [$b['age'], -strcmp($b['name'], $a['name'])];
}); // PHP 7+ 太空船操作符簡化多鍵比較

排序算法考試必考、面試必問、教學必講，但**生產代碼請直接用 sort()/usort()** —— 這是對 CPU 週期、開發時間、代碼可維護性的最大尊重。

1. 上一篇文章： PHP 可逆加密類實現：基於 XOR 與隨機密鑰流的對稱加密示例
2. 下一篇文章： PHP 單雙引號深度解析：性能、解析機制、轉義規則與最佳實踐

PHP 相關知識

PHP 圖片水印技術實戰：imagecopymerge 疊加、透明度控制、文字水印與批次處理

水印核心原理 水印本質是兩張圖片的像素級混合。PHP GD

PHP 字符串替換進階：sprintf + call_user_func_array 動態參數、str_replace 陣列映射替換與順序陷阱

PHP 字符串替換三板斧：sprintf 動態參數化、str

資深 PHP 開發者的編程心法：從需求理解到代碼質量的十大原則

我是如何編程的：十年實戰沉澱的核心思想 代碼世界變幻莫測，

PHP 微信支付開發完整實戰指南（基於 ThinkPHP 3.2）

PHP 微信支付開發完整實戰指南 本文詳細記錄了基於 Thi