排序算法（二）选择排序法

排序算法（二）选择排序法

选择排序算法和冒泡排序算法算是难兄难弟了，都是以其简单而闻名，也是在学校中我们主要学习的排序算法。但是不是不说，这个选择排序算法除了不稳定，其他都可以吊打冒泡排序算法。那现在难兄没了，只剩下这个难弟冒泡排序算法了。

选择排序法的基本介绍

选择排序法是一种不稳定的算法，也就是说相同的数据经过选择排序法之后不一定会保持原来的顺序。

选择排序法的基本思路

每次使用第一个位置的（不一定是arr[0]）和之后的数据比较，找到最小的那个数据然后两者交换。如此一来，小的数据就往数组的前面去了，数组也就变得有序了。不是我说，这个排序一看就比冒泡排序法好，因为每一轮排序只需要进行一次的交换。当然比较节省时间了。

从上图可以看出来，选择排序似乎和冒泡排序有点相似，一个是把大的数据往后边沉，一个是把小的数据往前面搬。

代码实现

    public static void selectSort(int[] arr) {
        int temp;

        for (int i = 0; i < arr.length-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

代码的几点说明：

1. i，j的作用：

   • i变量指的是数组开始排序的位置，因为每排一个序，前面就多一个数字变得有序，所以我们就没有必要动那些已经变得有序的数组了。所以说需要排序的范围就是 i 到 arr.length -1
   • j变量值的是i后面的那些数据，所以从i+1开始一直到数组的结束。i的结束的数组的倒数第二数，如果i到最后一个数的话后面已经没有数据，一个数怎么说都是有序的，所以说i没有必要到最后一个数。每次arr[i]也就是当前循环的第一个数都会与后面的arr[j]进行比较，一轮之后和最小的数进行交换然后i移动到下一个数

2. 为什么只有一次交换？

   因为minIndex变量的存在（minIndex被初始化为了i），我们可以存储找到的最小的值的下标，而不是一味的交换i与j的数据。当我们发现arr[j] < arr[minIndex]时，就把minIndex = j；因为他的值更小嘛，如此一来，我们就可以得到后面的最小值的下标了。一轮循环结束之后再进行交换（i != minIndex 如果i == minIndex那就说明if语句一直都是假的，arr[i]处的值就是最小的，没有必要和谁交换啦)。

选择排序的测试

测试环境及工具：我的电脑 Huawei MateBook 13+JDK1.8+Eclipse

测试手段：随机生成80000个[0,800000）的整数的数组进行排序，观察所花费的时间

测试代码：

public static void main(String[] args) {
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
//            arr[i] = (int) (Math.random()*800000);
            arr[i] = new Random().nextInt(800000);
        }
//        System.out.println(Arrays.toString(arr));
        long start_time = System.currentTimeMillis();
        selectSort(arr);
        long end_time = System.currentTimeMillis();
//        System.out.println(Arrays.toString(arr));
        System.out.println("Time :"+(end_time-start_time)+"ms");
}

测试结果：

1. Time: 1629ms
2. Time: 1417ms
3. Time: 1606ms

总结

选择排序法虽然和冒泡排序深处基本排序算法之列，但是选择排序的速度比冒泡排序法快的不是一点半点。虽然说冒泡排序法有稳定性上面的优势，但是同处基本排序算法的插入排序法也是稳定的，而且插入排序法的效率也蛮高的。冒泡排序。。。很危险吖~