前言

上一次，我们介绍了排序算法中“龟速三兄弟”的二哥“插入排序”。今天，我们继续介绍“龟速三兄弟”中的小弟——“选择排序”。和二哥“插入排序”一样，由于同样是“龟速三兄弟”中的一员，但是处理过程没有大哥“冒泡排序”那么简单明了，因此有不少人可能都没接触过“选择排序”，本文将通过例子来介绍“选择排序”的完整过程。

基本思想

每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 

1.    第一次循环时，i = 0，首先将代表着“最小值下标”的minIndex赋值为第一个数字的数组下标，即minIndex = 0。然后从第2个元素开始与array[minIndex]进行比较，如果有比array[minIndex]小的数，则将minIndex赋值为这个数的下标。当所有元素比较完后，再将array[0]与array[minIndex]交换位置，则arary[0]的值即为最小的数。

2.    第二次循环时，从array[1]开始处理，最后比较出最小的数与array[1]交换位置，过程同步骤1。

3.    直至处理完倒数第二个，结束处理。

例子

下面通过一个例子来看看快速排序是怎么工作的，红色为交换位置的数字。原数组如下。

第一次循环：

1.    先用minIndex记录下当次遍历数据最小的数的下标，当前为0。然后比较array[1]与array[minIndex]，即15与19；由于array[1] < array[minIndex]，因此将minIndex赋值为新的最小值下标，即minIndex = 1。

2.    比较array[2]与array[minIndex]，即37与15；由于array[2] > array[minIndex]，不进行任何操作。

3.    比较array[3]与array[minIndex]，即12与15；由于array[3] < array[minIndex]，因此将minIndex赋值为新的最小值下标，即minIndex = 3。

4.    该次循环的比较结束，将array[minIndex]与array[0]交换位置，交换后的数组如下。

第二次循环：

1.    由于array[0]已经放了最小的数，此次比较只需从array[1]开始，首先，我们同样的使用minIndex记录当次遍历数据最小的数的下标，刚开始记录为1。然后比较array[2]与array[minIndex]，即37与15；由于array[2] > array[minIndex]，不进行任何操作。

2.    比较array[3]与array[minIndex]，即19与15；由于array[3] > array[minIndex]，不进行任何操作。

3.    该次循环比较结束，准备交换array[minIndex]与array[1]位置，但是由于minIndex为1，因此无需进行交换。此时的数组如下。

第三次循环：

1.    此次比较从array[2]开始，首先，我们同样的使用minIndex记录当次遍历数据最小的数的下标，刚开始记录为2。然后比较array[3]与array[minIndex]，即19与37；由于array[3] < array[minIndex]，因此将minIndex赋值为新的最小值下标，即minIndex = 3。

2.    该次循环的比较结束，将array[minIndex]与array[2]交换位置，交换后的数组如下。

第四次循环：

由于此时array[0]~array[2]皆选择完毕，因此最后的array[3]自然也是在正确的位置上，因此我们只需要处理到倒数第二个数即可。

至此，整个排序过程结束。

完整过程

最后我们通过以下动图来看插入排序的整个过程，图中红色的柱子为当次遍历中最小的数，绿色的柱子为正在跟红色的柱子比较的数，橘黄色的柱子为当前已经排好序的数，浅蓝色的柱子为还未排好序的数。

整合

1.由第一次循环我们可以知道，第一次循环我们要选择的数字为整个数组中最小的数，也就是要放在array[0]位置的数，为了方便将该数放在array[0]，因此最外层循环的变量从0开始，由于只需处理到倒数第二个数，因此最外层循环代码可以写出如下。

for (int i = 0; i < array.length - 1; i++)

2.我们用变量minIndex代表当次循环中值最小的数的数组下标，第一次循环时，我们首先将minIndex赋值为0，结合当前循环变量 i 的值，可以写成minIndex = i。然后将之后的数与array[minIndex]进行比较，此时我们需要定义一个新的变量 j 来记录后续比较的数的下标。并在array[j] < array[minIndex]时，将minIndex赋值为 j，整理以上逻辑，代码如下。

for (int i = 0; i < array.length - 1; i++) {
    // 记录当次遍历值最小的数的位置
    int minIndex = i;
    for (int j = i + 1; j < array.length; j++) {
       // 如果array[j]比array[minIndex]小, 则将minIndex修改为j
       if (array[j] < array[minIndex]) {
           minIndex = j;
       }
    }
}

3.在当次循环结束后，我们需要将array[minIndex]放到属于它的位置，也就是array[i]，此时我们可以做一个判断，当minIndex != i 时，才进行交换，代码如下：

if (i != minIndex) {
    // 将当次遍历的最小值交换到对应位置
   int temp = array[i];
   array[i] = array[minIndex];
   array[minIndex] = temp;
}

整合以上代码，最后得出代码如下：

public class SelectSort {
    public static void selectSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        for (int i = 0; i < array.length - 1; i++) {
            // 记录当次遍历值最小的数的位置
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                // 如果array[j]比array[minIndex]小, 则将minIndex修改为j
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            if (i != minIndex) {
                // 将当次遍历的最小值交换到对应位置
                int temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
            }
        }
    }
}

时间复杂度

如果将数组的长度看作n，第一次循环时，j 从1开始直到n - 1，因此比较次数为n - 1；第二次为n - 2，依此类推。最终得到选择排序的比较次数 = (n - 1) + (n - 2) + ... + 2 + 1 = n * (n - 1) / 2，因此时间复杂度为：O(n^2)。

使用场景

选择排序和冒泡排序、插入排序一样。在进行量比较大的排序时，最好不要使用。在1000个数字以内的排序，用选择排序是可以接受的。1000个随机数使用选择排序耗时一般在5毫秒以内，但是当数字个数达到10000个时，耗时会达到30+毫秒，有比较明显的耗时，需要慎重使用。

相关阅读

排序算法：冒泡排序

排序算法：插入排序