選擇排序算法原理與 Java 實現詳解

算法核心思想

選擇排序：每輪從未排序區間選出最小(大)元素，與未排序區間首位元素交換。時間複雜度 O(n²)，空間 O(1)，不穩定。

圖解演示 (以升序為例)

初始: [64, 25, 12, 22, 11]
第1輪: 選最小 11 ↓ 交換 64 → [11, 25, 12, 22, 64]
第2輪: 選最小 12 ↓ 交換 25 → [11, 12, 25, 22, 64]
第3輪: 選最小 22 ↓ 交換 25 → [11, 12, 22, 25, 64]
第4輪: 選最小 25 ↓ 交換 25 → [11, 12, 22, 25, 64] (已有序)
完成: [11, 12, 22, 25, 64]

Java 標準實現

public class SelectionSort {
    // 升序
    public static void sort(int[] arr) {
        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] < arr[minIdx]) minIdx = j;
            }
            // 交換 (若 minIdx != i)
            if (minIdx != i) {
                int tmp = arr[i];
                arr[i] = arr[minIdx];
                arr[minIdx] = tmp;
            }
        }
    }
    
    // 降序 (只需改比較方向)
    public static void sortDesc(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int maxIdx = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] > arr[maxIdx]) maxIdx = j;
            }
            if (maxIdx != i) swap(arr, i, maxIdx);
        }
    }
    
    private static void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
    
    // 泛型版 (支援 Comparable)
    public static > void sort(T[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j].compareTo(arr[minIdx]) < 0) minIdx = j;
            }
            if (minIdx != i) swap(arr, i, minIdx);
        }
    }
    
    private static  void swap(T[] a, int i, int j) {
        T t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

性能分析

優化變體

• 雙向選擇排序：每輪同時選最小放左端、最大放右端，循環次數減半 (仍 O(n²))。
• 堆排序：用堆結構優化「找最小」為 O(log n)，總體 O(n log n) — 選擇排序的進化終極形態。

適用場景

• 數據量極小 (n < 50)。
• 記憶體極其受限 (嵌入式系統)。
• 交換操作極其昂貴 (如 EEPROM 寫入)，選擇排序交換次數最少。
• 教學演示排序基本原理。

對比：為什麼實際開發不用它？

// Java 內建排序 (雙軸快排 + 歸併 + 插入排序混合)
Arrays.sort(arr);           // 基本類型：Dual-Pivot Quicksort
Arrays.sort(objArr);        // 物件：TimSort (歸併+插入)，穩定、O(n log n)
Collections.sort(list);     // 同 Arrays.sort

JDK 排序在實際數據分佈下表現遠超 O(n²) 算法，且經過極致優化 (內部函數、分支預測、緩存友好)。