插入排序是一種簡單直觀的排序演算法，其工作原理類似整理撲克牌：將陣列分為「已排序」與「未排序」兩部分，每次從未排序區取出一個元素，在已排序區中找到合適位置插入。本文提供完整的 PHP 實現，包含隨機測試資料生成與效能說明。
/**
* 插入排序
* @param array $a 無序陣列
* @return array 有序陣列（原陣列被修改並返回）
*/
function insertSort(array &$a): array {
$size = count($a);
// 從第二個元素開始，預設第一個元素已排序
for ($i = 1; $i < $size; $i++) {
$temp = $a[$i]; // 當前待插入元素
$j = $i - 1;
// 在已排序區 [0..i-1] 中從右向左查找插入位置
while ($j >= 0 && $a[$j] > $temp) {
$a[$j + 1] = $a[$j]; // 元素右移
$j--;
}
$a[$j + 1] = $temp; // 插入到正確位置
}
return $a;
}
/**
* 生成指定大小的隨機整數陣列
*/
function randomNumber(int $size = 10): array {
$rand = [];
for ($i = 0; $i < $size; $i++) {
$rand[] = mt_rand(0, 1000);
}
return $rand;
}
// 測試
$a = randomNumber(20);
echo "Unsorted: " . implode(', ', $a) . "\n";
$sorted = insertSort($a);
echo "Sorted: " . implode(', ', $sorted) . "\n";
// 驗證是否正確排序
$isSorted = true;
for ($i = 1; $i < count($sorted); $i++) {
if ($sorted[$i-1] > $sorted[$i]) { $isSorted = false; break; }
}
echo $isSorted ? "✅ 排序正確" : "❌ 排序失敗";
| 指標 | 複雜度 | 說明 |
|---|---|---|
| 時間複雜度（最好） | O(n) | 陣列已有序，內層 while 迴圈不執行 |
| 時間複雜度（最壞/平均） | O(n²) | 逆序或隨機資料，需大量位移與比較 |
| 空間複雜度 | O(1) | 原地排序，僅需常數額外空間 |
| 穩定性 | 穩定 | 相等元素相對順序不變 |
實際專案中，應優先使用 PHP 高度優化的內建函式：
$arr = [5, 2, 9, 1, 5, 6]; sort($arr); // 升序，重新索引 rsort($arr); // 降序 asort($arr); // 升序，保持鍵值關聯 ksort($arr); // 按鍵名排序 // 物件排序 usort($objects, fn($a, $b) => $a->price <=> $b->price); // PHP 7+ 太空船運算子
將線性查找插入位置改為二分查找，比較次數從 O(n) 降為 O(log n)，但位移次數仍為 O(n²)，整體複雜度不變，僅減少比較操作：
function binaryInsertSort(array &$a): array {
$size = count($a);
for ($i = 1; $i < $size; $i++) {
$temp = $a[$i];
$left = 0;
$right = $i - 1;
// 二分查找插入位置
while ($left <= $right) {
$mid = ($left + $right) >> 1;
if ($a[$mid] > $temp) $right = $mid - 1;
else $left = $mid + 1;
}
// 位移元素
for ($j = $i - 1; $j >= $left; $j--) {
$a[$j + 1] = $a[$j];
}
$a[$left] = $temp;
}
return $a;
}
理解插入排序是掌握更複雜演算法（如希爾排序、TimSort）的基石。實際開發中，選擇正確的工具（內建函式 vs 自定義演算法）比手寫演算法更重要。
