需求

将无序数组通过方法变成有序数组

示例

[5, 1, 2, 8, 3, 9, 10, 6, 4, 7]
-------------------------------
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

思路

将数组分为两个子集，排序（左边）和未排序的（右边），每一轮从未排序的子集中选出最小的元素，放入排序子集，重复这个步骤，不断扩大有序子集，缩小无序子集，直至数组有序。

优化方式

为减少交换次数，每一轮可以先找最小的索引，在每轮最后再交换元素。

与冒泡排序比较

1. 二者平均时间复杂度都是O(n²)
2. 选择排序一般要快于冒泡，因为其交换次数少
3. 但如果集合有序度高，冒泡优先于选择
4. 冒泡属于稳定排序算法，而选择属于不稳定排序

代码

public static void selection(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int t = i;//记录最小值的下标
        for (int j = t + 1; j < arr.length; j++) {
            //寻找最小值下标
            if (arr[t] > arr[j]) {
                t = j;//更新下标
            }
        }
        //目标索引不在当前位置才交换
        if (t != i) {
            swap(arr, t, i);
        }
    }
}

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