选择排序

核心思想：将数据分为 “未排序区间” 和 “已排序区间”，每次在“未排序区间”找到最小的元素，追加到已排序区间的末尾。

如下图所示：

初始数组 「4，5，2，1，3」；

初始，未排序区间大小为 0， 从 0 开始，遍历数组，找到最小元素，放在 0 的位置。

第二次，从下标 1 开始，找最小的元素，放到 1 的位置。

…..

代码：

public class 选择排序 {

    public static void main(String[] args) {
        int[] arr = {5, 1, 11, 2, 0, 6, 9, 4};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int index = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[index] > arr[j]) {
                    index = j;
                }
            }
            int tmp = arr[index];
            arr[index] = arr[i];
            arr[i] = tmp;
        }
    }
}

排序三问

1 是原地排序吗

选择选择，顾名思义，就是每次选择最小的，然后追加到“已排序区间” 的末尾。没有使用其他的恐惧，所以，是原地排序算法。

2 是稳定的排序吗

假设现在有一组数据 {2,3,2,4,5,1,0,7};

我们先将 0 和 1 放到了正确的位置，注意，第一个 2 的位置 和 第二个 2 的位置就变了，所以，就不稳定了。

正因为如此，选择排序，相对于冒泡和插入，显得不那么厉害了。

3 种时间复杂度是多少？

最好时间复杂度，如果本身就是有序的，时间复杂度是 线性 On。

最坏时间复杂度，如果是满逆序的，时间 复杂度是指数级的，On^2.

平均时间复杂度，如果数据有序度为 满有序度/2， 时间复杂度是多少呢？我们看上面，可以知道，选择排序，每次都会找到一个最小的值，这次遍历可以认为是 On，n 次 On，就是 On^ ， 因此，他的时间复杂度是 On^2.