排序算法（一）：選擇排序 Java 實現與複雜度分析

算法思想

1. 從頭到尾遍歷數組。
2. 每輪在未排序部分找到最小元素，與當前位置交換。

Java 實現

[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);
            }
        }
    }

    // 從 i 開始找最小元素下標
    private static int getIndexOfSmallest(int[] arrays, int i) {
        int smallFlag = i + 1;
        for (int j = i + 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 v : arrays) System.out.print(v + " ");
    }
}

輸出結果

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

複雜度分析

• 時間：O(n²)（最好/最壞/平均皆然），因雙重循環固定執行 n(n-1)/2 次比較。
• 空間：O(1)，原地排序。
• 穩定性：不穩定（交換可能改變相等元素相對順序）。

適用場景

數據量小（n < 50）、不要求穩定、簡單易實現的場合。