選擇排序屬於原地比較排序，基本邏輯：
特點：交換次數最少（最多 n-1 次），但比較次數固定為 n(n-1)/2，與數據初始狀態無關。
| 指標 | 複雜度 | 說明 |
|---|---|---|
| 時間複雜度 | O(n²) | 最好/最壞/平均均為 O(n²)，雙層循環固定比較 |
| 空間複雜度 | O(1) | 僅需常數額外空間（交換臨時變量、索引記錄） |
| 穩定性 | 不穩定 | 相等元素可能因交換改變相對順序（如 [5a, 5b, 3] → [3, 5b, 5a]） |
| 適應性 | 無 | 無法利用數據有序度特性優化 |
public static void selectionSortAsc(int[] arr) {
int n = arr.length;
int compareCount = 0, swapCount = 0;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
// 尋找 [i+1, n-1] 中最小元素索引
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
compareCount++;
}
// 交換
if (minIdx != i) {
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
swapCount++;
}
}
System.out.printf("升序: 比較%d次, 交換%d次%n", compareCount, swapCount);
}
public static void selectionSortDesc(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int maxIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] > arr[maxIdx]) maxIdx = j;
}
if (maxIdx != i) swap(arr, i, maxIdx);
}
}
// 不使用臨時變量交換（僅整數適用，生產不推薦，可讀性差）
arr[i] = arr[minIdx] + (arr[minIdx] = arr[i]) * 0;
數組：[56, 12, 80, 91, 20]
第1輪: 最小值12(索引1) ↔ 56(索引0) → [12, 56, 80, 91, 20]
第2輪: 最小值20(索引4) ↔ 56(索引1) → [12, 20, 80, 91, 56]
第3輪: 最小值56(索引4) ↔ 80(索引2) → [12, 20, 56, 91, 80]
第4輪: 最小值80(索引4) ↔ 91(索引3) → [12, 20, 56, 80, 91]
完成
原始: [125, 350, 648, 789, 319, 699, 855, 755, 552, 489, 187, 916, 596, 731, 852]
降序: 比較26次, 交換13次 → [916, 855, 852, 789, 755, 731, 699, 648, 596, 552, 489, 350, 319, 187, 125]
升序: 比較56次, 交換7次 → [125, 187, 319, 350, 489, 552, 596, 648, 699, 731, 755, 789, 852, 855, 916]
觀察：降序比較次數少是因為實現中 if (arr[maxIdx] < arr[j]) 只有滿足條件才計數，升序每次循環都計數。實際比較次數固定為 n(n-1)/2 = 105 次。
每輪同時找最小和最大，放到兩端，輪數減半：
public static void bidirectionalSelectionSort(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int minIdx = left, maxIdx = right;
for (int i = left; i <= right; i++) {
if (arr[i] < arr[minIdx]) minIdx = i;
if (arr[i] > arr[maxIdx]) maxIdx = i;
}
swap(arr, left, minIdx);
// 若最大值原在 left 位置，交換後已移到 minIdx
if (maxIdx == left) maxIdx = minIdx;
swap(arr, right, maxIdx);
left++; right--;
}
}
利用堆結構將「尋找極值」從 O(n) 優化到 O(log n)，整體 O(n log n)；本質是選擇排序的優化版。
將數組分塊，並行尋找各塊極值，再合併；適用於多核環境大數據排序。
| 算法 | 平均時間 | 最好時間 | 交換/移動次數 | 穩定性 | 適用場景 |
|---|---|---|---|---|---|
| 選擇排序 | O(n²) | O(n²) | 最少 (≤n) | 不穩定 | 交換代價極大、內存寫入受限場景 |
| 冒泡排序 | O(n²) | O(n) | 多 | 穩定 | 教學、近乎有序數據 |
| 插入排序 | O(n²) | O(n) | 移動而非交換 | 穩定 | 小數據量、近乎有序、在線排序 |
Arrays.sort() (Dual-Pivot QuickSort) 或 Collections.sort() (TimSort)，O(n log n) 且高度優化選擇排序以「最小交換次數」為核心優勢，但 O(n²) 時間複雜度限制了實際應用範圍。理解其「固定比較、最少交換、不穩定」特性，掌握雙向優化思路，能幫助構建算法直覺。實際開發中，優先使用語言內置排序（TimSort/QuickSort 變體），僅在極特定約束場景（如寫入受限存儲介質）考慮選擇排序或其變體。
