PHP 經典排序算法完整實現：冒泡、快速、選擇、插入、交換排序

算法複雜度速覽

完整代碼實現（含類型提示與註釋）

<?php
declare(strict_types=1);

/** 冒泡排序：相鄰比較，大元素沉底 */
function bubbleSort(array $arr): array {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $swapped = false;
        for ($j = $n - 1; $j >= $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;
}

/** 交換排序：選擇最小值與當前位置交換 */
function exchangeSort(array $arr): array {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$j] < $arr[$i]) {
                [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
            }
        }
    }
    return $arr;
}

/** 選擇排序：每輪找最小值索引，最後交換 */
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;
}

/** 插入排序：構建有序區，新元素插入合適位置 */
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;
}

/** 快速排序：分治法，基準值分區遞歸 */
function quickSort(array $arr): array {
    $n = count($arr);
    if ($n <= 1) return $arr;
    
    $pivot = $arr[0];
    $left = $right = [];
    
    for ($i = 1; $i < $n; $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

/** PHP 內置排序對比 */
function builtinSort(array $arr): array {
    sort($arr, SORT_NUMERIC); // 修改原數組
    return $arr;
}

// 測試
$data = [64, 34, 25, 12, 22, 11, 90];
echo '原始: ' . implode(', ', $data) . "\n";
echo '冒泡: ' . implode(', ', bubbleSort($data)) . "\n";
echo '快速: ' . implode(', ', quickSort($data)) . "\n";
echo '內置: ' . implode(', ', builtinSort($data)) . "\n";
?>

性能基準測試（10,000 隨機整數）

<?php
function benchmark(callable $fn, array $data): float {
    $start = microtime(true);
    $fn($data);
    return microtime(true) - $start;
}

$data = array_map(fn() => mt_rand(1, 100000), range(1, 10000));

$algos = [
    'bubbleSort'    => 'bubbleSort',
    'exchangeSort'  => 'exchangeSort',
    'selectionSort' => 'selectionSort',
    'insertionSort' => 'insertionSort',
    'quickSort'     => 'quickSort',
    'builtin sort()'=> 'builtinSort',
];

foreach ($algos as $name => $fn) {
    $time = benchmark($fn, $data);
    printf("%-18s: %.4f 秒\n", $name, $time);
}

/* 典型輸出：
bubbleSort        : 2.1543 秒
exchangeSort      : 1.8921 秒
selectionSort     : 0.9876 秒
insertionSort     : 0.8765 秒
quickSort         : 0.0123 秒
builtin sort()    : 0.0011 秒
*/
?>

實戰選擇指南

• 數據量 < 50：插入排序（小數組常數因子小）
• 近乎有序數據：插入排序（接近 O(n)）
• 通用大數據：直接用內置 sort()（C 實現的 QuickSort + 優化）
• 教學/面試：掌握快速排序分區邏輯與遞歸邊界
• 穩定性要求：冒泡/插入/內置 usort + 索引輔助

進階：自定義比較器排序

<?php
$users = [
    ['name' => 'Alice', 'age' => 28],
    ['name' => 'Bob',   'age' => 22],
    ['name' => 'Carol', 'age' => 30],
];

// 年齡升序
usort($users, fn($a, $b) => $a['age'] <=> $b['age']);

// 複合排序：年齡升序，同齡按名字降序
usort($users, fn($a, $b) => 
    ($a['age'] <=> $b['age']) ?: 
    ($b['name'] <=> $a['name'])
);
?>

實際開發中 99% 場景直接使用內置排序函數，理解算法原理是為了面試與極端場景優化。