Java 選擇排序完整解析：逐步優化邏輯、程式碼實作與效能特徵

選擇排序核心思想

每一輪從未排序區間選出最小值，放到已排序區間末尾。透過雙層迴圈實現：

• 外層迴圈：控制輪數 (已排序區間邊界)
• 內層迴圈：在未排序區間尋找最小值索引
• 交換：將最小值與未排序區間首位元素交換

邏輯逐步優化演示

版本一：朴素雙層迴圈 (含冗餘比較)

for (int x = 0; x < arr.length; x++) {
    for (int y = 0; y < arr.length; y++) {
        if (arr[x] > arr[y]) { /* 交換 */ }
    }
}
// 問題：內層掃描整個陣列，包含已排序區，重複比較

版本二：內層從 x+1 開始 (排除已排序區)

for (int x = 0; x < arr.length; x++) {
    for (int y = x + 1; y < arr.length; y++) {
        if (arr[x] > arr[y]) { /* 交換 */ }
    }
}
// 問題：外層最後一輪 x = length-1 時，內層不執行，但外層仍多跑一次

版本三：外層到 length-1 (最終優化形態)

for (int x = 0; x < arr.length - 1; x++) {      // 最後一個元素自然就位，無需處理
    for (int y = x + 1; y < arr.length; y++) {  // 只掃描未排序區
        if (arr[x] > arr[y]) {
            // 交換邏輯
            int temp = arr[x];
            arr[x] = arr[y];
            arr[y] = temp;
        }
    }
}

完整可執行程式碼 (Java + PHP)

Java 版

public class SelectionSortDemo {
    public static void main(String[] args) {
        int[] arr = {2, 5, 4, 1};
        int[] sorted = selectionSort(arr);
        System.out.print("排序結果: ");
        for (int n : sorted) System.out.print(n + " "); // 1 2 4 5
    }
    
    public static int[] selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
}

PHP 版

<?php
class ArrayDemo {
    public static function main() {
        $arr = [2, 5, 4, 1];
        print_r(self::selectionSort($arr)); 
        // Array ( [0] => 1 [1] => 2 [2] => 4 [3] => 5 )
    }
    
    public static function selectionSort($arr) {
        for ($i = 0; $i < count($arr) - 1; $i++) {
            for ($j = $i + 1; $j < count($arr); $j++) {
                if ($arr[$i] > $arr[$j]) {
                    $temp = $arr[$i];
                    $arr[$i] = $arr[$j];
                    $arr[$j] = $temp;
                }
            }
        }
        return $arr;
    }
}
ArrayDemo::main();

效能特徵分析

進階優化：減少陣列存取 (記錄索引而非直接交換)

public static void selectionSortOptimized(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;  // 只記錄索引，不交換
            }
        }
        if (minIndex != i) {   // 單輪結束只交換一次
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

優勢：減少陣列寫入操作，對於「寫入成本高」的儲存介質 (如 EEPROM、某些快取場景) 有實質幫助。

何時使用選擇排序？

• ✅ 教學示範、理解排序基本原理
• ✅ 极小資料量 (n < 50)
• ✅ 記憶體寫入極其昂貴的特殊硬體環境
• ❌ 一般生產環境：請使用 Arrays.sort() (Dual-Pivot Quicksort + TimSort，O(n log n))
• ❌ 大量資料、即時系統、穩定性要求場合

排序演算法速查