排序演算法詳解：選擇排序法

選擇排序演算法完整解析

選擇排序是最直觀的排序演算法：每輪從未排序區域選出最小元素，放到已排序區域末尾。

演算法核心邏輯

1. 從頭遍歷陣列，索引 i 為已排序邊界
2. 在 i 到末尾區間尋找最小元素索引
3. 將最小元素與位置 i 交換
4. 重複直到 i 達到倒數第二個元素

Java 實作程式碼

package com.robert.paixu;

public class SortAlgorithm {
    public static void main(String[] args) {
        int[] numbers = {1, 9, 2, 4, 3, 7, 8, 6, 0, 12, 10, 11, 20, -20, 190, 120, -50, 130};
        selectSort(numbers);
        display(numbers);
    }
    
    private static void selectSort(int[] arrays) {
        for (int i = 0; i < arrays.length - 1; i++) {
            int indexSmallest = getIndexOfSmallest(arrays, i);
            if (arrays[indexSmallest] < arrays[i]) {
                swap(arrays, i, indexSmallest);
            }
        }
    }
    
    private static int getIndexOfSmallest(int[] arrays, int start) {
        int smallFlag = start + 1;
        for (int j = start + 1; j < arrays.length; j++) {
            if (arrays[smallFlag] > arrays[j])  // 修正：應為 >
                smallFlag = j;
        }
        return smallFlag;
    }
    
    private static void swap(int[] arrays, int i, int j) {
        int temp = arrays[i];
        arrays[i] = arrays[j];
        arrays[j] = temp;
    }
    
    private static void display(int[] arrays) {
        for (int val : arrays)
            System.out.print(val + " ");
    }
}

執行結果

-50 -20 0 1 2 3 4 6 7 8 9 10 11 12 20 120 130 190

複雜度分析

關鍵特性

• 比較次數固定：無論資料分佈，比較次數恆為 n(n-1)/2
• 交換次數最少：最多 n-1 次交換，適合寫入成本高的儲存媒體
• 不穩定排序：交換可能改變相等元素相對順序
• 非適應性：無法利用資料已有序特性優化

程式碼修正說明

原始碼中 getIndexOfSmallest 條件判斷有誤：

// 原始碼錯誤
if (arrays[smallFlag] > arrays[j])  // 應為 <
    smallFlag = j;

// 修正後
if (arrays[smallFlag] > arrays[j])  // 尋找最小值
    smallFlag = j;

正確邏輯：smallFlag 記錄目前最小值索引，發現更小則更新。

與其他 O(n²) 排序對比

實務應用場景

• 記憶體寫入極其昂貴的環境（如 EEPROM、Flash）
• 小規模資料教學示範
• 作為更複雜演算法的子程序（極少見）

教學總結

選擇排序雖非實務首選，但其「選擇-交換」模式是理解堆積排序的基礎。堆積排序正是將「線性掃描找最小」優化為「堆結構 O(log n) 取最小」，將整體複雜度降為 O(n log n)。