PHP 快速排序演算法深度解析：分治策略、分區邏輯、遞歸實作與效能優化

核心思想：分治法

1. 選取 **基準值** 通常取首/中/隨機元素。
2. **分區**：將陣列重新排列，小於基準在左，大於在右，基準落在最終位置。
3. **遞歸** 對左右子陣列重複上述步驟，直到子陣列長度 ≤ 1。

分區演示 (以首元素為基準)

原始: [5, 3, 0, 11, 44, 7, 23, 2]
基準: 5
分區過程:
  左指標 i 從左向右找 >5
  右指標 j 從右向左找 <5
  交換並繼續，直到 i >= j
  最後將基準與 j 位置交換
結果: [2, 3, 0, 5, 44, 7, 23, 11]
      左子陣列      右子陣列
遞歸處理左右兩部分...

完整類實作 (支援任意比較器)

<?php
class QuickSort
{
    /**
     * 公開入口
     * @param array $arr  待排序陣列 (引用修改)
     * @param callable|null $cmp 比較函數 fn($a,$b) 回傳 -1/0/1
     */
    public static function sort(array &$arr, callable $cmp = null): void
    {
        $cmp = $cmp ?? fn($a, $b) => $a <=> $b; // PHP 7+ 太空船運算子
        self::quickSort($arr, 0, count($arr) - 1, $cmp);
    }

    private static function quickSort(array &$arr, int $low, int $high, callable $cmp): void
    {
        if ($low >= $high) return;

        $pivotPos = self::partition($arr, $low, $high, $cmp);
        self::quickSort($arr, $low, $pivotPos - 1, $cmp);
        self::quickSort($arr, $pivotPos + 1, $high, $cmp);
    }

    private static function partition(array &$arr, int $low, int $high, callable $cmp): int
    {
        $pivot = $arr[$low]; // 基準值
        $i = $low;
        $j = $high;

        while ($i < $j) {
            // 從右向左找第一個 < pivot
            while ($i < $j && $cmp($arr[$j], $pivot) >= 0) {
                $j--;
            }
            // 從左向右找第一個 > pivot
            while ($i < $j && $cmp($arr[$i], $pivot) <= 0) {
                $i++;
            }
            if ($i < $j) {
                [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]]; // 解構賦值交換
            }
        }
        // 將基準放到最終位置
        $arr[$low] = $arr[$i];
        $arr[$i] = $pivot;
        return $i;
    }
}
?>

使用範例

$data = [5, 3, 0, 11, 44, 7, 23, 2];
QuickSort::sort($data);
print_r($data); // [0, 2, 3, 5, 7, 11, 23, 44]

// 物件排序
$users = [
    ['name'=>'Bob','age'=>30],
    ['name'=>'Alice','age'=>25],
    ['name'=>'Charlie','age'=>35],
];
QuickSort::sort($users, fn($a,$b) => $a['age'] <=> $b['age']);
print_r($users); // 按 age 升序

效能與優化要點

內建替代方案

sort($arr);           // 索引重排，Quicksort (C 實作，極快)
rsort($arr);          // 降序
usort($arr, $cmp);    // 自定比較，通常為 Quicksort/合併排序混合
ksort($arr);          // 鍵名排序

生產環境直接用內建 sort()/usort()，C 層實作、高度優化、穩定可靠。手寫 QuickSort 僅供教學/面試/特殊比較器需求。

總結

快速排序以「分治 + 分區」實現平均 O(n log n)、原地排序。掌握分區雙指標邏輯、基準選取策略、遞歸終止條件，即可靈活應對面試與特殊排序需求。