PHP 實現插入排序算法：代碼實現、複雜度分析與優化變體

算法核心思想

將數組分為「已排序區」和「未排序區」，每次從未排序區取首元素，在已排序區從右向左比較、位移，找到插入位置。類似整理撲克牌。

標準實現

function insertSort(array $a): array {
    $n = count($a);
    for ($i = 1; $i < $n; $i++) {
        $temp = $a[$i];
        $j = $i - 1;
        // 從右向左查找插入位置，同時後移元素
        while ($j >= 0 && $temp < $a[$j]) {
            $a[$j + 1] = $a[$j];
            $j--;
        }
        $a[$j + 1] = $temp; // 插入
    }
    return $a;
}

複雜度分析

測試驗證

function randomNumber(int $size = 10): array {
    $arr = [];
    for ($i = 0; $i < $size; $i++) $arr[] = mt_rand(0, 1000);
    return $arr;
}

$a = randomNumber(20);
echo "Unsorted: ".implode(' ', $a)."\n";
echo "Sorted:   ".implode(' ', insertSort($a))."\n";

優化變體

1. 二分查找插入位置（Binary Insertion Sort）

將線性查找優化為 O(log n)，但元素位移仍為 O(n²)，適合「比較成本高、移動成本低」的場景（如大對象排序）。

function binaryInsertSort(array $a): array {
    $n = count($a);
    for ($i = 1; $i < $n; $i++) {
        $temp = $a[$i];
        $left = 0; $right = $i - 1;
        while ($left <= $right) {
            $mid = ($left + $right) >> 1;
            if ($temp < $a[$mid]) $right = $mid - 1;
            else $left = $mid + 1;
        }
        for ($j = $i - 1; $j >= $left; $j--) $a[$j + 1] = $a[$j];
        $a[$left] = $temp;
    }
    return $a;
}

2. 希爾排序（Shell Sort）

插入排序的改進版，按增量分組預排序，最終增量為 1 時退化為插入排序，平均 O(n^1.3)。

適用場景總結

• 小規模數據（n < 50）：插入排序常因常數因子小而快於 O(n log n) 算法。
• 近乎有序數據：最好 O(n) 極其高效。
• 在線排序/流式數據：數據逐個到達，即時維護有序序列。
• 避免：大規模亂序數據，首選快排/歸併/堆排/Timsort(PHP 內建 sort())。