PHP 快速排序算法實現與解析

PHP 快速排序演算法完整實現

快速排序是經典的分治法排序演算法，平均時間複雜度為 O(n log n)，在實際應用中效能優異。以下提供一個簡潔的 PHP 遞迴實現，適合學習與參考。

核心程式碼

<?php
function quicksort($seq) {
    if (count($seq) > 1) {
        $k = $seq[0];           // 選取基準值
        $x = array();           // 小於等於基準值的元素
        $y = array();           // 大於基準值的元素
        
        for ($i = 1; $i < count($seq); $i++) {
            if ($seq[$i] <= $k) {
                $x[] = $seq[$i];
            } else {
                $y[] = $seq[$i];
            }
        }
        
        // 遞迴排序左右子陣列並合併
        $x = quicksort($x);
        $y = quicksort($y);
        return array_merge($x, array($k), $y);
    } else {
        return $seq;            // 基礎情況：單元素或空陣列直接返回
    }
}

// 測試範例
$arr = array(12, 2, 16, 30, 8, 28, 4, 10, 20, 6, 18);
print_r(quicksort($arr));
?>

執行結果

Array
(
    [0] => 2
    [1] => 4
    [2] => 6
    [3] => 8
    [4] => 10
    [5] => 12
    [6] => 16
    [7] => 18
    [8] => 20
    [9] => 28
    [10] => 30
)

演算法解析

• 基準值選擇：採用首元素作為 pivot，簡單但最壞情況（已排序陣列）會退化為 O(n²)
• 分區策略：單趟掃描將元素分為「小於等於」與「大於」兩組
• 遞迴終止條件：陣列長度 ≤ 1 時直接返回
• 空間複雜度：遞迴呼叫堆疊深度平均 O(log n)，最壞 O(n)

優化建議

實際專案中建議：

1. 隨機選取基準值或採用「三數取中」法避免最壞情況
2. 小陣列（如 < 10 元素）改用插入排序
3. 尾遞迴優化或改寫為迭代版本減少堆疊開銷
4. PHP 7+ 可直接使用內建 sort()/usort()，底層採用混合排序演算效能更優