Java 經典排序：選擇排序原理、優化與完整實作

算法核心思想

選擇排序 每輪從未排序區間選出最小（或最大）元素，與區間首位交換。第 i 輪處理 arr[i...n-1]，共需 n-1 輪。

執行流程圖解

陣列：[5, 2, 8, 4, 9, 1]

1. 第 1 輪：全範圍最小值 1，與索引 0 交換 → [1, 2, 8, 4, 9, 5]
2. 第 2 輪：索引 1~5 最小值 2，已在正確位置 → [1, 2, 8, 4, 9, 5]
3. 第 3 輪：索引 2~5 最小值 4，與索引 2 交換 → [1, 2, 4, 8, 9, 5]
4. 第 4 輪：索引 3~5 最小值 5，與索引 3 交換 → [1, 2, 4, 5, 9, 8]
5. 第 5 輪：索引 4~5 最小值 8，與索引 4 交換 → [1, 2, 4, 5, 8, 9]

優化實作：減少交換次數

public class SelectionSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) minIdx = j;
            }
            if (minIdx != i) swap(arr, i, minIdx); // 僅在必要時交換
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

複雜度分析

與冒泡排序比較

• 選擇排序交換次數遠少於冒泡排序（O(n) vs O(n²)），適合「寫入成本高」的存儲介質（如 EEPROM、Flash）。
• 兩者時間複雜度同階，但選擇排序因固定比較次數，在近乎有序資料上無優勢（冒泡優化版可達 O(n)）。

變體：堆排序

利用二元堆結構將「選出最小值」從 O(n) 降為 O(log n)，整體時間複雜度達 O(n log n)，是選擇排序的高效進化版。