萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 排序演算法實作:氣泡排序與快速排序程式碼範例與效能分析

演算法複雜度對照

演算法平均時間複雜度最壞時間複雜度空間複雜度穩定性PHP 實作建議
氣泡排序O(n²)O(n²)O(1)穩定教學/極小資料
快速排序O(n log n)O(n²)O(log n)不穩定教學/理解分治法
內建 sort()O(n log n)O(n log n)O(1)不穩定生產環境首選

氣泡排序實作

<?php
/**
 * 氣泡排序:相鄰比較,大者沉底 (遞增)
 * @param array $arr 參考傳遞,原地排序
 * @return array 排序後陣列 (同一參考)
 */
function bubbleSort(array &$arr): array
{
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $swapped = false;
        // 每輪將最大值「氣泡」到末端,下輪可少比較一個
        for ($j = 0; $j < $n - 1 - $i; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                // 交換
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]]; // PHP 7.1+ 解構賦值
                $swapped = true;
            }
        }
        // 優化:若本輪無交換,已有序,提早結束
        if (!$swapped) break;
    }
    return $arr;
}

// 測試
$data = [23, 14, 35, 28, 45, 98, 12, 19, 1, 78];
echo "原始: " . implode(',', $data) . "\n";
bubbleSort($data);
echo "氣泡: " . implode(',', $data) . "\n";
// 輸出: 1,12,14,19,23,28,35,45,78,98
?>

快速排序實作

<?php
/**
 * 快速排序:分治法,選基準值分區
 * @param array $arr
 * @return array 新排序陣列 (非原地)
 */
function quickSort(array $arr): array
{
    $n = count($arr);
    if ($n <= 1) return $arr;

    $pivot = $arr[0]; // 簡單選第一個為基準 (隨機選取可避免最壞情況)
    $left = $right = [];

    for ($i = 1; $i < $n; $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }

    // 遞歸排序左右分區,合併結果
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

// 原地快速排序 (進階,節省記憶體)
function quickSortInPlace(array &$arr, int $low = 0, int $high = null): void
{
    if ($high === null) $high = count($arr) - 1;
    if ($low >= $high) return;

    $pivot = partition($arr, $low, $high);
    quickSortInPlace($arr, $low, $pivot - 1);
    quickSortInPlace($arr, $pivot + 1, $high);
}

function partition(array &$arr, int $low, int $high): int
{
    $pivotValue = $arr[$high];
    $i = $low - 1;
    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] <= $pivotValue) {
            $i++;
            [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
        }
    }
    [$arr[$i + 1], $arr[$high]] = [$arr[$high], $arr[$i + 1]];
    return $i + 1;
}

// 測試
$data = [23, 14, 35, 28, 45, 98, 12, 19, 1, 78];
$sorted = quickSort($data);
echo "快速: " . implode(',', $sorted) . "\n";
// 輸出: 1,12,14,19,23,28,35,45,78,98
?>

PHP 內建排序函數 (生產環境請用這些)

<?php
$arr = [23, 14, 35, 28, 45, 98, 12, 19, 1, 78];

sort($arr);           // 遞增,重新索引
rsort($arr);          // 遞減,重新索引
asort($arr);          // 遞增,保持鍵值關聯
ksort($arr);          // 鍵名遞增
usort($arr, fn($a, $b) => $a <=> $b); // 自訂比較 (太空船運算子 PHP 7+)

// 多維陣列排序
$users = [
    ['name'=>'A', 'age'=>30],
    ['name'=>'B', 'age'=>25],
];
usort($users, fn($a, $b) => $a['age'] <=> $b['age']);
// 或 array_multisort
array_multisort(array_column($users, 'age'), SORT_ASC, $users);
?>

結語

理解氣泡排序 (O(n²)) 與快速排序 (O(n log n) 平均) 的原理,是演算法基礎訓練。**實務開發請直接使用 PHP 內建 sort()、usort()、array_multisort()**,它們基於 C 實作的混合排序 (Timsort/QuickSort 混合),效能極佳且經過充分測試。手寫排序僅供教學、面試或極特殊需求 (如自訂比較器無法用 usort 表達) 時使用。

copyright © 萬盛學電腦網 all rights reserved