萬盛學電腦網

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

PHP 實現插入排序算法詳解與性能分析

算法原理

插入排序將數組分為「已排序區」和「未排序區」,初始已排序區僅含第一個元素。每次從未排序區取出首元素,在已排序區中從右向左比較,找到插入位置並移動元素騰出空位插入。穩定、原地、適合小規模或近乎有序數據。

標準實現

<?php
/**
 * 插入排序(升序)
 * @param array $arr 數值數組(引用傳遞,原地排序)
 * @return array 同一數組引用(鏈式調用便利)
 */
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;
}

// 測試
$data = [64, 34, 25, 12, 22, 11, 90];
insertionSort($data);
echo implode(', ', $data); // 11, 12, 22, 25, 34, 64, 90

泛化版:支援自定義比較器

function insertionSortFlexible(array &$arr, callable $cmp = null): array {
    $cmp ??= fn($a, $b) => $a <=> $b; // PHP 7.0+ 太空船操作符
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $cmp($arr[$j], $key) > 0) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
    return $arr;
}

// 降序
insertionSortFlexible($data, fn($a, $b) => $b <=> $a);
// 對象數組按屬性排序
insertionSortFlexible($users, fn($a, $b) => $a->age <=> $b->age);

複雜度分析

  • 最好 O(n):數組已有序,內層 while 循環一次不執行。
  • 最壞 O(n²):逆序,每次插入需遍歷整個已排序區。
  • 適合場景:n < 50、近乎有序、數據流實時排序(如插入新元素維持有序)。

PHP 內建排序對比

$data = range(1, 10000);
shuffle($data);

// 內建 sort() - 快速排序變體 (C 級實現)
$t1 = microtime(true);
sort($data);
echo "sort(): " . (microtime(true) - $t1) . "s\n"; // ~0.002s

// 插入排序 (PHP 用戶態)
$t2 = microtime(true);
insertionSort($data);
echo "insertionSort(): " . (microtime(true) - $t2) . "s\n"; // ~1.2s (慢 600 倍)

結論:生產代碼永遠使用內建 sort()/usort(),C 級實現快數百倍。插入排序僅用於教學、面試、或極小數據量(<20)且需自定義比較邏輯且不想寫匿名函數的罕見場景。

優化變體:二分查找插入點

function binaryInsertionSort(array &$arr): array {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        // 二分查找插入位置
        $left = 0; $right = $i - 1;
        while ($left <= $right) {
            $mid = ($left + $right) >> 1;
            if ($arr[$mid] > $key) $right = $mid - 1;
            else $left = $mid + 1;
        }
        // 移動元素
        for ($j = $i - 1; $j >= $left; $j--) {
            $arr[$j + 1] = $arr[$j];
        }
        $arr[$left] = $key;
    }
    return $arr;
}

比較次數從 O(n²) 降為 O(n log n),但移動次數仍為 O(n²),PHP 中因函數調用開銷大,實際未必比標準版快。

總結

插入排序是理解「原地、穩定、增量構建」排序思想的經典教材。PHP 開發中直接用 sort()、usort()、array_multisort(),只在面試白板題、教學演示、極微量數據(<20)且無法使用內建函數時手寫。

copyright © 萬盛學電腦網 all rights reserved
指標最好平均最壞空間穩定性
時間複雜度O(n)O(n²)O(n²)O(1)穩定