简单选择排序介绍

简单选择排序法就是通过n-i次关键字比较，找到最小的关键字下标，最后在替换n-i下标和最小下标的值。
简单排序的思想和冒泡排序的思想的区别是冒泡排序是相邻关键字两两比较，如果小，则直接替换，可能在一轮循环会进行多次值交换。而简单选择排序法是一轮循环找到最小关键字下标，最后进行最多一次替换。

简单选择排序算法

    public static void simpleSelectionSort(Integer[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i;//初始最小关键字下标为i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] > arr[j]) { // 如果前一个元素比后一个元素大，则替换位置
                    min = j;
                }
            }
            if (min != i) {//如果一轮比较下来，最小下标和当前i下标不一致，则替换值
                Integer temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }

假设需要对关键字序列{9,3,8,2,7,4,6,1,5}使用简单选择排序，如下图：

如上面图的流程所示，当i=0,j=1,min=0时，进行比较[min]>[j]，所以min=1。当j=3时，[min]>[j]，所以min=3。当j=7时，[min]>[j]，所以min=7。最后替换min下标和i下标的值，也就是把找到的最小关键字和第一位替换。同理，然后进行下一个最小关键字的轮询比较替换。

时间复杂度

最好的情况和最差情况比较次数相同。第i趟排序需要进行n-i次比较，总共需要比较$\frac{n(n-1)}{2}$次。
对于交换来说，最好情况，不需要交换。最差情况也就是逆序时，需要交换n-1次。
最终的时间复杂度为O($n^2$)。

和冒泡排序的性能比较

前面有说冒泡排序一轮比较大小可能会多次大小值替换，而简单选择排序每次轮询只需要进行最多一次值替换。接下来我们就来看下序列长度为10万个随机数，分别用冒泡和简单选择两种算法执行时间需要多久。

    public static void main(String[] args) {
        Integer[] arrs = new Integer[100000];
        Random random = new Random();
        for (int i = 0; i < arrs.length; i++) {
            arrs[i]=random.nextInt(arrs.length);
        }
        Integer[] newArrays = Arrays.copyOf(arrs, arrs.length);
        long start = System.currentTimeMillis();
        simpleSelectionSort(newArrays);
        long end = System.currentTimeMillis();
        System.out.println("简单选择排序执行时间:"+(end-start)+"ms");

        newArrays = Arrays.copyOf(arrs, arrs.length);
        start = System.currentTimeMillis();
        bubbleSort(newArrays);
        end = System.currentTimeMillis();
        System.out.println("冒泡排序执行时间:"+(end-start)+"ms");
    }

    public static void simpleSelectionSort(Integer[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i;//初始最小关键字下标为i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] > arr[j]) { // 如果前一个元素比后一个元素大，则替换min值
                    min = j;
                }
            }
            if (min != i) {//如果一轮比较下来，最小下标和当前i下标不一致，则替换值
                Integer temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }

    public static void bubbleSort(Integer[] arr) {
        boolean flag = true; //flag标记是否需要继续循环
        for (int i = 0; i < arr.length && flag; i++) {//每一轮循环进行flag判断
            flag = false;
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j - 1] > arr[j]) { // 如果前一个元素比后一个元素大，则替换位置
                    Integer temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                    flag = true; //有数据交换则将flag置为true
                }
            }
        }
    }

最终得到的结果如下：

简单选择排序执行时间:7455ms
冒泡排序执行时间:28337ms

我们发现当数量比较大的无序序列进行排序时，简单选择排序相较于冒泡排序省去了大量的值替换操作，所以耗时比冒泡要少的多。所以，我们得出的结论是简单选择排序比冒泡排序的性能要优。