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

測試資料

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

1. 氣泡排序

原理：相鄰元素兩兩比較，大的「冒」到右邊，每輪確定一個最大值。

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

• 時間複雜度：O(n²)
• 空間複雜度：O(1)
• 穩定排序

2. 選擇排序

原理：每輪在未排序區間找最小值，與區間首位交換。

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)
• 不穩定排序

3. 插入排序

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

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

• 時間複雜度：O(n²)（最佳 O(n)，近乎有序時極快）
• 空間複雜度：O(1)
• 穩定排序、原地排序、線上演算法

4. 快速排序

原理：分治法，選基準值，小的放左、大的放右，遞迴處理子陣列。

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

• 時間複雜度：平均 O(n log n)，最差 O(n²)（已有序時）
• 空間複雜度：O(log n) 遞迴堆疊
• 不穩定排序
• 優化：隨機選基準、三數取中、小陣列改插入排序

效能比較（10,000 筆隨機整數）

實務建議

1. 生產代碼一律使用 sort() / rsort() / usort() / asort() 等內建函數，經過高度優化、穩定可靠。
2. 教學/面試/特殊約束（如不能用內建、需穩定且 O(n log n)）才手寫演算法。
3. 若需在 PHP 實作高效排序，可考慮 nimble 擴充或改用 FFI 呼叫 C 庫。