Java 排序算法：選擇排序原理與實現詳解

算法思想

選擇排序每輪從未排序區間選出最小（或最大）元素，放到已排序區間末尾。直觀簡單，且交換次數最少（最多 n-1 次），適合「寫入代價高」的存儲介質。

複雜度分析

Java 完整實現

package com.baobaotao.test;

public class Sort {

    /** 選擇排序 */
    public static void selectSort(int[] array) {
        int length = array.length;
        for (int i = 0; i < length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
            printArr(array); // 觀察每輪變化
        }
    }

    public static void swap(int[] a, int i, int j) {
        if (i == j) return;
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void printArr(int[] array) {
        for (int v : array) System.out.print(v + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] number = {11, 95, 45, 15, 78, 84, 51, 24, 12};
        selectSort(number);
    }
}

運行輸出示例

11 95 45 15 78 84 51 24 12
11 12 45 15 78 84 51 24 95
11 12 15 45 78 84 51 24 95
11 12 15 24 78 84 51 45 95
11 12 15 24 45 84 51 78 95
11 12 15 24 45 51 84 78 95
11 12 15 24 45 51 78 84 95
11 12 15 24 45 51 78 84 95

優化方向

• 雙向選擇排序：每輪同時選出最小和最大，放到兩端，趟數減半。
• 堆排序：利用堆結構將選擇最小元素從 O(n) 降為 O(log n)，整體達到 O(n log n)。

總結

選擇排序雖時間複雜度較高，但「最小交換次數」特性在特定場景（如 EEPROM 寫入、大對象移動）仍有價值。它也是理解堆排序的基石。