萬盛學電腦網

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

PHP 陣列排序算法大全:插入、選擇、氣泡、快速排序完整實作與效能分析

為什麼要手寫排序?

PHP 內建 `sort()`、`asort()`、`ksort()` 等函式已高度優化(C 實作),實務上**直接使用內建函式**。手寫排序算法的價值在於:理解時間/空間複雜度、面試準備、特殊邏輯無法用內建函式表達時的自定義排序基礎。

四大經典排序 PHP 實作

1. 插入排序 — 適合小規模、近乎有序資料

<?php
function insertionSort(array &$arr): void
{
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        // 將大於 key 的元素右移
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
}
  • 時間複雜度:最好 O(n)、平均/最差 O(n²)
  • 空間複雜度:O(1) 原地排序
  • 穩定排序

2. 選擇排序 — 簡單但效能固定 O(n²)

<?php
function selectionSort(array &$arr): void
{
    $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]]; // PHP 7.1+ 解構賦值
        }
    }
}
  • 時間複雜度:O(n²) 無最好情況
  • 空間複雜度:O(1)
  • 不穩定排序

3. 氣泡排序 — 教學用、實務極少用

<?php
function bubbleSort(array &$arr): void
{
    $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]];
                $swapped = true;
            }
        }
        if (!$swapped) break; // 提前結束優化
    }
}
  • 時間複雜度:最好 O(n)、平均/最差 O(n²)
  • 空間複雜度:O(1)
  • 穩定排序

4. 快速排序 — 平均 O(n log n)、實務常用(PHP 內建 sort 底層即為快排變體)

<?php
function quickSort(array $arr): array
{
    if (count($arr) <= 1) return $arr;

    $pivot = $arr[0];
    $left = $right = [];

    for ($i = 1; $i < count($arr); $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 = $arr[$high];
    $i = $low - 1;
    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] <= $pivot) {
            $i++;
            [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
        }
    }
    [$arr[$i + 1], $arr[$high]] = [$arr[$high], $arr[$i + 1]];
    $pi = $i + 1;

    quickSortInPlace($arr, $low, $pi - 1);
    quickSortInPlace($arr, $pi + 1, $high);
}
  • 時間複雜度:平均 O(n log n)、最差 O(n²)(已排序陣列),可用隨機 pivot 改善
  • 空間複雜度:遞迴呼叫棧 O(log n) ~ O(n)
  • 不穩定排序

PHP 內建排序函式速查表

函式排序依據保留鍵名順序適用場景
sort()值否(重建索引)升冪索引陣列
rsort()值否降冪索引陣列反序
asort()值是升冪關聯陣列按值排序
arsort()值是降冪關聯陣列按值反序
ksort()鍵是升冪關聯陣列按鍵排序
krsort()鍵是降冪關聯陣列按鍵反序
natsort()值 (自然排序)是升冪含數字字串:'img2' < 'img10'
natcasesort()值 (自然排序、不分大小寫)是升冪同上,忽略大小寫
usort()自定義比較函式否自訂複雜物件、多欄位排序
uasort()自定義比較函式是自訂關聯陣列自定義排序
uksort()自定義鍵比較是自訂按鍵自定義排序

實務常見排序需求範例

多維陣列多欄位排序

<?php
$users = [
    ['name' => 'Alice', 'age' => 25, 'score' => 90],
    ['name' => 'Bob',   'age' => 30, 'score' => 85],
    ['name' => 'Charlie','age' => 25, 'score' => 95],
];

// 年齡升冪,分數降冪
usort($users, function ($a, $b) {
    if ($a['age'] !== $b['age']) return $a['age'] <=> $b['age'];
    return $b['score'] <=> $a['score']; // 分數高者優先
});

物件陣列排序

<?php
class Product {
    public function __construct(public string $name, public float $price, public int $stock) {}
}

$products = [
    new Product('A', 100, 5),
    new Product('B', 50,  20),
    new Product('C', 100, 2),
];

// 價格升冪,庫存降冪
usort($products, fn($a, $b) =>
    $a->price <=> $b->price
    ?: $b->stock <=> $a->stock
);

效能基準測試參考 (10,000 元素隨機整數)

算法PHP 手寫耗時內建 sort() 耗時備註
插入排序~1.2 秒~0.002 秒O(n²) 明顯偏慢
選擇排序~1.5 秒
氣泡排序~2.8 秒最慢
快速排序 (遞迴)~0.015 秒接近內建但仍慢 10 倍

結論:任何實務排序需求,**直接使用內建函式**。手寫排序僅供學習演算法原理。

結語

掌握排序算法原理有助於理解電腦科學核心概念,但在 PHP 開發中,善用 `usort`、`array_multisort`、集合類別(如 Laravel Collections)配合箭頭函式,才是高效、可維護的專業做法。

copyright © 萬盛學電腦網 all rights reserved