選擇排序 每輪從未排序區選出最大 (或最小) 元素,與未排序區首位元素交換。進行 n-1 輪後完成排序。特點是交換次數少 (最多 n-1 次),但比較次數固定 O(n²)。
原始:[2, 6, 3, 9]
[9, 6, 3, 2][9, 6, 3, 2][9, 6, 3, 2]<?php
function selectSort(&$arr) {
$len = count($arr);
for ($i = 0; $i < $len - 1; $i++) {
$maxIdx = $i;
for ($j = $i + 1; $j < $len; $j++) {
if ($arr[$j] > $arr[$maxIdx]) { // 由大到小
$maxIdx = $j;
}
}
if ($maxIdx !== $i) {
// 交換
$tmp = $arr[$i];
$arr[$i] = $arr[$maxIdx];
$arr[$maxIdx] = $tmp;
}
}
}
$myarr = array(2, 6, 3, 9);
selectSort($myarr);
echo '<pre>'; print_r($myarr); // [9, 6, 3, 2]
?>
| 指標 | 數值 |
|---|---|
| 時間複雜度 | O(n²) (最好/最差/平均皆同) |
| 空間複雜度 | O(1) 原地排序 |
| 比較次數 | n(n-1)/2 |
| 交換次數 | 0 ~ n-1 |
| 穩定性 | 不穩定 (相等元素相對位置可能改變) |
rsort()/arsort()。選擇排序邏輯直觀,適合初學者理解「循環不變式」與「原地交換」概念,也是後續學習堆積排序 的基礎。