开篇

上篇我们好好聊了聊冒泡排序，这篇我们来聊聊另一种初级排序算法——选择排序

正文

选择排序的算法思路同样很简单。还是数组为例，我们现在有个整数数组，要求将其中整数元素按值的大小从小到大排个序。选择排序的具体思路是这样：先从头遍历数组，找出其中值最小的那个元素，然后将其值同遍历区间最开始那个元素交换，如果值最小的元素恰是最开始那个元素，就自己跟自己交换值。第一遍遍历完成，数组中最小的值已经是数组第一个元素，此时数组第一个元素已部分有序，将重新遍历的初始下标加一，开始下次遍历，如此循环，直至遍历区间内只剩一个元素，此时数组已整体有序。

来具象化捋一遍选择排序的逻辑：

``

    /*
    设现有无序数组 a = [40, 50, 20, 30, 10]
    其有序状态应为 a = [10, 20, 30, 40, 50]
    我们对其做下选择排序，具象展示如下：
数组下标：a[0]　　a[1]　　a[2]　　a[3]　　a[4]
初始值：　40　　　50　　　20　　　 30　　　10　　

第一次选择遍历过程： 40　　　50　　　20　　　30　　　10  (遍历区间值最小元素为a[4],
                    ↑                             ↑  与遍历区间初始下标a[0]交换值)
                   
第二次选择遍历过程： 10　　　50　　　20　　　30　　　40  (最小元素为a[2],与a[1]交换值，
                   ---     ↑       ↑                 下划线标示的元素已部分有序)

第三次选择遍历过程： 10　　　20　　　50　　　30　　　40  (最小元素为a[3],与a[2]交换值，
                   ----------      ↑      ↑          下划线标示的元素已部分有序)
                   
第四次选择遍历过程： 10　　　20　　　30　　　50　　　40  (最小元素为a[4],与a[3]交换值，
                   ------------------     ↑      ↑   下划线标示的元素已部分有序)
                   
第五次选择遍历过程： 10　　　20　　　30　　　40　　　50  (遍历区间内只剩一个元素了，
                   -------------------------     ↑↑   表明此时数组已整体有序)
                   
数组此时已整体有序： 10　　　20　　　30　　　40　　　50  (数组此时已整体有序）
                   --------------------------------
                    
*/

OK 逻辑捋的差不多了我们开始撸代码，以 Java 为例，我们先来撸个为整数数组选择排序的递归实现版本：

/**
     * @see: 选择排序的递归实现
     * @param array: 待排序数组，我们采用原地排序
     * @param start: 当次查找最小值（遍历区间）的初始下标，初次调用值应为0
     */
    public static void sortSelect(int[] array, int start){
        //递归结束条件，此时数组已整体有序
        if (start >= array.length - 1){
            return;
        }

        //先假定遍历区间第一个下标的值为最小值;
        int minValueIndex = start;
        //开始遍历特定数组区间，将区间内最小值交换到区间初始位置
        for (int i = start + 1; i <= array.length - 1; i ++){
            if (array[i] < array[minValueIndex]){
                minValueIndex = i;
            }
        }
        //把最小的值交换到遍历区间初始下标位置
        int mid = array[start];
        array[start] = array[minValueIndex];
        array[minValueIndex] = mid;
        //递归开始遍历下个遍历区间
        sortSelect(array, start + 1);
    }

我们在实际生产环境中写排序算法肯定不能用递归，在 Java 中递归的函数调用栈太深会致开销甚大，上面主要是为便于理解来的初级版本，我们来优化成非递归版本，即双层嵌套版本：

/**
     * @see: 选择排序的非递归实现，即双层嵌套实现
     * @param array: 待排序数组，我们采用原地排序
     */
    public static void sortSelect(int[] array){
        //递归结束条件，此时数组已整体有序
        for (int start = 0; start < array.length - 1; start ++){
            //先假定遍历区间第一个下标的值为最小值;
            int minValueIndex = start;
            for (int startInner = start + 1; startInner <= array.length - 1; startInner ++ ){
                if (array[startInner] < array[minValueIndex]){
                    minValueIndex = startInner;
                }
            }
            //把最小的值交换到遍历区间初始下标位置
            int mid = array[start];
            array[start] = array[minValueIndex];
            array[minValueIndex] = mid;
            //循环开始遍历下个遍历区间
        }
    }

两种实现代码撸下来，相信你已彻底掌握了选择排序算法。

尾巴

选择排序有两个特点：

1. 运行时间和输入无关，其时间复杂度恒为 О(n²)，即使你输入的数组本来就整体有序也是如此！
2. 数据值交换（或言数据移动）是最少的，如上所示，一次遍历只有一次值交换，还有可能是自己跟自己交换，对比冒泡排序，你知道我在说什么！

选择排序需要的额外空间复杂度同冒泡排序，为О(1)

读者请自行发散思维把以上代码改成为 Comparable 数组排序的版本。

下篇我们聊插入排序。

完。