PHP 排序演算法完整實作：冒泡、插入、選擇、快速排序

掌握經典排序演算法是程式設計基礎。本文提供 PHP 實作的四大排序法，含時間複雜度分析與適用場景說明。

1. 冒泡排序

時間複雜度：O(n²) | 穩定排序 | 適合小資料量教學

function bubbleSort(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]];
            }
        }
    }
    return $arr;
}

2. 插入排序

時間複雜度：O(n²) | 穩定 | 近乎有序資料表現佳（接近 O(n)）

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

3. 選擇排序

時間複雜度：O(n²) | 不穩定 | 交換次數最少（O(n)）

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

4. 快速排序

時間複雜度：平均 O(n log n) | 不穩定 | 實務最常用

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

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

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

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

測試與驗證

$test = [43, 154, 3, 78, 13, 284, 167, 2, 56, 2234, 121, 57, 345];
var_dump(quickSort($test));
// 輸出: [2, 3, 13, 43, 56, 57, 78, 121, 154, 167, 284, 345, 2234]

效能比較與選擇建議

實務建議

生產環境直接使用 PHP 內建 sort() / usort()（底層為 QuickSort 改良版），僅在面試、教學或特殊需求時手寫演算法。