PHP 插入排序算法原理與實戰代碼詳解

插入排序是一種直觀、易於理解的排序算法，適合小規模數據或近乎有序的數組。本文通過實例拆解其核心邏輯，並提供封裝後的 PHP 函數供直接使用。

算法核心思想

以數組 [2, 6, 3, 9] 為例，目標是降序排列。插入排序將數組分為「已排序區」和「未排序區」。初始時，第一個元素視為已排序。每次從未排序區取出首個元素，在已排序區中從右向左比較，找到合適位置插入，並將較大元素右移。

執行過程圖解

• 第 1 輪：取 6，與 2 比較，6 > 2 → 插入 2 前面 → [6, 2, 3, 9]
• 第 2 輪：取 3，與 2 比較，3 > 2 → 2 右移；再與 6 比較，3 < 6 → 插入 6 後 → [6, 3, 2, 9]
• 第 3 輪：取 9，依次與 2、3、6 比較，均小於 9 → 全部右移，9 插到最前 → [9, 6, 3, 2]

PHP 代碼實現

封裝為函數，採用引用傳參（&$arr）直接修改原數組，避免拷貝開銷：

<?php
/**
 * 插入排序（降序）
 * @param array &$arr 待排序數組（引用傳參）
 */
function insertSort(&$arr) {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $insertVal = $arr[$i]; // 待插入的值
        // 內層循環：從已排序區右端向左掃描
        for ($j = $i; $j > 0; $j--) {
            if ($insertVal > $arr[$j - 1]) {
                $arr[$j] = $arr[$j - 1]; // 後移
            } else {
                break; // 找到位置，提前結束內層循環
            }
        }
        $arr[$j] = $insertVal; // 插入
    }
}

// 測試
$myarr = array(2, 6, 3, 9);
insertSort($myarr);
echo '<pre>';
print_r($myarr); // 輸出: Array ( [0] => 9 [1] => 6 [2] => 3 [3] => 2 )
?>

代碼優化說明

• 將 $arr[$i] 存入變量 $insertVal，減少數組訪問次數。
• 內層循環增加 break，一旦找到插入位置立即跳出，避免無謂比較。
• 時間複雜度：最好 O(n)（已有序），最壞 O(n²)（逆序），平均 O(n²)。空間複雜度 O(1)。

適用場景

數據量較小（< 50）、部分有序、或作為快速排序等高級算法的小區間優化。大數據量請改用快速排序、歸並排序或 PHP 內建 rsort()。