排序算法之选择排序

选择排序的基本原理：
对于给定的数组，经过一轮的比较火的最小的数，并将该数的位置和第一个数的位置进行交换；然后对不包含第一个数的其他数继续进行比较并进行位置的交换，一直重复到只有一个数为止。

示例：[9, 1, 8, 3, 6, 2, 7]
i=0 arr[i] = 9 temp=9 index = 0
开始比较，9 > 1 temp = 1, index = 1,
…
后面的都比 temp=1 大；所以第一轮比较 temp=1，index=1，即最小值，
那么交换和 arr[i] 的位置
…
第一轮 [1, 9, 8, 3, 6, 2, 7]

第二轮 [1, 2, 8, 3, 6, 9, 7]
第三轮 [1, 2, 3, 8, 6, 9, 7]
第四轮 [1, 2, 3, 6, 8, 9, 7]
第五轮 [1, 2, 3, 6, 7, 9, 8]
第六轮 [1, 2, 3, 6, 7, 8, 9]
第七轮 [1, 2, 3, 6, 7, 8, 9]

public class SelectSort {

    public static void sort(int[] arr) {
        int temp = 0; // temp 保存最小的值
        int index = 0; // 保存 最小值 temp 的索引位置
        // 共有n轮循环
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            temp = arr[i]; // 保存当前的最小值
            index = i; // 记录最小值的位置
            // 开始遍历，寻找最小值
            // 从第 i+1 个开始
            for (int j = i + 1; j < n; j++) {
                // 如果有比 temp 小的值，就将当前值给到temp值，即当前的最小值
                if (temp > arr[j]) {
                    index = j;
                    temp = arr[j];
                }
            }
            // 一轮比较之后，如果最小值的索引不等于当前的索引值的话，说明要交换位置
            if (index != i) {
                // 交换位置 swap
                arr[index] = arr[i];
                arr[i] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[] { 9, 1, 8, 3, 6, 2, 7 };
        sort(arr);
    }
}

最后我们看一下算法的时间复杂度，为 O(n^2)，空间复杂度为O(1)，
是一个不稳定的算法，因为如果存在两个相同的值在数组中，经过比较后相同的两个值中，后面的值有可能跑到前面去。

按照找最小值，与无序区首部交换的思想则不稳定：
排序前：
2,4,4*，3
排序后：
2,3,4*，4