排序算法系列(3)——直接选择排序

其实在我心中有两大最基础的简单排序，一个是关于本系列的第一个算法——冒泡排序，另外一个就是本文要讲的直接选择排序，从某种意义上，我认为直接选择排序才是本人心中最简单的排序，也是最符合正常人的思维逻辑：

1. 从N大小的数组中，找到最小的数字，把它和第1个位置的数字互换，这样我们进行第一次选择就确定了排序的第1个位置的数据。

2. 接下来，从剩下没排好序的子数组中找到最小值，与第2个位置的数据进行互换，这样确定了排序的第2个位置的数据。

按照上述方式直到排完所有的顺序……

其实，仔细想来，冒泡排序和直接选择排序的核心思想是一样的：

目的都是每轮将最小/大值放到对应队列首/尾，然后去按照同样逻辑排剩下的元素

只不过二者的实现方式不同：

冒泡排序是通过相邻两个数据互相交换的方式将极值放到列表尾/首;
而直接选择排序是直接遍历数组确定极值后将其放到列表尾/首。

下图是直接选择排序的示意图：

直接选择排序.png

代码直接贴，看到两个循环，时间复杂度果断：

    private static void straightSelectSort(int[] arrays, int start, int end) {
        for (int i = start; i < end; i++) {
            int minIndex = i;
            for (int j = i + 1; j <= end; j++) {
                if (arrays[minIndex] > arrays[j]){
                    minIndex = j;
                }
            }
            // 将[i,end]区间的最小值与i位置的值互换
            if (minIndex != i){
                swap(arrays, i , minIndex);
            }
        }
    }

同冒泡排序那样，既然讲了选择排序中一个简单的排序算法，下次就讲一个相对难一些的选择排序算法——堆排序，提前需要掌握两个知识点：完全二叉树和堆，然后堆排序也就不难了，可以理解为堆排序利用了堆这个数据结构的特性，因而使得排序更加高效，其时间复杂度为：