排序算法：选择排序

以升序为例，选择排序就是选出最小的元素排最左边，然后在剩下的元素里再继续选出最小的元素排刚刚元素的右边。

实现

java实现

/**
 * 选择排序
 */
public static void selectSort(int[] arr) {
    // 从位置0开始，获取最小的元素放位置0，然后从位置1开始获取最小的元素放位置1
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            // 如果碰到比arr[minIndex]还小的元素，就把minIndex更新为更小元素的位置坐标
            if (arr[minIndex] > arr[j]) {
                minIndex = j;

            }
        }
        // 如果minIndex不等于i说明被更新了，有最小元素存在，交换元素的值
        if (minIndex != i) {
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

不管是原数组是有序还是无序，都需要进行每一次比较，所以时间复杂度都是一样的。计算一下，外层是n-1次，内层的循环刚开始是从1到n-1,也就是遍历n-1次，然后n-2次，然后是n-3次……时间复杂度是1+2+3+……+(n-2) +(n-1)= (n-1+1)×(n-1)/2，很显然最大幂次也是n²，所以时间复杂度恒定是O(n²)，这和冒泡排序不同，冒泡排序最好情况是O(n)。选择排序是原地排序，空间复杂度为O(1)。

关于稳定性，如果存在两个相等的元素，那么左边的会先被选择，最后还是会放在左边，所以选择排序是稳定的。如果这么想的话，就错了，实际上选择排序是不稳定的，因为交换会破坏稳定性，举个例子，

有个数组[5, 8, 5, 2, 9]，为了区分，标记为[5A, 8, 5B, 2, 9]

第一次遍历后，数组变为了[2, 8, 5B, 5A, 9]

原来左边的5跑到了右边，所以选择排序是不稳定的。

总结

时间复杂度：O(n²)

空间复杂度：O(1)

稳定性：不稳定