選擇排序法 Java 實作與泛型支援

演算法原理

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

泛型實作（支援任意 Comparable）

package utils.sort;

public class ChooseSort implements SortStrategy {
    @Override
    public void sort(Comparable[] obj) {
        if (obj == null) {
            throw new NullPointerException("The argument can not be null!");
        }
        for (int i = 0; i < obj.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < obj.length; j++) {
                if (obj[minIndex].compareTo(obj[j]) > 0) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                Comparable tmp = obj[i];
                obj[i] = obj[minIndex];
                obj[minIndex] = tmp;
            }
        }
    }
}

介面定義

package utils.sort;

public interface SortStrategy {
    void sort(Comparable[] array);
}

使用範例

Integer[] arr = {5, 2, 9, 1, 5, 6};
new ChooseSort().sort(arr);
// arr → [1, 2, 5, 5, 6, 9]

String[] names = {"Bob", "Alice", "Charlie"};
new ChooseSort().sort(names);
// names → ["Alice", "Bob", "Charlie"]

關鍵點解析

1. Comparable 介面：元素需實作 compareTo，回傳負/零/正代表小於/等於/大於。
2. 原地交換：僅使用單一暫存變數 tmp，空間複雜度 O(1)。
3. 防呆檢查：null 陣列直接拋出 NullPointerException。
4. 優化：若 minIndex == i 則略過交換，減少指令數。

常見排序法比較

實務建議

• 教學/極小資料量（n < 50）→ 選擇排序可接受。
• 生產環境請直接使用 Arrays.sort() 或 Collections.sort()（TimSort，O(n log n)、穩定、高度優化）。
• 需自訂比較邏輯時，傳入 Comparator 而非修改元素類別。