Java——简单选择排序

简单选择排序基本思想：第一趟，从n个元素中找出关键字最小的元素与第一个元素交换；第二趟，在从第二个元素开始的n-1个元素中在选出关键字最小的元素与第二个元素交换；如此，第k趟，则从第k个元素开始的n-k+1个元素中选出关键字最小的元素与第k个元素交换，直到整个序列按关键字有序。

public static void test2(int[] r) {
        for(int i = 1;i < r.length;i++) {
            int j = i - 1;
            int min = r[j]; //默认第一项是最小的元素
            for(;j<r.length;j++) {
                if(min > r[j]) {//查找剩下的元素的最小值
                    int temp = min;
                    min = r[j];
                    r[j] = temp;
                }
            }
            r[i-1] = min; //把最小值赋值给第一项
        }
    }

空间效率：显然简单选择排序是需要一个辅助空间

时间效率：再简单选择排序中，所需移动元素的次数较少，在排序序列已经有序的情况下，简单选择排序不需要移动元素，在最坏的情况下，即待排序序列本身是逆序时，则移动元素的次数为3(n-1).然而无论简单选择排序过程中移动元素的次数多少，在任何情况下，简单选择排序都需要进行n(n-1)/2次比较操作，因此简单选择排序的时间复杂度O(n2)

其实，基于这个简单选择排序，我们可以深入思考一下，这个算法的改进空间。。后期我会跟进的。。。。