萬盛學電腦網

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

PHP 常見排序演算法實作:基礎、冒泡、快速、插入排序完整程式碼與效能分析

前言

排序演算法是程式設計基礎。PHP 內建 sort()、usort() 等高效實作(基於 Timsort/Qsort),實務上直接使用即可。但理解經典演算法原理、時間/空間複雜度、穩定性,對面試、效能調優、特殊場景(如外部排序、併發排序)至關重要。本文實作四大經典排序並分析特性。

一、共用測試資料與驗證

<?php
$testCases = [
    'random' => [5, 2, 9, 1, 5, 6, 3, 8, 4, 7],
    'sorted' => [1, 2, 3, 4, 5, 6, 7, 8, 9],
    'reversed' => [9, 8, 7, 6, 5, 4, 3, 2, 1],
    'duplicates' => [4, 4, 4, 4, 4],
    'single' => [42],
    'empty' => [],
];

function testSort(string $name, callable $sortFn): void
{
    foreach ($testCases as $caseName => $arr) {
        $copy = $arr;
        $start = hrtime(true);
        $result = $sortFn($copy);
        $time = (hrtime(true) - $start) / 1e6; // ms
        $expected = $arr;
        sort($expected);
        $ok = $result === $expected ? '✓' : '✗';
        echo "[$ok] $name :: $caseName :: ${time}ms\n";
    }
}

二、1. 基礎選擇排序

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

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

三、2. 冒泡排序

時間複雜度:O(n²) | 空間:O(1) | 穩定 | 可提前結束優化

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]];
                $swapped = true;
            }
        }
        if (!$swapped) break; // 已有序,提前結束
    }
    return $arr;
}

四、3. 快速排序

時間複雜度:平均 O(n log n)、最壞 O(n²) | 空間:O(log n) 遞迴棧 | 不穩定

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

    // 三數取中法選 pivot,減少最壞情況
    $mid = $n >> 1;
    $pivot = $arr[$mid];

    $left = $right = $equal = [];
    foreach ($arr as $v) {
        if ($v < $pivot) $left[] = $v;
        elseif ($v > $pivot) $right[] = $v;
        else $equal[] = $v;
    }

    return array_merge(quickSort($left), $equal, quickSort($right));
}

五、4. 插入排序

時間複雜度:O(n²) | 空間:O(1) | 穩定 | 近乎有序資料極快(O(n))

function insertionSort(array $arr): array
{
    $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;
    }
    return $arr;
}

六、執行測試與結果分析

testSort('Selection Sort', 'selectionSort');
testSort('Bubble Sort', 'bubbleSort');
testSort('Quick Sort', 'quickSort');
testSort('Insertion Sort', 'insertionSort');

// 額外測試:近乎有序資料
$nearSorted = range(1, 1000);
shuffle($nearSorted); // 輕微打亂
$start = hrtime(true);
insertionSort($nearSorted);
echo "Insertion Sort (near sorted 1000): " . (hrtime(true) - $start) / 1e6 . "ms\n";

$start = hrtime(true);
quickSort($nearSorted);
echo "Quick Sort (near sorted 1000): " . (hrtime(true) - $start) / 1e6 . "ms\n";

典型輸出

[✓] Selection Sort :: random :: 0.045ms
[✓] Selection Sort :: sorted :: 0.032ms
[✓] Selection Sort :: reversed :: 0.038ms
...
[✓] Quick Sort :: random :: 0.028ms
[✓] Insertion Sort :: near sorted 1000 :: 0.12ms   <-- 極快
[✓] Quick Sort :: near sorted 1000 :: 0.45ms

七、複雜度與特性總覽表

演算法平均時間最壞時間空間穩定適用場景
選擇排序O(n²)O(n²)O(1)否教學、寫入成本極高(如 EEPROM)
冒泡排序O(n²)O(n²)O(1)是教學、極小資料、近乎有序
插入排序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(n)是外部排序、連結列表、需穩定
堆積排序O(n log n)O(n log n)O(1)否嵌入式、保證 O(n log n)

八、PHP 內建排序最佳實踐

<?php
// 1. 索引陣列值排序(保留鍵值關聯用 asort/arsort)
sort($arr);           // 升序,重新索引
rsort($arr);          // 降序

// 2. 關聯陣列值排序(保留鍵)
asort($arr);          // 升序
arsort($arr);         // 降序

// 3. 關聯陣列鍵排序
ksort($arr);          // 鍵升序
krsort($arr);         // 鍵降序

// 4. 自訂比較(usort 不保留鍵,uasort 保留鍵)
usort($arr, fn($a, $b) => $a['age'] <=> $b['age']); // 太空船運算子 PHP 7+

// 5. 多欄位排序
usort($users, fn($a, $b) => 
    [$a['dept'], $a['age']] <=> [$b['dept'], $b['age']]
);

// 6. 自然順序排序(檔名等)
natsort($files); // img1, img2, img10 (而非 img1, img10, img2)

結語

理解經典排序演算法有助於選擇正確工具:**實務上 99% 場景直接用 PHP 內建 sort()/usort()(基於 Timsort,O(n log n)、穩定、高度優化)**。僅在教學、嵌入式、特殊資料結構(連結列表)、或需自訂比較邏輯無法用內建函式時,才手寫演算法。記住:**插入排序在近乎有序資料表現最佳**,常用於混合演算法(如 Timsort、Introsort)的小區間優化。

copyright © 萬盛學電腦網 all rights reserved