選擇排序每輪從未排序區域選出 最小元素，與未排序區域首位元素交換。將陣列劃分為「已排序區域（左）」與「未排序區域（右）」，邊界逐步右移。
package al;
public class SelectSort {
/**
* 選擇排序（升序）
* @param array 待排序陣列
* 時間複雜度：O(n²) — 無論輸入分佈
* 空間複雜度：O(1)
* 穩定性：不穩定（交換可能改變相等元素相對順序）
* 特點：交換次數最少，僅 O(n)
*/
public void sort(int[] array) {
int n = array.length;
for (int i = 0; i < n; i++) {
int minIndex = i; // 假設當前位置即最小
// 掃描未排序區域尋找真正最小值索引
for (int j = i; j < n; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
// 單次交換將最小值放到正確位置
if (minIndex != i) {
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}
}
}
public static void main(String[] args) {
SelectSort sorter = new SelectSort();
int[] elements = {14, 77, 21, 9, 10, 50, 43, 14};
System.out.print("排序前：");
printArray(elements);
sorter.sort(elements);
System.out.print("排序後：");
printArray(elements);
// 輸出：9 10 14 14 21 43 50 77
}
private static void printArray(int[] arr) {
for (int v : arr) System.out.print(v + " ");
System.out.println();
}
}初始：[64, 25, 12, 22, 11]
i=0：最小 11 (索引4) ↔ 64 → [11, 25, 12, 22, 64]
i=1：最小 12 (索引2) ↔ 25 → [11, 12, 25, 22, 64]
i=2：最小 22 (索引3) ↔ 25 → [11, 12, 22, 25, 64]
i=3：最小 25 (索引3) 無交換
i=4：單一元素無需處理
結果：[11, 12, 22, 25, 64]| 指標 | 數值 | 說明 |
|---|---|---|
| 時間複雜度 | O(n²) | 最佳/平均/最壞皆同，約 n²/2 次比較 |
| 交換次數 | O(n) | 每輪最多 1 次，共 n-1 輪 |
| 空間複雜度 | O(1) | 原地排序 |
| 穩定性 | 不穩定 | 例：[5, 5, 3] → 首輪 3 與第一個 5 交換，相對順序反轉 |
| 適應性 | 無 | 輸入有序度不影響比較次數 |
| 維度 | 冒泡排序 | 選擇排序 |
|---|---|---|
| 比較次數 | O(n²) | O(n²) |
| 交換/移動次數 | O(n²) | O(n) 優勢 |
| 穩定性 | 穩定 | 不穩定 |
| 最佳情況優化 | 旗標 O(n) | 無（仍需完整掃描） |
| 實務適用性 | 教學為主 | 寫入成本高（如 Flash/EEPROM）時優選 |
選擇排序的「每輪掃描找最小」可用 最小堆 優化為 O(log n)，整體複雜度降為 O(n log n)，即堆積排序。Java 實作可用 PriorityQueue 或手寫堆調整。
Arrays.sort()（TimSort/雙軸快排）或 Collections.sort()。選擇排序以「最少交換次數」著稱，是理解「選擇-交換」範式的經典算法。雖時間複雜度仍為 O(n²)，但其 O(n) 寫入特性在特定硬體場景具備不可替代價值。掌握其與冒泡、插入排序的異同，有助於建立完整的初級排序算法知識體系。
