PHP 排序算法實戰：冒泡排序與快速排序完整實現、性能對比與優化策略

排序是程序設計基礎操作。本文提供冒泡排序（教學用）與快速排序（實用級）的 PHP 完整實現、多種寫法對比、性能基準測試、優化技巧及內置函數最佳實踐。

冒泡排序

基本思想：重複遍歷數組，比較相鄰元素並交換，大元素像氣泡浮到末端。時間複雜度 O(n²)，僅適合教學或極小數據集（< 50）。

標準雙層循環

function bubbleSort( array $arr ): array {
    $len = count($arr);
    for ( $i = 1; $i < $len; $i++ ) {
        for ( $j = $len - 1; $j >= $i; $j-- ) {
            if ( $arr[$j] < $arr[$j-1] ) { // 升序
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j-1];
                $arr[$j-1] = $tmp;
            }
        }
    }
    return $arr;
}

優化版：提前終止標誌

function bubbleSortOptimized( array $arr ): array {
    $len = count($arr);
    for ( $i = 1; $i < $len; $i++ ) {
        $swapped = false;
        for ( $j = $len - 1; $j >= $i; $j-- ) {
            if ( $arr[$j] < $arr[$j-1] ) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j-1];
                $arr[$j-1] = $tmp;
                $swapped = true;
            }
        }
        if ( ! $swapped ) break; // 本輪無交換，已有序
    }
    return $arr;
}

快速排序

分治法：選基準值，分區為「小於基準」與「大於基準」兩子數組，遞歸排序再合併。平均 O(n log n)，實際性能優異。

標準遞歸實現

function quickSort( array $arr ): array {
    $len = count($arr);
    if ( $len <= 1 ) return $arr;
    
    $pivot = $arr[0]; // 選第一個為基準
    $left = $right = [];
    
    for ( $i = 1; $i < $len; $i++ ) {
        if ( $arr[$i] <= $pivot ) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    
    return array_merge( quickSort($left), [$pivot], quickSort($right) );
}

原地分區版（節省內存，PHP 陣列複製開銷大，實際較慢）

function quickSortInPlace( array &$arr, int $low, int $high ) {
    if ( $low >= $high ) return;
    
    $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]]; // PHP 7.1+ 解構賦值交換
        }
    }
    [$arr[$i+1], $arr[$high]] = [$arr[$high], $arr[$i+1]];
    $pi = $i + 1;
    
    quickSortInPlace($arr, $low, $pi - 1);
    quickSortInPlace($arr, $pi + 1, $high);
}

// 使用
$data = [23, 98, 54, 2, 9, 62, 34];
quickSortInPlace($data, 0, count($data)-1);

性能基準測試 (PHP 8.1, 10萬隨機整數)

function benchmark( $name, callable $sort, array $data ) {
    $copy = $data;
    $start = microtime(true);
    $sort($copy);
    $elapsed = microtime(true) - $start;
    echo "$name: " . round($elapsed * 1000, 2) . " ms\n";
}

$data = range(1, 100000);
shuffle($data);

benchmark('bubbleSort', 'bubbleSort', $data);           // ~45,000 ms (極慢)
benchmark('bubbleSortOptimized', 'bubbleSortOptimized', $data); // ~42,000 ms
benchmark('quickSort', 'quickSort', $data);             // ~45 ms
benchmark('quickSortInPlace', 'quickSortInPlace', $data); // ~120 ms (引用傳遞開銷)
benchmark('sort()', 'sort', $data);                     // ~8 ms (C 級內置)
benchmark('rsort()', 'rsort', $data);                   // ~8 ms

結果分析

PHP 內置排序函數最佳實踐

自定義比較示例 (多字段排序)

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

usort($users, function($a, $b) {
    // 年齡升序，年齡相同則分數降序
    if ( $a['age'] !== $b['age'] ) return $a['age'] <=> $b['age'];
    return $b['score'] <=> $a['score']; // 太空船操作符 PHP 7+
});

/*
結果：
Charlie (25, 95)
Alice   (25, 90)
Bob     (30, 85)
*/

進階：穩定排序與大數據集策略

• 穩定性：PHP sort() 系列**不穩定**（相等元素相對位置可能變）。需穩定排序時，給元素加原始索引字段作為次級鍵。
• 超大數據集 (> 100萬)：
  1. 分塊排序 + 歸併 (外部排序)
  2. 使用 Redis Sorted Set / 數據庫 ORDER BY 推算
  3. 考慮 C 擴展 (如 php-ast 排序) 或離線計算
• 避免在比較函數中做重計算：預計算排序鍵，使用 array_multisort() 多鍵排序。

// array_multisort 多鍵排序 (高性能)
$ages = array_column($users, 'age');
$scores = array_column($users, 'score');
array_multisort($ages, SORT_ASC, $scores, SORT_DESC, $users);

總結建議

1. 生產代碼永遠使用內置 sort()/usort()/array_multisort()，C 級實現、穩定優化、邊界情況處理完善。
2. 教學/面試掌握快速排序分區邏輯、遞歸終止條件、基準選擇策略（隨機/三數取中）。
3. 極小數組 (< 20)插入排序可能比快排快（常數因子小），PHP 內部小數組優化已處理。
4. 記住太空船操作符 <=> (PHP 7+) 簡化比較函數編寫。