PHP 經典排序算法實現：冒泡排序優化版與快速排序

冒泡排序

核心思想：相鄰元素兩兩比較，大的後移（升序），每輪將最大元素「冒泡」到末尾。優化點：若某輪無交換，說明已有序，提前終止。

基礎版

function bubbleSortBasic(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]) {
                [$arr[$j], $arr[$j - 1]] = [$arr[$j - 1], $arr[$j]]; // PHP 7.1+ 解構賦值交換
            }
        }
    }
    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]) {
                [$arr[$j], $arr[$j - 1]] = [$arr[$j - 1], $arr[$j]];
                $swapped = true;
            }
        }
        if (!$swapped) break; // 本輪無交換，已有序
    }
    return $arr;
}

測試

$data = [3, 8, 1, 4, 11, 7];
print_r(bubbleSortOptimized($data));
// Output: [1, 3, 4, 7, 8, 11]

快速排序

分治策略：選基準值，小於基準放左陣列，大於放右陣列，遞歸排序左右子陣列，最後合併。

實現

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));
}

測試

$data = [23, 98, 54, 2, 9, 62, 34];
print_r(quickSort($data));
// Output: [2, 9, 23, 34, 54, 62, 98]

複雜度對比

實際開發建議

• PHP 內置 sort()/rsort()/usort() 基於 QuickSort/ZendSort（混合排序），性能遠超用戶態實現，**生產代碼直接使用內置函數**。
• 教學/面試場景理解原理即可，注意遞歸深度限制（大數據量快排可能棧溢出，可改用迭代棧）。
• 穩定排序需求用 usort() 配合索引保持，或改用歸併排序。