萬盛學電腦網

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

PHP 經典排序演算法實作大全

前言

雖然 PHP 內建 sort()、usort() 已高度優化,但理解經典排序演算法有助於面試、教學與特定場景(如自定義比較邏輯、外部排序)的靈活應用。本文提供四大經典演算法的 PHP 實作與複雜度分析。

1. 冒泡排序

相鄰元素兩兩比較,大的往後冒泡。穩定排序。

function bubbleSort(array $arr): array {
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $n - 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;
}

時間複雜度:O(n²) | 空間:O(1) | 穩定

2. 插入排序

將未排序元素插入已排序序列適當位置。小規模/近乎有序資料極快。

function insertionSort(array $arr): array {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
    return $arr;
}

時間複雜度:O(n²) 最好 O(n) | 空間:O(1) | 穩定

3. 選擇排序

每輪選出最小元素放到已排序區末尾。不穩定。

function selectionSort(array $arr): array {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $minIdx = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$j] < $arr[$minIdx]) $minIdx = $j;
        }
        if ($minIdx !== $i) {
            [$arr[$i], $arr[$minIdx]] = [$arr[$minIdx], $arr[$i]];
        }
    }
    return $arr;
}

時間複雜度:O(n²) | 空間:O(1) | 不穩定

4. 快速排序

分治法:選基準值,分左右子陣列遞歸排序。平均 O(n log n),最壞 O(n²)。

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

時間複雜度:平均 O(n log n) | 空間:O(log n) 遞歸棧 | 不穩定

效能實測(10,000 筆隨機整數)

演算法耗時 (ms)備註
PHP 內建 sort()~2C 實作,最快
Quick Sort (PHP)~45遞歸開銷大
Insertion Sort~1200適合小陣列
Selection Sort~1500
Bubble Sort~2800教學用

實務建議

  • 生產代碼永遠使用內建 sort()/usort(),底層採用 QuickSort + Insertion Sort 混合(Zend Engine)。
  • 需自定義比較時用 usort($arr, fn($a,$b) => $a <=> $b)(PHP 7+ 太空船操作符)。
  • 超大資料集(百萬級)考慮外部排序或資料庫 ORDER BY。
copyright © 萬盛學電腦網 all rights reserved