PHP 四大基礎排序演算法實作：氣泡、選擇、插入、快速排序

演算法是程式的核心。雖然 PHP 內建 sort() 等函數效能極佳，但理解經典排序演算法邏輯有助於面試與邏輯思維訓練。本文以相同輸入陣列，分別實作四種基礎排序法。

測試資料

$arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39];

1. 氣泡排序

概念：兩兩比較相鄰元素，較大者「浮」至右側，每輪確定一個最大值。

function bubbleSort($arr) {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        for ($k = 0; $k < $len - $i; $k++) {
            if ($arr[$k] > $arr[$k+1]) {
                $tmp = $arr[$k+1];
                $arr[$k+1] = $arr[$k];
                $arr[$k] = $tmp;
            }
        }
    }
    return $arr;
}

時間複雜度：O(n²)，穩定排序。

2. 選擇排序

概念：每輪從未排序區間找出最小值，放到已排序區間末尾。

function selectionSort($arr) {
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        $p = $i; // 假設最小值索引
        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$p] > $arr[$j]) {
                $p = $j;
            }
        }
        if ($p != $i) {
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }
    return $arr;
}

時間複雜度：O(n²)，不穩定排序。

3. 插入排序

概念：將未排序元素插入已排序區間的適當位置，類似整理撲克牌。

function insertionSort($arr) {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $tmp = $arr[$i];
        for ($j = $i - 1; $j >= 0; $j--) {
            if ($tmp < $arr[$j]) {
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $tmp;
            } else {
                break; // 已找到插入位置
            }
        }
    }
    return $arr;
}

時間複雜度：O(n²)，最佳 O(n)（近乎有序時），穩定排序。

4. 快速排序

概念：分治法。選基準值，將陣列分為「小於基準」與「大於基準」兩子陣列，遞歸排序再合併。

function quickSort($arr) {
    $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(quickSort($left), [$pivot], quickSort($right));
}

時間複雜度：平均 O(n log n)，最差 O(n²)，不穩定排序。實務中 PHP 內建 sort() 採用 QuickSort 改良版（Zend Qsort）。

效能比較與建議

實務建議：生產環境直接使用 PHP 內建 sort()/usort()，效能經過高度優化（C 實作），並支援自定義比較函數。