简单选择排序

简单选择排序法(Simple Selection Sort) 就是通过n - i 次关键字间的比较，从n-j+1个记录中选出关键字最小的记录，并和第i (1 <= i <= n) 个记录交换之。

图1 简单选择排序

简单选择排序如图1所示：
初始状态：i从第一位0开始，先把i=0设置为最小值下标min。j从i+1的位置开始遍历，依次与最小值下标min对应的数据对比，找到真正的最小值j=3，并把j=3设置为最小值下标min。然后交互i=0和min=3下标对应的数字。
第一轮排序：交互完成后，i从第二位1开始，把i=1设置为最小值下标min。j从i+1的位置开始遍历，依次与最小值下标min对应的数据对比，找到真正的最小值j=3，并把j=3设置为最小值下标min。然后交互i=1和min=3下标对应的数字。
不断重复上述步骤，直到排序完成！

代码实现：

//简单选择排序
private static int[] selectSort(int[] a) {
    for(int i=0; i<a.length; i++){
        int temp;
        //将当前下标定义为最小值下标
        int min = i;

        //从i的后一位开始遍历
        for(int j=i+1; j<a.length; j++) {
            //如果之前定义的最小值下标大于之后的数，将新的最小值下标赋值给min
            if (a[min] > a[j]) {
                min = j;
            }
        }
        //找到此轮最小值，与a[i]交换
        temp = a[min];
        a[min] = a[i];
        a[i] = temp;
    }
    return a;
}

public static void main(String[] args) {
    int[] a = {1, 4 , 6, 0, 3, 2, 5, 9};
    int[] b = selectSort(a);
    System.out.print("Select sort:\n");
    for(int i=0; i<a.length; i++) {
        System.out.print(b[i] + ", ");
    }

输出结果

Select sort:
0, 1, 2, 3, 4, 5, 6, 9,

时间复杂度 O（n^2）