Java 選擇排序算法原理與完整實現教程

算法思想

選擇排序是一種簡單直觀的交換排序，可視為冒泡排序的改進。核心思路：每一輪從無序區選出最小（或最大）元素，與無序區首位元素交換，逐步擴大有序區。

步驟如下（以升序為例）：

1. 第一輪：從索引 0 開始，遍歷全數組找到最小值的索引 min，若 min != 0 則交換 arr[0] 和 arr[min]。
2. 第二輪：從索引 1 開始，在剩餘無序區尋找最小值，交換到索引 1。
3. 重複上述過程，共需 n-1 輪，最後一個元素自然是最大值。

時間複雜度：O(n²)（最好/最壞/平均均為此），空間複雜度 O(1)，不穩定排序（相同值可能因交換改變相對順序）。

Java 完整實現

數組封裝類 SelectArray

package ch02;

public class SelectArray {
    private long[] arr;
    private int elems; // 有效元素數量

    public SelectArray() { this(50); }
    public SelectArray(int max) { arr = new long[max]; }

    public void insert(long value) { arr[elems++] = value; }

    public void display() {
        for (int i = 0; i < elems; i++) System.out.print(arr[i] + " ");
        System.out.println();
    }

    /** 選擇排序核心邏輯 */
    public void selectSort() {
        for (int i = 0; i < elems - 1; i++) {
            int min = i;
            for (int j = i + 1; j < elems; j++) {
                if (arr[j] < arr[min]) min = j;
            }
            // 交換
            long tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }
}

測試類

package ch02;

public class TestSelectArray {
    public static void main(String[] args) {
        SelectArray sArr = new SelectArray();
        sArr.insert(89);
        sArr.insert(54);
        sArr.insert(667);
        sArr.insert(7);
        sArr.insert(12);
        sArr.insert(43);
        sArr.insert(12);

        System.out.println("排序前：");
        sArr.display();

        sArr.selectSort();

        System.out.println("排序後：");
        sArr.display();
    }
}

輸出結果

排序前：
89 54 667 7 12 43 12 
排序後：
7 12 12 43 54 89 667 

關鍵點解析

• 雙重循環：外層控制輪數（n-1），內層在無序區尋找極值索引。
• 交換優化：僅當 min != i 時才交換，減少無謂操作（代碼中省略此判斷，實際建議加上）。
• 泛型擴展：可改用 Comparable<T> 支持任意可比較類型。

適用場景

數據量較小（n < 50）、對穩定性無要求、內存受限的嵌入式環境。大數據量請改用快速排序、歸併排序或系統內置 Arrays.sort()。