PHP 常見排序算法實現總結（插入、選擇、冒泡、快速、鍵值排序）

算法複雜度對比

代碼實現（均為升序）

1. 插入排序

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

2. 選擇排序

function selectSort(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;
}

3. 冒泡排序

function bubbleSort(array $arr): array {
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        $swapped = false;
        for ($j = 0; $j < $len - 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;
}

4. 快速排序

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

5. 保持鍵值關係的值排序（冒泡實現）

function sortByVal(array $arr, string $order = 'asc'): array {
    $keys = array_keys($arr);
    $vals = array_values($arr);
    $len = count($vals);
    $keyMap = range(0, $len - 1);

    for ($i = 0; $i < $len; $i++) {
        for ($j = $len - 1; $j > $i; $j--) {
            $cond = $order === 'asc' ? $vals[$j] < $vals[$j-1] : $vals[$j] > $vals[$j-1];
            if ($cond) {
                [$vals[$j], $vals[$j-1]] = [$vals[$j-1], $vals[$j]];
                [$keyMap[$j], $keyMap[$j-1]] = [$keyMap[$j-1], $keyMap[$j]];
            }
        }
    }
    return array_combine(array_map(fn($i) => $keys[$i], $keyMap), $vals);
}

6. 內建函數版（推薦生產環境）

function arraySortByVal(array $arr, string $key, string $order = 'asc'): array {
    $valMap = array_column($arr, $key);
    $order === 'asc' ? asort($valMap) : arsort($valMap);
    return array_replace(array_flip($valMap), $arr); // 保持原鍵順序
}

選型建議

• 數據量 < 50：插入/冒泡/選擇均可，代碼簡單。
• 數據量 > 1000：必須用快速排序或內建 sort()/usort()。
• 需保持鍵值關係：用 asort()/arsort() 或 uasort()。
• 超大數據量：下推到 MySQL ORDER BY，利用索引排序。