PHP 陣列排序三大經典演算法實作教學

PHP 陣列排序三大經典演算法實作教學

雖然 PHP 內建 sort()、usort() 高效且穩定，但理解氣泡、選擇、插入三大基礎排序演算法，是演練邏輯思維、應對面試、處理特殊排序需求的核心功力。本文以 PHP 實作並逐步追蹤執行過程。

測試資料

$arr = [3, 5, -1, 0, 2];  // 目標：升序排列 [-1, 0, 2, 3, 5]

一、氣泡排序

核心思想： 相鄰元素兩兩比較，大者後移，每輪將最大值「氣泡」至末尾。

function bubbleSort(array $arr): array {
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        // 每輪減少一次比較，因為最後 $i 個已就位
        for ($j = 0; $j < $len - 1 - $i; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                // PHP 交換寫法
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
            }
        }
    }
    return $arr;
}

執行過程追蹤

初始: [3, 5, -1, 0, 2]

第1輪 (i=0, 確定第5位):
  j=0: 3<5 不換 → [3, 5, -1, 0, 2]
  j=1: 5>-1 換 → [3, -1, 5, 0, 2]
  j=2: 5>0  換 → [3, -1, 0, 5, 2]
  j=3: 5>2  換 → [3, -1, 0, 2, 5]  ← 最大值 5 就位

第2輪 (i=1, 確定第4位):
  j=0: 3>-1 換 → [-1, 3, 0, 2, 5]
  j=1: 3>0  換 → [-1, 0, 3, 2, 5]
  j=2: 3>2  換 → [-1, 0, 2, 3, 5]  ← 次大值 3 就位

第3輪 (i=2): [-1, 0, 2, 3, 5] (無交換，提前結束優化點)
第4輪 (i=3): 完成

結果: [-1, 0, 2, 3, 5]

複雜度與特性

• 時間：O(n²) 最好/平均/最差
• 空間：O(1) 原地排序
• 穩定性：穩定 (相等元素不交換順序)
• 優化：加入 $swapped 標記，無交換時提前跳出

二、選擇排序

核心思想： 每輪從未排序區選出最小值，與未排序區首位交換。

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;
}

執行過程追蹤

初始: [2, 1, -1, 3, 0]

第1輪 (i=0):
  假設最小=2 (索引0)
  j=1: 1<2  → 最小=1 (索引1)
  j=2: -1<1 → 最小=-1 (索引2)  ← 全域最小
  j=3: 3>-1 無變
  j=4: 0>-1 無變
  交換 索引0(-1) ↔ 索引2(2) → [-1, 1, 2, 3, 0]

第2輪 (i=1):
  未排序區: [1, 2, 3, 0]
  尋得最小=0 (索引4)
  交換 索引1(0) ↔ 索引4(1) → [-1, 0, 2, 3, 1]

第3輪 (i=2): 最小=1 (索引4) ↔ 索引2(2) → [-1, 0, 1, 3, 2]
第4輪 (i=3): 最小=2 (索引4) ↔ 索引3(3) → [-1, 0, 1, 2, 3]

結果: [-1, 0, 1, 2, 3]

複雜度與特性

• 時間：O(n²) 固定，無最好情況優化
• 空間：O(1)
• 穩定性：不穩定 (交換可能改變相等元素相對順序)
• 優勢：交換次數最少 (最多 n-1 次)，適合寫入成本高的存儲介質

三、插入排序

核心思想： 維護已排序前綴，將下一元素插入適當位置，如整理撲克牌。

function insertionSort(array $arr): array {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $insertVal = $arr[$i];      // 待插入值
        $insertIdx = $i - 1;        // 已排序區末尾索引
        
        // 從右向左掃描，大於待插入值的元素右移
        while ($insertIdx >= 0 && $insertVal < $arr[$insertIdx]) {
            $arr[$insertIdx + 1] = $arr[$insertIdx];
            $insertIdx--;
        }
        // 插入空出的位置
        $arr[$insertIdx + 1] = $insertVal;
    }
    return $arr;
}

執行過程追蹤

初始: [2, 1, -1, 3, 0]

i=1: 待插入=1
  已排序=[2] | 1<2 → 2右移 → [2, 2, -1, 3, 0]
  插入1 → [1, 2, -1, 3, 0]

i=2: 待插入=-1
  已排序=[1, 2] | -1<2 → 2右移 → [1, 2, 2, 3, 0]
           | -1<1 → 1右移 → [1, 1, 2, 3, 0]
  插入-1 → [-1, 1, 2, 3, 0]

i=3: 待插入=3
  已排序=[-1, 1, 2] | 3>2 → 無移動
  插入3 → [-1, 1, 2, 3, 0]

i=4: 待插入=0
  已排序=[-1, 1, 2, 3] | 0<3 → 3右移
                    | 0<2 → 2右移
                    | 0<1 → 1右移
                    | 0>-1 停止
  插入0 → [-1, 0, 1, 2, 3]

結果: [-1, 0, 1, 2, 3]

複雜度與特性

• 時間：O(n²) 平均/最差，**O(n) 最好** (已近乎有序時)
• 空間：O(1)
• 穩定性：穩定
• 優勢：適應性強、線上排序 (可邊讀取邊排序)、小規模/近乎有序資料極快

三大演算法對比總結

PHP 實戰建議

1. 生產代碼永遠使用內建函數： sort($arr) (C 實現的 QuickSort/合併排序混合，O(n log n))
2. 複雜排序用 usort()： usort($arr, fn($a,$b) => $a['age'] <=> $b['age'])
3. 多鍵值排序用 array_multisort()
4. 教學/面試/特殊約束 (如嵌入式無標準庫、需穩定排序且不可用額外空間) 才手寫演算法

理解經典排序演算法的機制、優缺點與適用場景，不僅能應對面試，更能在效能調優、異常排查時做出正確的直覺判斷。