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