前言

排序演算法是程式設計基礎核心。雖然 PHP 內建 `sort()`、`usort()` 高度優化，但理解經典演算法原理對於面試、教學與特定場景優化仍有價值。本文實作四大經典排序並分析複雜度。

複雜度快速比較

演算法	平均時間	最壞時間	空間	穩定性	備註
插入排序	O(n²)	O(n²)	O(1)	✅ 穩定	小資料/近乎有序最快
選擇排序	O(n²)	O(n²)	O(1)	❌ 不穩定	交換次數最少 O(n)
氣泡排序	O(n²)	O(n²)	O(1)	✅ 穩定	教學用，實務極少用
快速排序	O(n log n)	O(n²)	O(log n)	❌ 不穩定	大資料首選，PHP 內建採用變體

1. 插入排序

如同整理撲克牌，將未排序元素插入已排序區間正確位置。

<?php
function insertionSort(array &$arr): void {
    $count = count($arr);
    
    for ($i = 1; $i < $count; $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        
        // 將大於 key 的元素向右移動
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
}

// 測試
$data = [64, 34, 25, 12, 22, 11, 90];
insertionSort($data);
print_r($data); // [11, 12, 22, 25, 34, 64, 90]
?>

優化：二分搜尋插入位置

<?php
function binaryInsertionSort(array &$arr): void {
    $count = count($arr);
    
    for ($i = 1; $i < $count; $i++) {
        $key = $arr[$i];
        $left = 0;
        $right = $i - 1;
        
        // 二分搜尋插入位置
        while ($left <= $right) {
            $mid = (int)(($left + $right) / 2);
            if ($arr[$mid] > $key) {
                $right = $mid - 1;
            } else {
                $left = $mid + 1;
            }
        }
        
        // 移動元素
        for ($j = $i - 1; $j >= $left; $j--) {
            $arr[$j + 1] = $arr[$j];
        }
        $arr[$left] = $key;
    }
}
?>

2. 選擇排序

每輪從未排序區找最小值，放到已排序區末尾。

<?php
function selectionSort(array &$arr): void {
    $count = count($arr);
    
    for ($i = 0; $i < $count - 1; $i++) {
        $minIdx = $i;
        
        for ($j = $i + 1; $j < $count; $j++) {
            if ($arr[$j] < $arr[$minIdx]) {
                $minIdx = $j;
            }
        }
        
        if ($minIdx !== $i) {
            [$arr[$i], $arr[$minIdx]] = [$arr[$minIdx], $arr[$i]]; // PHP 7.1+ 解構賦值
        }
    }
}
?>

3. 氣泡排序

相鄰元素兩兩比較，大的「浮」到右邊。可加入優化旗標提早結束。

<?php
function bubbleSort(array &$arr): void {
    $count = count($arr);
    
    for ($i = 0; $i < $count - 1; $i++) {
        $swapped = false;
        
        for ($j = 0; $j < $count - 1 - $i; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
                $swapped = true;
            }
        }
        
        // 本輪無交換，代表已排序完成
        if (!$swapped) break;
    }
}
?>

4. 快速排序

分治法：選基準值，分割為「小於」與「大於」兩子陣列，遞迴排序。

基礎版（非原地、易理解）

<?php
function quickSortBasic(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(quickSortBasic($left), [$pivot], quickSortBasic($right));
}
?>

原地版（In-place，記憶體效率佳）

<?php
function quickSortInPlace(array &$arr, int $low = 0, int $high = null): void {
    if ($high === null) $high = count($arr) - 1;
    if ($low >= $high) return;
    
    $pivotIndex = partition($arr, $low, $high);
    quickSortInPlace($arr, $low, $pivotIndex - 1);
    quickSortInPlace($arr, $pivotIndex + 1, $high);
}

function partition(array &$arr, int $low, int $high): int {
    // 隨機選擇基準值，避免最壞情況
    $randIdx = random_int($low, $high);
    [$arr[$randIdx], $arr[$high]] = [$arr[$high], $arr[$randIdx]];
    
    $pivot = $arr[$high];
    $i = $low - 1;
    
    for ($j = $low; $j < $high; $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;
}
?>

PHP 內建排序 vs 手寫演算法

<?php
$data = range(1, 10000);
shuffle($data);

// 內建 sort() - C 實作，高度優化
$start = microtime(true);
$copy = $data;
sort($copy);
echo "sort(): " . (microtime(true) - $start) * 1000 . " ms\n";

// 手寫快速排序
$start = microtime(true);
$copy = $data;
quickSortInPlace($copy);
echo "quickSortInPlace(): " . (microtime(true) - $start) * 1000 . " ms\n";

// 通常內建快 10-50 倍
?>

自定比較：usort() 實用範例

<?php
$users = [
    ['name' => 'Alice', 'age' => 25, 'score' => 85],
    ['name' => 'Bob', 'age' => 30, 'score' => 92],
    ['name' => 'Charlie', 'age' => 22, 'score' => 78],
];

// 多欄位排序：分數降序，年齡升序
usort($users, function($a, $b) {
    if ($a['score'] !== $b['score']) {
        return $b['score'] <=> $a['score']; // 太空船運算子 PHP 7+
    }
    return $a['age'] <=> $b['age'];
});

print_r($users);
?>

何時使用手寫排序？

• 教學/面試展示演算法理解
• 特殊資料結構（鏈表、外部排序）
• 需要完整控制比較邏輯且無法用 `usort()` 表達
• 嵌入式/受限環境無標準庫

生產環境建議

永遠優先使用 PHP 內建排序函式（`sort()`、`usort()`、`ksort()` 等）。它們基於 C 實作的混合排序（Timsort/QuickSort 混合），經過大量優化、測試且處理邊界情況完善。手寫排序僅供學習參考。