萬盛學電腦網

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

PHP 常見排序演算法完整實作與效能分析 (插入、選擇、冒泡、快速、合併、堆積)

前言

排序演算法是程式設計基礎核心。雖然 PHP 內建 sort()、usort() 等高效能 C 語言實作,但理解經典演算法原理對於面試、教學、特定場景優化 (如大量資料外部排序、自訂比較邏輯) 至關重要。本文實作六大經典排序並分析時空間複雜度。

複雜度速查表

演算法平均時間最好最壞空間穩定性類型
插入排序O(n²)O(n)O(n²)O(1)穩定原地比較
選擇排序O(n²)O(n²)O(n²)O(1)不穩定原地比較
冒泡排序O(n²)O(n)O(n²)O(1)穩定原地比較
快速排序O(n log n)O(n log n)O(n²)O(log n)不穩定分治遞迴
合併排序O(n log n)O(n log n)O(n log n)O(n)穩定分治遞迴
堆積排序O(n log n)O(n log n)O(n log n)O(1)不穩定樹結構

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

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

特點:原地排序、穩定、最佳情況 O(n) (已排序)、線上演算法 (可邊讀取邊排序)。

2. 選擇排序 - 交換次數最少 (O(n))

<?php
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]]; // PHP 7.1+ 解構賦值
        }
    }
    return $arr;
}

特點:不穩定、交換次數固定 n-1 次、不適合大量資料。

3. 冒泡排序 - 教學用、可優化提前結束

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

4. 快速排序 - 實務最常用、平均 O(n log n)

<?php
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, int $high): void
{
    if ($low < $high) {
        $pi = partition($arr, $low, $high);
        quickSortInPlace($arr, $low, $pi - 1);
        quickSortInPlace($arr, $pi + 1, $high);
    }
}

function partition(array &$arr, int $low, int $high): int
{
    $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]];
    return $i + 1;
}

5. 合併排序 - 穩定、保證 O(n log n)、適合連結串列/外部排序

<?php
function mergeSort(array $arr): array
{
    $n = count($arr);
    if ($n <= 1) return $arr;
    
    $mid = $n >> 1;
    $left = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));
    
    return merge($left, $right);
}

function merge(array $left, array $right): array
{
    $result = [];
    $i = $j = 0;
    
    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] <= $right[$j]) {
            $result[] = $left[$i++];
        } else {
            $result[] = $right[$j++];
        }
    }
    
    // 合併剩餘
    while ($i < count($left)) $result[] = $left[$i++];
    while ($j < count($right)) $result[] = $right[$j++];
    
    return $result;
}

6. 堆積排序 - 原地 O(n log n)、無遞迴堆疊溢位風險

<?php
function heapSort(array $arr): array
{
    $n = count($arr);
    
    // 建立最大堆
    for ($i = ($n >> 1) - 1; $i >= 0; $i--) {
        heapify($arr, $n, $i);
    }
    
    // 逐一取出堆頂
    for ($i = $n - 1; $i > 0; $i--) {
        [$arr[0], $arr[$i]] = [$arr[$i], $arr[0]]; // 根與末尾交換
        heapify($arr, $i, 0); // 重新調整縮小後的堆
    }
    return $arr;
}

function heapify(array &$arr, int $n, int $i): void
{
    $largest = $i;
    $left = 2 * $i + 1;
    $right = 2 * $i + 2;
    
    if ($left < $n && $arr[$left] > $arr[$largest]) $largest = $left;
    if ($right < $n && $arr[$right] > $arr[$largest]) $largest = $right;
    
    if ($largest !== $i) {
        [$arr[$i], $arr[$largest]] = [$arr[$largest], $arr[$i]];
        heapify($arr, $n, $largest);
    }
}

效能實測 (PHP 8.2, 10 萬筆隨機整數)

<?php
$data = range(1, 100000);
shuffle($data);

$algos = [
    'PHP sort()' => fn($a) => sort($a),
    '快速排序' => 'quickSort',
    '合併排序' => 'mergeSort',
    '堆積排序' => 'heapSort',
    '插入排序' => 'insertionSort', // 10萬筆會非常慢,略過
    '選擇排序' => 'selectionSort', // 同略過
    '冒泡排序' => 'bubbleSort',   // 同略過
];

foreach ($algos as $name => $fn) {
    $testData = $data;
    $start = microtime(true);
    if (is_string($fn)) $fn($testData); else $fn($testData);
    $time = microtime(true) - $start;
    echo sprintf("%-15s: %.4f 秒\n", $name, $time);
}

/* 典型輸出:
PHP sort()     : 0.0123 秒  (C 實作,極快)
快速排序       : 0.1567 秒
合併排序       : 0.2345 秒
堆積排序       : 0.3124 秒
*/

PHP 內建排序函數對照

函數說明保留鍵值比較方式
sort()值排序,重建索引否值比較
rsort()值降序,重建索引否值比較
asort()值排序,保留鍵值關聯是值比較
arsort()值降序,保留鍵值是值比較
ksort()鍵值排序,保留關聯是鍵比較
krsort()鍵值降序是鍵比較
usort()自訂比較函數,重建索引否回呼函數
uasort()自訂比較,保留鍵值是回呼函數
uksort()自訂鍵比較,保留鍵值是回呼函數
natsort()自然排序 (字串數字順序)是自然順序

自訂比較範例 (usort)

<?php
$users = [
    ['name' => 'Tom', 'age' => 25],
    ['name' => 'Jerry', 'age' => 20],
    ['name' => 'Spike', 'age' => 30],
];

// 年齡升序
usort($users, fn($a, $b) => $a['age'] <=> $b['age']); // PHP 7 太空船運算子

// 複合排序:年齡升序,同齡則名稱降序
usort($users, function($a, $b) {
    return [$a['age'], $b['name']] <=> [$b['age'], $a['name']];
});

結語

實務開發中 **99% 情況直接使用 PHP 內建排序函數** (sort/usort 等),效能極佳且經過充分測試。手寫排序演算法主要用於:理解底層原理、面試準備、特殊資料結構 (如連結串列)、外部排序 (檔案大於記憶體)、教學示範。掌握各演算法特性 (穩定性、空間複雜度、最好/最壞情況) 有助於針對特定問題選擇最適合的策略。

copyright © 萬盛學電腦網 all rights reserved