插入排序 將陣列分為「已排序區」與「未排序區」。初始時已排序區只有第一個元素。每次從未排序區取出第一個元素,在已排序區中從右向左比較,找到適當位置插入,並將較大元素右移。重複直到未排序區為空。
原始陣列:[2, 6, 3, 9]
[6, 2, 3, 9][6, 3, 2, 9][9, 6, 3, 2]<?php
function insertSort(&$arr) {
$len = count($arr);
for ($i = 1; $i < $len; $i++) {
$insertVal = $arr[$i];
$j = $i - 1;
// 從右向左掃描已排序區
while ($j >= 0 && $insertVal > $arr[$j]) { // 由大到小用 >
$arr[$j + 1] = $arr[$j]; // 右移
$j--;
}
$arr[$j + 1] = $insertVal; // 插入空位
}
}
$myarr = array(2, 6, 3, 9);
insertSort($myarr);
echo '<pre>'; print_r($myarr); // [9, 6, 3, 2]
?>
| 情況 | 時間複雜度 | 比較次數 | 移動次數 |
|---|---|---|---|
| 最好 (已排序) | O(n) | n-1 | 0 |
| 最差 (逆序) | O(n²) | n(n-1)/2 | n(n-1)/2 |
| 平均 | O(n²) | ~n²/4 | ~n²/4 |
rsort() (由大到小) 或 arsort() (保留鍵名),底層採用 Quicksort,效能遠優於純 PHP 實作。