选择排序

选择排序（selection sort）在排序算法中也是比较基础的一个，来，一起看看。

选择排序思想

和冒泡排序的名字一样，它的名字也是足够直白的。“选择”两个字对于人生来说真算的上是一个比较艰难的字眼，不过在选择排序中不用担心，这里做选择没那么难。具体来说，我们可以把数组看作两部分，一部分为有序区，一部分为无序区，我们每次只需要在数组无序区中选择出指定的值，然后把它放到有序区，直到无序区没有元素（具体操作来说，只需要把有序区和无序区两个值的位置交换即可）。

那什么是指定的值？我也不是故意要用这个含糊其辞的说法，正所谓“命运只有一个，而人生却有多种选择”，在这里也有多种选择。对于这个值，我们可以选择无序区的最大值；也可以选择无序区的最小值；甚至可以既选择无序区的最大值，又选择无序区的最小值。其实最后一种选择相当于是对前两种选择的一种优化，在下面会说到。

当然不同的选择也会导致放到有序区的规则不同。这里以数组从小到大排序为例，假如数组前半段为有序区，后半段为无序区，那么每次需要在无序区中选择出最小值，将它放到有序区的末尾即可；假如数组前半段为无序区，后半段为有序区，那么每次需要在无序区中选择出最大值，将它放到有序区的开头即可。

接下来就用个简单的demo来演示一下整个过程吧。假如数组前半段为有序区，后半段为无序区，待排序数组如下：

2

5

4

8

7

9

1

6

3

比较和交换的详细过程为：
（1）记录数组第一个位置，从第二个位置开始一直到数组末尾，找到其中的最小值对应的位置，交换两元素位置

1

5

4

8

7

9

2

6

3

（2）接下来都以此类推，记录数组第二个位置，从第三个位置开始一直到数组末尾寻找最小值，交换位置；记录数组第三个位置，从第四个位置开始一直到数组末尾寻找最小值，交换位置...

接下来直接给出所有轮次的结果如下：

1	5	4	8	7	9	2	6	3
1	2	4	8	7	9	5	6	3
1	2	3	8	7	9	5	6	4
1	2	3	4	7	9	5	6	8
1	2	3	4	5	9	7	6	8
1	2	3	4	5	6	7	9	8
1	2	3	4	5	6	7	9	8
1	2	3	4	5	6	7	8	9

当然，假如数组前半段为无序区，后半段为有序区的情况，和上边的demo相似，就不赘述了。

选择排序代码

/**
 * 每次选择最小值
 * @param data 待排序数组
 * @return 排序后的数组
 */
public int[] selectionSort(int[] data) {
    // minIndex 为最小值的下标；temp为 swap 时用到的临时变量
    int minIndex, temp;
    for (int i = 0; i < data.length - 1; i++) {
        minIndex = i;
        // 找出最小值的下标
        for (int j = i + 1; j < data.length; j ++) {
            if (data[j] < data[minIndex]) {
                minIndex = j;
            }
        }
        // 如果找到的最小值下标不是 i，两位置元素交换位置
        if (minIndex > i) {
            // swap
            temp = data[i];
            data[i] = data[minIndex];
            data[minIndex] = temp;
        }
    }
    return data;
}

/**
 * 每次选择最大值
 * @param data 待排序数组
 * @return 排序后的数组
 */
public int[] selectionSort(int[] data) {
    int maxIndex, temp;
    for (int i = data.length - 1; i >= 0; i--) {
        maxIndex = i;
        for (int j = 0; j < i; j++) {
            if (data[j] > data[maxIndex]) {
                maxIndex = j;
            }
        }
        if (maxIndex < i) {
            // swap
            temp = data[i];
            data[i] = data[maxIndex];
            data[maxIndex] = temp;
        }
    }
    return data;
}

选择排序优化

在前面说选择排序思想时已经卖了这个关子，在这里具体说说是怎么回事。在上面的介绍中，每次我们在选择指定值时，只选择最小值或最大值，然后每次只交换一对元素，那怎么给它提速呢？当然很简单，那我们每次选两个值，既选择最小值，又选择最大值，把每次遍历交换的元素增加一个，这样自然是能够减少遍历的次数，让排序提点速。

具体在代码优化实现上，有个点需要注意一下。当选出最小值和最大值后进行位置交换时，如果先交换的是最小值的位置，那么此时可能有一种情况，就是最小值的位置上原本放的是数组中的最大值，这种情况下需要更新一下最大值所在的位置。

好像有点绕，举个例子来说一下，假如待排序数组为 [4, 2, 1, 3]，第一轮找到最小值为 1，最大值为 4，先交换最小值，4 和 1 交换位置，此时最大值 4 的位置被交换到了原来 1 的位置，这时要把最大值的位置更新为原来 1 的位置，然后再交换最大值。

选择排序优化代码

/**
 * 每次选择最小值和最大值
 * @param data 待排序数组
 * @return 排序后的数组
 */
public int[] selectionSort(int[] data) {
    int minIndex, maxIndex, temp;
    for (int left = 0, right = data.length - 1; left < right; left++, right--) {
        minIndex = left;
        maxIndex = right;
        for (int i = left; i <= right; i++) {
            if (data[i] < data[minIndex]) {
                minIndex = i;
            }
            if (data[i] > data[maxIndex]) {
                maxIndex = i;
            }
        }
        if (minIndex > left) {
            // swap left and minIndex first
            temp = data[left];
            data[left] = data[minIndex];
            data[minIndex] = temp;
            // 先交换的是最小值的位置，所以需要考虑如果最大值位置原本就在 left 位置时的情况
            // 如果是该情况，那么当最小值被交换后，最大值此时的位置为 minIndex
            if (left == maxIndex) {
                maxIndex = minIndex;
            }
        }
        if (maxIndex < right) {
            // swap right and maxIndex
            temp = data[right];
            data[right] = data[maxIndex];
            data[maxIndex] = temp;
        }
    }
    return data;
}

复杂度和稳定性分析

1. 时间复杂度

• 最优时间复杂度：O(n^2)

  • 当用优化后的选择排序代码进行排序时，虽然遍历的次数减少了一半，时间复杂度变为O(n/2 * n/2)，运行时间确实有所减少，但是省略常数后，它的算法时间复杂度仍然为O(n^2)级别。

• 最坏时间复杂度：O(n^2)

• 平均时间复杂度：O(n^2)

2. 空间复杂度：O(1)

• 整个过程都是原地排序，并没有用到其它辅助的空间。

3. 选择排序是一种不稳定排序。

• 这个应该很好举例，假如待排序数组为 [4, 3, 4, 1, 2]。

原地排序和稳定性的概念在从冒泡排序开始最后中有解释，就不赘述了。

---