PHP 經典排序演算法與二分搜尋實作：合併、快速、氣泡、插入、選擇排序完整程式碼解析

前言：為什麼 PHP 開發者也要精通演算法？

雖然 PHP 內建 sort()、usort() 等高效排序函式，但理解經典演算法邏輯有助於：面試準備、效能調優時選擇正確策略、處理特殊資料結構（如大量資料外部排序、自訂比較規則）。本文提供五大排序法與二分搜尋的 PHP 實作，附註解與複雜度分析。

1. 合併排序 —— 穩定 O(n log n) 的分治典範

核心思想

• 自下而上：相鄰長度 1 子陣列合併 → 長度 2 → 長度 4 … 直到整體有序。
• 自上而下（遞迴）：分解 → 遞迴排序子區間 → 合併兩有序區間。

PHP 實作（自上而下）

/** 合併兩有序區間 [start..mid] 和 [mid+1..end] */
function merge(array &$arr, int $start, int $mid, int $end): void {
    $i = $start; $j = $mid + 1; $k = 0;
    $tmp = [];

    while ($i <= $mid && $j <= $end) {
        $tmp[$k++] = ($arr[$i] <= $arr[$j]) ? $arr[$i++] : $arr[$j++];
    }
    while ($i <= $mid) $tmp[$k++] = $arr[$i++];
    while ($j <= $end)   $tmp[$k++] = $arr[$j++];

    for ($i = 0; $i < $k; ++$i) $arr[$start + $i] = $tmp[$i];
}

/** 合併排序遞迴入口 */
function merge_sort(array &$arr, int $start = 0, int $end = 0): void {
    $len = count($arr);
    if ($len <= 1 || $start >= $end) return;
    $mid = intval(($start + $end) / 2);
    merge_sort($arr, $start, $mid);
    merge_sort($arr, $mid + 1, $end);
    merge($arr, $start, $mid, $end);
}

特性：穩定排序、固定 O(n log n)、需 O(n) 額外空間、適合連結串列與外部排序。

2. 快速排序 —— 平均 O(n log n) 的實戰首選

核心思想

選取基準值，將陣列分割為「小於基準」與「大於基準」兩部分，遞迴處理。原地排序，空間僅 O(log n) 遞迴堆疊。

PHP 實作（函數式風格，易讀但非原地）

function quick_sort(array $arr): array {
    $len = count($arr);
    if ($len <= 1) return $arr;

    $pivot = $arr[0];
    $left = $right = [];

    for ($i = 1; $i < $len; ++$i) {
        if ($arr[$i] <= $pivot) $left[] = $arr[$i];
        else $right[] = $arr[$i];
    }

    return array_merge(quick_sort($left), [$pivot], quick_sort($right));
}

注意：已排序資料會退化為 O(n²)，實務常用「三數取中」或隨機基準值優化。PHP 內建 sort() 採用 QuickSort 變體（Introsort）避免最壞情況。

3. 氣泡排序 —— 教學用 O(n²) 簡單直觀

function bubble_sort(array $arr): array {
    $len = count($arr);
    for ($i = 0; $i < $len; ++$i) {
        for ($j = $len - 1; $j > $i; --$j) {
            if ($arr[$j] < $arr[$j - 1]) {
                [$arr[$j], $arr[$j - 1]] = [$arr[$j - 1], $arr[$j]]; // PHP 7.1+ 解構賦值交換
            }
        }
    }
    return $arr;
}

優化點：若某輪無交換提前結束，最好情況（已有序）達 O(n)。

4. 插入排序 —— 小資料量、近乎有序資料的最佳選擇

function insert_sort(array $arr): array {
    $len = count($arr);
    for ($i = 1; $i < $len; ++$i) {
        $tmp = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $arr[$j] > $tmp) {
            $arr[$j + 1] = $arr[$j];
            --$j;
        }
        $arr[$j + 1] = $tmp;
    }
    return $arr;
}

適用場景：資料量 < 1000、線上演算法（串流資料逐筆插入）、混合演算法（如 Timsort）的基礎單元。

5. 選擇排序 —— 不穩定但交換次數最少 O(n²)

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

特性：交換次數固定 N-1 次，適合寫入成本高的儲存介質（如 EEPROM）。

6. 二分搜尋 —— 有序陣列 O(log n) 定位關鍵字

function bin_search(array $arr, int $key): int {
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        $mid = intval(($low + $high) / 2);
        if ($arr[$mid] == $key) return $mid;
        if ($arr[$mid] > $key) $high = $mid - 1;
        else $low = $mid + 1;
    }
    return -1; // 未找到
}

// 測試
$arr = [1, 2, 4, 6, 10, 40, 50, 80, 100, 110];
echo bin_search($arr, 80); // 輸出 7（0-based 索引）

前提：陣列必須已排序。PHP 可用 array_search（線性 O(n)）或自行排序後二分搜尋。

複雜度總結表

實務建議

• 生產環境優先使用內建 sort()/usort()（C 實作、Introsort 混合演算法、高度優化）。
• 自訂比較邏輯時傳入 usort($arr, fn($a,$b) => $a <=> $b)（PHP 7+ 太空船運算子）。
• 超大資料量（超過記憶體）採用外部合併排序（分塊排序寫檔、多路歸併）。
• 二分搜尋可用 array_bsearch（PECL）或自行實作；搭配 SplFixedArray 可提升記憶體效率。