Java 排序算法總結：選擇排序原理與優化實現

選擇排序核心思想

選擇排序將數組分為「已排序區」（前部）與「未排序區」（後部）。每輪從未排序區中選出最小（或最大）元素，與未排序區首位元素交換，擴大已排序區。重複 n-1 輪完成排序。

算法特性

• 時間複雜度：固定 O(n²)，無論數據分佈。
• 空間複雜度：O(1)，原地排序。
• 穩定性：不穩定，交換操作可能改變相等元素相對順序。
• 交換次數：最少，僅 O(n) 次交換，適合寫入成本高的存儲介質。

Java 基礎實現

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) {
                int temp = arr[i];
                arr[i] = arr[minIdx];
                arr[minIdx] = temp;
            }
        }
    }
}

優化變體

雙向選擇排序

每輪同時選出最小值放前端、最大值放後端，將外層循環次數減半：

public static void bidirectionalSelectionSort(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int minIdx = left, maxIdx = right;
        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[minIdx]) minIdx = i;
            if (arr[i] > arr[maxIdx]) maxIdx = i;
        }
        swap(arr, left, minIdx);
        // 若 maxIdx 原本在 left 位置，交換後已移至 minIdx
        if (maxIdx == left) maxIdx = minIdx;
        swap(arr, right, maxIdx);
        left++;
        right--;
    }
}

堆排序本質

堆排序可視為選擇排序的優化版：利用堆結構將「尋找最值」從 O(n) 降為 O(log n)，整體複雜度達 O(n log n)。

適用場景與總結

選擇排序因固定 O(n²) 很少用於大規模數據，但其「最小交換次數」特性使其在 EEPROM/Flash 寫入、數組元素巨大（交換代價高）等特定場景有優勢。教學中常作為原地不穩定排序的典型代表。