选择排序所面临的问题

labuladong原创约 3086 字

前置知识

阅读本文前，你需要先学习：

排序算法的关键指标

一句话总结

选择排序是最简单朴素的排序算法，但是时间复杂度较高，且不是稳定排序。其他基础排序算法都是基于选择排序的优化。

你可以点开可视化面板，点击播放按钮，然后点击加速/减速按钮调节速度，即可直观感受选择排序的过程：

如果你是没接触过排序算法的初学者，那是最好的，不要急着看定义之类的东西；如果你之前了解过排序算法，现在请你忘记定义，忘记曾经背诵过的算法代码。

有了前面内容的铺垫，你已经有了一定的编程能力，能够解决一些基础的算法问题了。那么在这个前提下，我有一个学习方法分享，供你参考：

遇到一个新问题的时候，不要急着找人要一个标准答案，而应该启动自己的思考。被灌输一次标准答案，就错失一次机缘，少一分灵气。被灌得多了，人就傻了。

总有些读者，愁眉苦脸地找我诉苦，说算法题刷完了就忘怎么办啊。我还觉得这是好事呢，念念不忘的是执念，忘了才好，说明还没被塞满，这就是独立思考的机缘呀。

所以回到问题，让我们抓住这次机缘。现在就是给你输入一个数组，让你写个排序算法把所有元素从小到大排序，你来说，怎么写？如果你从来没有思考过这个问题，可以停下几分钟想一想。

void sort(int[] nums) {
    // 你的代码，将 nums 中的元素从小到大排序
}

我第一次思考这个问题时，想到的最直接的方法是这样的：

先遍历一遍数组，找到数组中的最小值，然后把它和数组的第一个元素交换位置；接着再遍历一遍数组，找到第二小的元素，和数组的第二个元素交换位置；以此类推，直到整个数组有序。

这个算法有一个被大家熟知的名字，叫做「选择排序」，即每次都去遍历选择最小的元素。写成代码就是这样的：

java

void sort(int[] nums) {
    int n = nums.length;
    // sortedIndex 是一个分割线
    // 索引 < sortedIndex 的元素都是已排序的
    // 索引 >= sortedIndex 的元素都是未排序的
    // 初始化为 0，表示整个数组都是未排序的
    int sortedIndex = 0;
    while (sortedIndex < n) {
        // 找到未排序部分 [sortedIndex, n) 中的最小值
        int minIndex = sortedIndex;
        for (int i = sortedIndex + 1; i < n; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }
        }
        // 交换最小值和 sortedIndex 处的元素
        int tmp = nums[sortedIndex];
        nums[sortedIndex] = nums[minIndex];
        nums[minIndex] = tmp;

        // sortedIndex 后移一位
        sortedIndex++;
    }
}

cpp

void sort(vector<int>& nums) {
    int n = nums.size();
    // sortedIndex 是一个分割线
    // 索引 < sortedIndex 的元素都是已排序的
    // 索引 >= sortedIndex 的元素都是未排序的
    // 初始化为 0，表示整个数组都是未排序的
    int sortedIndex = 0;
    while (sortedIndex < n) {
        // 找到未排序部分 [sortedIndex, n) 中的最小值
        int minIndex = sortedIndex;
        for (int i = sortedIndex + 1; i < n; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }
        }
        // 交换最小值和 sortedIndex 处的元素
        int tmp = nums[sortedIndex];
        nums[sortedIndex] = nums[minIndex];
        nums[minIndex] = tmp;

        // sortedIndex 后移一位
        sortedIndex++;
    }
}

python

def sort(nums: List[int]) -> None:
    n = len(nums)
    # sortedIndex 是一个分割线
    # 索引 < sortedIndex 的元素都是已排序的
    # 索引 >= sortedIndex 的元素都是未排序的
    # 初始化为 0，表示整个数组都是未排序的
    sortedIndex = 0
    while sortedIndex < n:
        # 找到未排序部分 [sortedIndex, n) 中的最小值
        minIndex = sortedIndex
        for i in range(sortedIndex + 1, n):
            if nums[i] < nums[minIndex]:
                minIndex = i
        # 交换最小值和 sortedIndex 处的元素
        nums[sortedIndex], nums[minIndex] = nums[minIndex], nums[sortedIndex]

        # sortedIndex 后移一位
        sortedIndex += 1

func sort(nums []int) {
    n := len(nums)
    // sortedIndex 是一个分割线
    // 索引 < sortedIndex 的元素都是已排序的
    // 索引 >= sortedIndex 的元素都是未排序的
    // 初始化为 0，表示整个数组都是未排序的
    sortedIndex := 0
    for sortedIndex < n {
        // 找到未排序部分 [sortedIndex, n) 中的最小值
        minIndex := sortedIndex
        for i := sortedIndex + 1; i < n; i++ {
            if nums[i] < nums[minIndex] {
                minIndex = i
            }
        }
        // 交换最小值和 sortedIndex 处的元素
        nums[sortedIndex], nums[minIndex] = nums[minIndex], nums[sortedIndex]

        // sortedIndex 后移一位
        sortedIndex++
    }
}

javascript

function sort(nums) {
    const n = nums.length;
    // sortedIndex 是一个分割线
    // 索引 < sortedIndex 的元素都是已排序的
    // 索引 >= sortedIndex 的元素都是未排序的
    // 初始化为 0，表示整个数组都是未排序的
    let sortedIndex = 0;
    while (sortedIndex < n) {
        // 找到未排序部分 [sortedIndex, n) 中最小值的索引
        let minIndex = sortedIndex;
        for (let i = sortedIndex + 1; i < n; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }
        }
        // 交换最小值和 sortedIndex 处的元素
        [nums[sortedIndex], nums[minIndex]] = [nums[minIndex], nums[sortedIndex]];

        // sortedIndex 后移一位
        sortedIndex++;
    }
}

上述算法的可视化过程如下：

这个算法是正确的，稍加改动就可以作为力扣第 912 题「排序数组」的解法代码。

但这个算法无法通过 912 题的所有测试用例，最后会得到一个超时的错误，这说明算法的逻辑是正确的，只是时间复杂度较高，超出了题目的限制。

暂且不管如何通过 912 题，我们先来按照排序算法的几个关键指标来分析一下这个排序算法。

是否是原地排序

是的。因为算法并没有使用额外的数组空间进行辅助，只是用了几个变量，空间复杂度是 $O(1)$ 。

时空复杂度分析

这个 sort 函数中包含一个 while 循环嵌套一个 for 循环，相当于是这样：

for (int sortedIndex = 0; sortedIndex < n; sortedIndex++) {
    for (int i = sortedIndex + 1; i < n; i++) {
        // ...
    }
}

你看到了，这就是嵌套 for 循环，总的循环次数是 (n - 1) + (n - 2) + (n - 3) +... + 1，这是等差数列求和，结果近似是 n^2 / 2，所以这个排序算法的时间复杂度用 Big O 表示法就是 $O(n^2)$ ，其中 n 是待排序数组的元素个数。

而且你注意这个算法有个特点，即便整个数组已经是有序的，它还是会执行 n^2 / 2 次，即原始数据的有序度对算法的时间复杂度没有任何影响。

要关注排序算法的实际执行次数

对于一般的算法时空复杂度分析，我们只需要从 Big O 表示法的角度来分析即可，即仅关心量级（最高次项）的大小，而不关心系数和低次项。

但是在分析不同排序算法的场景下，实际的执行次数，以及一些特殊情况（比如数组本身就有序的情况），还是有必要关注的。

因为有多种排序算法从 Big O 的视角来看都是 $O(n^2)$ 复杂度，那么我们要根据他们的实际执行次数以及特殊情况下的表现，来分析它们的优劣。

时间都去哪了？优化思路？

现在，请你观察这个算法的逻辑，仔细思考几分钟，时间复杂度是否还有优化的可能？

不要小看这里是基础章节，我讲的都是思维方法，未来你做任何题目，优化时间复杂度的思路和这里一模一样。

首先，如果代码没有写错，算法时间复杂度还是太高，那只有一种可能，就是存在冗余计算。

上述算法中出现冗余计算的地方比较容易看出来：

它首先遍历 nums[0..] 寻找最小值，然后遍历 nums[1..] 寻找最小值，然后遍历 nums[2..] 寻找最小值，以此类推。

那么请问，在遍历 nums[0..] 的时候，其实已经遍历过 nums[1..] 和 nums[2..] 的所有元素了，你为什么要再次遍历呢？

理论上，你应该可以在遍历 nums[0..] 的时候，顺便找到 nums[1..] 和 nums[2..] 的最小元素，对吧？如果能做到这一点，是不是就可以消掉内层的 for 循环，从把时间复杂度降低一个数量级？

好，现在我们已经找到了冗余计算的症结所在，并且有了一个优化思路。那么这个思路是否可以实现呢？你是否能够在遍历 nums[0..] 的时候，顺便找到 nums[1..] 和 nums[2..] 的最小元素？

我将进行抽象，把这个优化场景转化成一个全新的问题：

给你一个数组 nums，请你计算一个新数组 suffixMin 数组，其中 suffixMin[i] 表示 nums[i..] 中的最小值。

如果正着思考，假设现在我知道了 nums[0..] 中的最小元素，我是否能够推导出 nums[1..] 中的最小元素呢？

答案是不可能。信息不足，我实在不知道如何根据 min(nums[0..]) 推导出 min(nums[1..])，只能重新遍历一遍 nums[1..]。

但是，我自己都不相信，就是算个最小值，咋可能这么难搞呢？我的脑子被智子锁死了吗？？？

如果反过来思考，假设现在我知道了 nums[1..] 中的最小元素，我是否能够推导出 nums[0..] 中的最小元素呢？

答案是可以的，min(nums[0..]) = min(nums[0], min(nums[1..]))。

有了这个思路，这个 suffixMin 数组就能算出来了，关键是倒着计算：

int[] nums = new int[]{3, 1, 4, 2};
// suffixMin[i] 表示 nums[i..] 中的最小值
int[] suffixMin = new int[nums.length];

// 从后往前计算 suffixMin
suffixMin[nums.length - 1] = nums[nums.length - 1];
for (int i = nums.length - 2; i >= 0; i--) {
    suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]);
}

// [1, 1, 2, 2]
System.out.println(suffixMin);

好了，这个计算 suffixMin 数组的问题解决了，现在回到选择排序的优化，我现在只需要花 $O(n)$ 的时间遍历一遍 nums 数组算出 suffixMin 数组，就可以在 $O(1)$ 的时间内得到 nums[1..], nums[2..], ... 任意子数组的最小值。

按理说，现在我可以把选择排序的内层 for 循环消掉，时间复杂度优化成 $O(n)$ 了，对吗？答案是不行。

请你思考几分钟，为什么不行，关键的问题在哪里？

点击查看我的思考

有的读者可能会说，选择排序中需要知道最小元素的索引进行交换，而 suffixMin 数组里面只存储了最小元素的值，没有存储索引，所以无法优化选择排序。

但是，我完全可以建一个新数组 minIndex，在计算 suffixMin 数组的时候，同时在 minIndex 记录下最小元素对应的索引，所以这个问题不是关键。

其实，问题的关键在于交换操作。

suffixMin 数组正确工作有个前提，就是 nums 数组不可变。如果 nums[i] 的值发生改变，那么所有 suffixMin[0..i] 存储的最小值就失效了，需要重新计算一次才行。

这个应该不难理解吧，比方说你的 suffixMin[3] = 6，意思是 nums[3..] 中的最小值是 6。如果你修改了 nums[5] = 2，那么 suffixMin[0..5] 的值都应该变成 2，而不再是 6 了。

选择排序中的交换操作，会导致 nums 中的元素位置发生变化，进而导致 suffixMin 数组失效，这才是问题的本质。

综上，所有尝试都是错误的，选择排序无法进行任何优化。

那么我们花了那么多时间，尝试了种种方法，最后啥名堂也没弄出来，是不是很失败？

不，我认为这些才是有效的思考，是真正能够帮助读者掌握算法思维的。

比如上面预计算 suffixMin 的方法是一种经典的算法思维，后文前缀和技巧就会用到。nums 数组变化导致预计算数组 suffixMin 失效也是一类经典的算法问题，前文线段树基础会解决这个问题。

在本站的教程中，我会经常展现这种思考过程。在后面讲到的排序算法中，你也可以思考一下，它们的本质上和选择排序有什么区别？凭什么它们就能把时间复杂度降到 $O(n^2)$ 以下？

排序的稳定性

请你按照排序算法的几个关键指标中对排序稳定性的定义，分析一下这个算法是不是稳定排序？

如果这个算法不是稳定排序，那么是什么操作导致了它失去了排序稳定性呢？是否可以优化这个算法，使它成为稳定排序？请思考几分钟，然后再看我的理解。

点击查看答案

选择排序算法不是稳定排序。

按照稳定排序的定义，相同元素的相对位置不会发生变化才能称为稳定排序。你举个简单的例子就看出这个算法不稳定了：

[2', 2''', 2'', 1]

这个例子中有多个重复元素 2，我分别用 2'、2'''、2'' 来区别这三个元素。如果这个排序算法是稳定的，那么排序后的结果应该保持三个 2 的相对顺序：

[1, 2', 2''', 2'']

但实际上，你在脑子里跑一下这个算法就能想到，它第一次寻找最小值时，肯定会把元素 2' 和 1 交换，这一下就会打乱 2 之间的相对顺序了：

[1, 2''', 2'', 2']

是交换操作，使得选择排序失去了排序的稳定性。

有没有什么办法可以优化这个算法，使它成为稳定排序？现在时间复杂度都到 $O(n^2)$ 了，属于排序算法里面最差的那一档，好歹咱也支棱起来，把自己搞成一个稳定排序，行不行？

你可以自己想一想这个问题，在后面的排序算法，我们会尝试解决这个问题。

选择排序所面临的问题

912. 排序数组 https://leetcode.cn/problems/sort-an-array

912. Sort an Array https://leetcode.com/problems/sort-an-array

是否是原地排序

时空复杂度分析

时间都去哪了？优化思路？

排序的稳定性