選擇排序 是一種簡單直觀的比較排序算法。核心思想：
特點：交換次數最少（O(n)），適合寫入成本高的存儲介質（如 EEPROM、Flash）。
<?php
class SelectionSort {
/**
* 選擇排序（升序）
* @param array &$arr 引用傳遞，原地排序
* @param callable|null $compare 自定義比較函數
* @return void
*/
public function sort(array &$arr, callable $compare = null): void {
$compare ??= fn($a, $b) => $a <=> $b; // PHP 7.4+ 箭頭函數
$len = count($arr);
for ($i = 0; $i < $len - 1; $i++) {
$minIdx = $i;
// 內層循環：尋找最小元素索引
for ($j = $i + 1; $j < $len; $j++) {
if ($compare($arr[$j], $arr[$minIdx]) < 0) {
$minIdx = $j;
}
}
// 交換（僅當找到更小元素時）
if ($minIdx !== $i) {
$this->swap($arr, $i, $minIdx);
}
}
}
/**
* 交換數組兩個位置的元素
*/
private function swap(array &$arr, int $i, int $j): void {
[$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]]; // PHP 7.1+ 解構賦值
}
/**
* 降序排序
*/
public function sortDesc(array &$arr): void {
$this->sort($arr, fn($a, $b) => $b <=> $a);
}
/**
* 對象數組按屬性排序
*/
public function sortByProperty(array &$arr, string $prop, bool $asc = true): void {
$this->sort($arr, fn($a, $b) => $asc
? ($a->$prop <=> $b->$prop)
: ($b->$prop <=> $a->$prop)
);
}
}
// 使用示例
$sorter = new SelectionSort();
$numbers = [4, 6, 1, 2, 9, 8, 7, 3, 5];
$sorter->sort($numbers);
echo "升序: " . implode(', ', $numbers) . "\n"; // 1, 2, 3, 4, 5, 6, 7, 8, 9
$objects = [
(object)['name' => 'C', 'age' => 30],
(object)['name' => 'A', 'age' => 25],
(object)['name' => 'B', 'age' => 28],
];
$sorter->sortByProperty($objects, 'age');
echo "按年齡升序: " . json_encode($objects) . "\n";
?>
| 指標 | 複雜度 | 說明 |
|---|---|---|
| 時間複雜度（最好） | O(n²) | 無論輸入如何，比較次數固定：n(n-1)/2 |
| 時間複雜度（平均） | O(n²) | |
| 時間複雜度（最壞） | O(n²) | |
| 空間複雜度 | O(1) | 原地排序，僅需常數額外空間 |
| 交換次數 | O(n) | 最多 n-1 次交換，優於冒泡排序 O(n²) |
| 穩定性 | 不穩定 | 相等元素相對位置可能改變（如 5a, 5b → 交換後變 5b, 5a） |
| 算法 | 比較次數 | 交換/移動次數 | 穩定性 | 適合場景 |
|---|---|---|---|---|
| 選擇排序 | n(n-1)/2 | ≤ n-1 | 不穩定 | 寫入昂貴、小數據量、教學 |
| 冒泡排序 | n(n-1)/2 | O(n²) | 穩定 | 近乎有序數據（優化後）、教學 |
| 插入排序 | O(n²) | O(n²) | 穩定 | 小數據、近乎有序、在線排序 |
每輪同時找最小和最大，放到兩端，輪數減半：
public function bidirectionalSort(array &$arr): void {
$left = 0;
$right = count($arr) - 1;
while ($left < $right) {
$minIdx = $left;
$maxIdx = $right;
for ($i = $left; $i <= $right; $i++) {
if ($arr[$i] < $arr[$minIdx]) $minIdx = $i;
if ($arr[$i] > $arr[$maxIdx]) $maxIdx = $i;
}
$this->swap($arr, $left, $minIdx);
// 注意：若 maxIdx == left，交換後最大元素已移至 minIdx
if ($maxIdx === $left) $maxIdx = $minIdx;
$this->swap($arr, $right, $maxIdx);
$left++;
$right--;
}
}
利用堆結構將「尋找最小元素」從 O(n) 降為 O(log n)，整體複雜度達到 O(n log n)：
public function heapSort(array &$arr): void {
$n = count($arr);
// 建堆
for ($i = ($n >> 1) - 1; $i >= 0; $i--) {
$this->heapify($arr, $n, $i);
}
// 排序
for ($i = $n - 1; $i > 0; $i--) {
$this->swap($arr, 0, $i);
$this->heapify($arr, $i, 0);
}
}
private function heapify(array &$arr, int $n, int $i): void {
$largest = $i;
$left = 2 * $i + 1;
$right = 2 * $i + 2;
if ($left < $n && $arr[$left] > $arr[$largest]) $largest = $left;
if ($right < $n && $arr[$right] > $arr[$largest]) $largest = $right;
if ($largest !== $i) {
$this->swap($arr, $i, $largest);
$this->heapify($arr, $n, $largest);
}
}
$arr = [4, 6, 1, 2, 9, 8, 7, 3, 5]; // 生產代碼永遠使用內置函數 sort($arr); // 升序，重建索引 rsort($arr); // 降序 asort($arr); // 升序，保持索引關係 uasort($arr, fn($a, $b) => $a <=> $b); // 自定義比較，保持索引 usort($arr, fn($a, $b) => $a <=> $b); // 自定義比較，重建索引 // 內置排序採用 Timsort（PHP 8+）或 QuickSort，平均 O(n log n)、高度優化、穩定 // 手寫排序僅用於教學、特殊約束環境、面試
| 數據量 | 選擇排序 | PHP sort() | 倍數差距 |
|---|---|---|---|
| 1,000 | ~15 ms | ~0.3 ms | 50x |
| 5,000 | ~350 ms | ~1.8 ms | 194x |
| 10,000 | ~1.4 s | ~4 ms | 350x |
選擇排序作為經典 O(n²) 算法，核心價值在於教學示範、交換次數最少理論意義、特殊硬體環境適用性。實際 PHP 開發中，絕不應在生產代碼中使用手寫選擇排序，內置 sort()/usort() 經過 C 層高度優化、採用 Timsort/QuickSort 混合算法、平均 O(n log n)、穩定可靠。理解選擇排序原理、複雜度分析、穩定性特徵、優化方向（堆排序），有助於建立扎實的算法思維，應對面試與底層原理分析。
