PHP 插入排序算法實現與代碼解析

算法原理

1. 默認第一個元素已排序
2. 從第二個元素開始，取出當前元素 $insertVal
3. 在已排序區間（索引 0 到 i-1）從右向左掃描
4. 若已排序元素 > $insertVal，將該元素右移一位
5. 重複直到找到 ≤ $insertVal 的位置或到達數組開頭
6. 將 $insertVal 插入空出的位置
7. 重複步驟 2-6 直至遍歷完畢

時間複雜度：最好 O(n)（已有序）、最壞/平均 O(n²)；空間複雜度 O(1)，穩定排序。

PHP 實現代碼

<?php
$arr = [123, 0, 5, -1, 4, 15];

function insertSort(array &$arr): void {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $insertVal = $arr[$i];
        $insertIndex = $i - 1;

        // 從右向左查找插入位置
        while ($insertIndex >= 0 && $insertVal < $arr[$insertIndex]) {
            $arr[$insertIndex + 1] = $arr[$insertIndex]; // 右移
            $insertIndex--;
        }
        // 插入
        $arr[$insertIndex + 1] = $insertVal;
    }
}

insertSort($arr);
print_r($arr);
/* 輸出：
Array
(
    [0] => -1
    [1] => 0
    [2] => 4
    [3] => 5
    [4] => 15
    [5] => 123
)
*/

優化變體

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

將線性查找改為二分查找，比較次數降至 O(log n)，但移動次數仍為 O(n²)，適合比較操作昂貴的場景。

function binaryInsertSort(array &$arr): void {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $val = $arr[$i];
        $left = 0;
        $right = $i - 1;
        // 二分查找插入位置
        while ($left <= $right) {
            $mid = (int)(($left + $right) / 2);
            if ($val < $arr[$mid]) {
                $right = $mid - 1;
            } else {
                $left = $mid + 1;
            }
        }
        // $left 即為插入位置，右移元素
        for ($j = $i - 1; $j >= $left; $j--) {
            $arr[$j + 1] = $arr[$j];
        }
        $arr[$left] = $val;
    }
}

應用場景與建議

• 數據量小（< 50）、近乎有序、嵌入式環境、教學演示
• 大數據量請使用 sort()（快速排序）、usort() 或 SplHeap/SplPriorityQueue
• PHP 內建排序函數基於 C 實現，性能遠超用戶態代碼，優先使用