PHP 快速排序演算法原理深度解析與遞歸實作

快速排序是對冒泡排序的重大改進，採用分治法策略，平均時間複雜度 O(n log n)，是實務中最常用的高效排序演算法之一。本文詳細解析其核心邏輯、分區過程與 PHP 遞歸實作。

核心思想：分治法

1. 選取基準值：通常取第一個或中間元素
2. 分區：將陣列重新排列，小於基準值的置左，大於的置右
3. 遞歸排序：對左右兩個子陣列重複上述步驟
4. 合併：因原地排序，無需額外合併步驟

單趟分區過程圖解

以陣列 [49, 38, 65, 97, 76, 13, 27, 49] 為例，基準值 49：

初始: [49, 38, 65, 97, 76, 13, 27, 49]
       ↑                    ↑
       i                    j
步驟1: j 向左找 < 49 → 27，與 i+1(38) 交換
步驟2: i 向右找 > 49 → 65，與 j-1(97) 交換
... 重複直到 i >= j
最終: [27, 38, 13, 49, 76, 97, 65, 49]
              ↑
           基準值歸位（索引 3）
左側皆 ≤ 49，右側皆 ≥ 49

PHP 遞歸實作（標準版）

<?php
function quickSort(array &$arr, int $left, int $right): void {
    if ($left >= $right) return;
    
    $pivotIndex = partition($arr, $left, $right);
    quickSort($arr, $left, $pivotIndex - 1);
    quickSort($arr, $pivotIndex + 1, $right);
}

function partition(array &$arr, int $left, int $right): int {
    $pivot = $arr[$left]; // 選最左為基準
    $i = $left;
    $j = $right;
    
    while ($i < $j) {
        // 從右向左找第一個 < pivot
        while ($i < $j && $arr[$j] >= $pivot) $j--;
        // 從左向右找第一個 > pivot
        while ($i < $j && $arr[$i] <= $pivot) $i++;
        if ($i < $j) {
            [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
        }
    }
    // 基準值歸位
    $arr[$left] = $arr[$i];
    $arr[$i] = $pivot;
    return $i;
}

// 測試
$data = [13, 14, 55, 10, 54, 2, 79, 106, 89, 90, 22, 60, 111, 77777, -110, -10, 123];
quickSort($data, 0, count($data) - 1);
echo implode(', ', $data);
// -110, -10, 2, 10, 13, 14, 22, 54, 55, 60, 79, 89, 90, 106, 111, 123, 77777
?>

效能指標與優化方向

關鍵優化策略

• 三數取中法：取首、中、末三者中位數作基準，避免最差情況
• 隨機基準：$pivot = $arr[rand($left, $right)]
• 小陣列切換插入排序：長度 < 10 時改用插入排序
• 尾遞歸優化：對較大分區遞歸，較小分區迴圈處理，限制堆疊深度

實務建議

PHP 內建 sort()、usort() 採用混合排序（Timsort/QuickSort），效能經過高度優化且穩定，**生產環境請直接使用內建函式**，僅在教學、面試或特殊約束（如嵌入式環境無標準庫）時手寫快速排序。