PHP 經典排序算法實現：選擇、冒泡、插入排序代碼詳解

算法複雜度對比

1. 選擇排序

邏輯： 每輪從未排序區選出最小(大)元素，與未排序區首位交換。

<?php
function selectionSort(array &$arr, string $order = 'asc'): void {
    $n = count($arr);
    $cmp = $order === 'asc' 
        ? fn($a, $b) => $a > $b  // 升序：前>後則交換
        : fn($a, $b) => $a < $b; // 降序：前<後則交換

    for ($i = 0; $i < $n - 1; $i++) {
        $extremeIdx = $i; // 假設當前是極值
        // 在未排序區尋找真正極值
        for ($j = $i + 1; $j < $n; $j++) {
            if ($cmp($arr[$extremeIdx], $arr[$j])) {
                $extremeIdx = $j;
            }
        }
        // 交換
        if ($extremeIdx !== $i) {
            [$arr[$i], $arr[$extremeIdx]] = [$arr[$extremeIdx], $arr[$i]]; // PHP 7.1+ 解構賦值
        }
    }
}

// 測試
$data = [21.5, 33, 90, 7, -4, 5, 55, 11];
selectionSort($data, 'asc');
print_r($data); // [-4, 5, 7, 11, 21.5, 33, 55, 90]

2. 冒泡排序

邏輯： 相鄰元素兩兩比較，大者「冒泡」到右側。每輪將最大值推到末尾。

<?php
function bubbleSort(array &$arr, string $order = 'asc'): void {
    $n = count($arr);
    $cmp = $order === 'asc' 
        ? fn($a, $b) => $a > $b 
        : fn($a, $b) => $a < $b;

    for ($i = 0; $i < $n - 1; $i++) {
        $swapped = false; // 優化：若本輪無交換，說明已有序
        // 最後 i 個已歸位，無需比較
        for ($j = 0; $j < $n - 1 - $i; $j++) {
            if ($cmp($arr[$j], $arr[$j + 1])) {
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
                $swapped = true;
            }
        }
        if (!$swapped) break; // 提前結束
    }
}

// 測試
$data = [101, 101, -9, -8, 0, 76, 1, 57, 43, 90, 23, -56];
bubbleSort($data, 'asc');
print_r($data); // [-56, -9, -8, 0, 1, 23, 43, 57, 76, 90, 101, 101]

3. 插入排序

邏輯： 將未排序區元素逐個「插入」到已排序區的適當位置，類似整理撲克牌。

<?php
function insertionSort(array &$arr, string $order = 'asc'): void {
    $n = count($arr);
    $cmp = $order === 'asc' 
        ? fn($a, $b) => $a > $b  // 升序：已排序區元素 > 待插入元素，則後移
        : fn($a, $b) => $a < $b;

    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i]; // 待插入元素
        $j = $i - 1;
        // 在已排序區 [0...i-1] 從右向左掃描，騰出位置
        while ($j >= 0 && $cmp($arr[$j], $key)) {
            $arr[$j + 1] = $arr[$j]; // 後移
            $j--;
        }
        $arr[$j + 1] = $key; // 插入
    }
}

// 測試
$data = [4, 7, 0, -7, 1, 14, 5];
insertionSort($data, 'desc'); // 降序
print_r($data); // [14, 7, 5, 4, 1, 0, -7]

PHP 內建排序函數實戰 (生產環境標準)

基本排序

$arr = [3, 1, 4, 1, 5, 9, 2, 6];
sort($arr);          // 升序，重建索引
rsort($arr);         // 降序，重建索引
asort($arr);         // 升序，保持鍵值關聯
arsort($arr);        // 降序，保持鍵值關聯
ksort($arr);         // 按鍵名升序
krsort($arr);        // 按鍵名降序

自定義比較 usort / uasort / uksort

$users = [
    ['name' => 'Alice', 'age' => 25, 'score' => 88],
    ['name' => 'Bob', 'age' => 30, 'score' => 92],
    ['name' => 'Charlie', 'age' => 25, 'score' => 95],
];

// 多字段排序：年齡升序，年齡相同則分數降序
usort($users, function($a, $b) {
    if ($a['age'] !== $b['age']) {
        return $a['age'] <=> $b['age']; // PHP 7+ 太空船操作符
    }
    return $b['score'] <=> $a['score']; // 分數降序
});
/*
結果:
Charlie (25, 95)
Alice   (25, 88)
Bob     (30, 92)
*/

多維數組多鍵排序 array_multisort

$data = [
    ['id' => 1, 'category' => 'A', 'price' => 100],
    ['id' => 2, 'category' => 'B', 'price' => 50],
    ['id' => 3, 'category' => 'A', 'price' => 200],
];

// 提取排序列
$categories = array_column($data, 'category');
$prices = array_column($data, 'price');

// category 升序 (A 在前), price 降序 (高價在前)
array_multisort($categories, SORT_ASC, $prices, SORT_DESC, $data);
/*
結果:
id=1 (A, 100)
id=3 (A, 200)  ← 同分類下價格高在前
id=2 (B, 50)
*/

總結

• 教學/面試： 掌握選擇、冒泡、插入的邏輯差異、穩定性、優化點 (冒泡提前結束、插入排序二分查找插入位)。
• 實際開發： 100% 使用內建函數。usort + 太空船操作符 <=> 處理 99% 複雜排序需求。
• 大數據排序： 超過內存限制時，使用外部排序 (分片排序 + 歸併) 或數據庫 ORDER BY。