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

前言

雖然 PHP 內建 `sort()`、`usort()` 高效且好用，但理解經典排序演算法有助於面試、教學與特殊場景優化。本文提供四大經典排序的 PHP 實作、時間複雜度分析與適用情境。

1. 插入排序

適合小規模或近乎有序資料，穩定排序。

function insertionSort(array $arr): array {
    $n = count($arr);
    for ($i = 1; $i < $n; $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)
• 穩定性：穩定

2. 選擇排序

每輪選出最小值交換到正確位置，交換次數少 (O(n))。

function selectionSort(array $arr): array {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $minIdx = $i;
        for ($j = $i + 1; $j < $n; $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 bubbleSort(array $arr): array {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $swapped = false;
        for ($j = 0; $j < $n - 1 - $i; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
                $swapped = true;
            }
        }
        if (!$swapped) break; // 提前結束優化
    }
    return $arr;
}

• 時間複雜度：最好 O(n)、平均/最差 O(n²)
• 空間複雜度：O(1)
• 穩定性：穩定

4. 快速排序

分治法，選基準值分區遞迴，平均效能最佳。

function quickSort(array $arr): array {
    if (count($arr) <= 1) return $arr;
    $pivot = $arr[0];
    $left = $right = [];
    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] <= $pivot) $left[] = $arr[$i];
        else $right[] = $arr[$i];
    }
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

// 原地分區版本 (空間 O(log n))
function quickSortInPlace(array &$arr, int $low, int $high): void {
    if ($low < $high) {
        $pi = partition($arr, $low, $high);
        quickSortInPlace($arr, $low, $pi - 1);
        quickSortInPlace($arr, $pi + 1, $high);
    }
}
function partition(array &$arr, int $low, int $high): int {
    $pivot = $arr[$high];
    $i = $low - 1;
    for ($j = $low; $j <= $high - 1; $j++) {
        if ($arr[$j] <= $pivot) {
            $i++;
            [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
        }
    }
    [$arr[$i + 1], $arr[$high]] = [$arr[$high], $arr[$i + 1]];
    return $i + 1;
}

• 時間複雜度：平均 O(n log n)、最差 O(n²) (已排序陣列)
• 空間複雜度：O(log n) 遞迴堆疊
• 穩定性：不穩定

效能實測 (10,000 筆隨機整數)

實務建議

1. 生產環境永遠使用內建 `sort()`/`usort()`/`asort()`：C 底層實作、高度優化、支援自訂比較函數
2. 教學/面試/特殊約束 (記憶體極限、串流排序) 才手寫演算法
3. 大量資料排序考慮：外部排序、資料庫 `ORDER BY`、分散式排序
4. PHP 8.1+ 新增 `array_is_list()`、`array_find()` 等輔助函數