選擇排序是最直觀的排序演算法之一：每輪從未排序區間選出最小（或最大）元素，與未排序區首位元素交換。雖時間複雜度 O(n²) 不適合大量資料，但交換次數極少 (O(n))、空間複雜度 O(1)，是教學與小規模資料的經典選擇。本文詳細解析基本版、優化版、樹形選擇排序三種變體。
i = 0 ~ n-2，代表當前待確定的位置j = i+1 ~ n-1，在剩餘元素中尋找最小值索引 minIdxminIdx != i，交換 arr[i] 與 arr[minIdx]i = n-2，最後一個元素自然就位
public class SelectionSort {
/**
* 選擇排序：升序，支援任何實作 Comparable 的型別
* @param 元素型別
* @param arr 待排序陣列（原地排序）
*/
public static <T extends Comparable<T>> void selectionSort(T[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
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].compareTo(arr[minIdx]) < 0) {
minIdx = j;
}
}
// 僅在找到更小值時交換
if (minIdx != i) {
T temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
}
// 測試用 Date 類別（實作 Comparable）
static class Date implements Comparable<Date> {
int year, month, day;
Date(int y, int m, int d) { year = y; month = m; day = d; }
@Override public int compareTo(Date o) {
if (year != o.year) return Integer.compare(year, o.year);
if (month != o.month) return Integer.compare(month, o.month);
return Integer.compare(day, o.day);
}
@Override public String toString() { return year + "-" + month + "-" + day; }
}
public static void main(String[] args) {
Date[] dates = {
new Date(2023, 5, 20),
new Date(2022, 12, 1),
new Date(2023, 1, 15),
new Date(2021, 8, 30)
};
System.out.println("排序前: " + Arrays.toString(dates));
selectionSort(dates);
System.out.println("排序後: " + Arrays.toString(dates));
}
}
| 指標 | 數值 | 說明 |
|---|---|---|
| 時間複雜度 | O(n²) | 最好/最差/平均皆同，約 n²/2 次比較 |
| 空間複雜度 | O(1) | 原地排序，僅需常數額外空間 |
| 交換次數 | 0 ~ n-1 | 最少交換排序法之一 |
| 穩定性 | 不穩定 | 相等元素相對順序可能改變 |
| 適應性 | 無 | 輸入有序度不影響比較次數 |
每輪同時找出最小值與最大值，放置於兩端，輪數減半：
public static <T extends Comparable<T>> void bidirectionalSelectionSort(T[] arr) {
if (arr == null || arr.length <= 1) return;
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].compareTo(arr[minIdx]) < 0) minIdx = i;
if (arr[i].compareTo(arr[maxIdx]) > 0) maxIdx = i;
}
// 先處理最小值
if (minIdx != left) swap(arr, left, minIdx);
// 若最大值原本在 left，交換後已移至 minIdx
if (maxIdx == left) maxIdx = minIdx;
// 再處理最大值
if (maxIdx != right) swap(arr, right, maxIdx);
left++;
right--;
}
}
private static <T> void swap(T[] arr, int i, int j) {
T tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
建立完全二元樹（錦標賽樹），葉節點為元素，內部節點儲存子樹最小值。每次取根節點（最小值），將該葉節點設為無窮大，向上更新路徑。
public static void treeSelectionSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
// 樹大小：2*n - 1 (索引 0 為根)
int[] tree = new int[2 * n - 1];
// 1. 建樹：葉節點填入資料 (索引 n-1 ~ 2n-2)
for (int i = 0; i < n; i++) {
tree[n - 1 + i] = arr[i];
}
// 內部節點自底向上計算最小值
for (int i = n - 2; i >= 0; i--) {
tree[i] = Math.min(tree[2*i + 1], tree[2*i + 2]);
}
// 2. 依序取出最小值
for (int k = 0; k < n; k++) {
arr[k] = tree[0]; // 根節點即最小值
// 找到該最小值對應的葉節點並設為 MAX_VALUE
int leafIdx = findLeaf(tree, 0, arr[k]);
tree[leafIdx] = Integer.MAX_VALUE;
// 向上更新祖先節點
updateAncestors(tree, leafIdx);
}
}
private static int findLeaf(int[] tree, int node, int target) {
if (node >= tree.length) return -1;
if (2*node + 1 >= tree.length) { // 葉節點
return tree[node] == target ? node : -1;
}
int left = findLeaf(tree, 2*node + 1, target);
if (left != -1) return left;
return findLeaf(tree, 2*node + 2, target);
}
private static void updateAncestors(int[] tree, int idx) {
while (idx > 0) {
int parent = (idx - 1) / 2;
int newVal = Math.min(tree[2*parent + 1], tree[2*parent + 2]);
if (tree[parent] == newVal) break; // 未改變可提早結束
tree[parent] = newVal;
idx = parent;
}
}
| 演算法 | 時間複雜度 | 空間複雜度 | 比較次數 | 交換/移動次數 | 適用場景 |
|---|---|---|---|---|---|
| 基本選擇排序 | O(n²) | O(1) | n(n-1)/2 | 0 ~ n-1 | 教學、小陣列、記憶體極限環境 |
| 雙向選擇排序 | O(n²) | O(1) | ~n²/2 (輪數減半) | 0 ~ n-1 | 略優於基本版，實務仍不如插入排序 |
| 樹形選擇排序 | O(n log n) | O(n) | n log n | n log n (樹更新) | 外部排序、需穩定 O(n log n) 且空間允許 |
Arrays.sort() (Dual-Pivot QuickSort / TimSort)，O(n log n) 且高度優化。選擇排序雖非高效能排序主流，但其原地、極少交換、邏輯清晰的特性使其在教學、嵌入式、外部排序啟動階段仍具價值。理解基本版、雙向優化與樹形變體的時空權衡，有助於建立演算法設計的權衡思維。
