动态可视化十大排序算法之选择排序算法

选择排序

提及选择排序算法，我是一点都不陌生，我大一上学期在 C 语言这门课程中学习到的两个算法，其中一个就是选择排序算法，另一个就是冒泡排序算法。

选择排序的思想也是基于交换的，它的数组分为待排序区间和已排序区间，这点和插入排序的操作有点像，插入排序我们下篇文章会讲。但是选择排序是每次从待排序区间选择最小的值，和待排序区间的第一个元素进行交换，这样的话，每次迭代，已排序区间的长度都会加 1，而待排序区间会 减 1,这样迭代 n 次，数组就会变得有序。

看了说明，想必你还是有点糊涂，具体的看下视频吧！

怎么样？看完视频，是不是觉得清楚了好多，总结说就是，每次从待排序区间选择最小的元素，和待排序区间元素的第一个进行交换。

代码实现

#!/usr/bin/python
# -*- coding:utf-8 -*-
from typing import List


def select_sort(array: List[int]) -> None:
    for i in range(len(array)):
        min_number_index = i
        for j in range(i + 1, len(array)):
            if array[j] < array[min_number_index]:
                min_number_index = j
        array[i], array[min_number_index] = array[min_number_index], array[i]


if __name__ == "__main__":
    array = [44, 3, 38, 5, 47]
    select_sort(array)
    print(array)

看了代码实现，如果你还没有明白的话，那就看下下面这幅图，更加的直观。

选择排序算法原理示意图

不知道你有没有发现，在查找待排序区间的最小值的时候，记录的是数组的下标。这是为什么呢？

因为数组通过下标访问数组元素的时间复杂度是

, 这个我想大部分人都是了解的。

数组在计算机中的存储空间是连续的，数组名就代表了存储空间的首地址，首地址加上偏移量，就可以访问到数组元素了。

所以说，实际的代码实现和理论讲解还是有点不一样的。因此，在计算机这门实践课程中，检验你懂了的唯一评价标准就是「你可以写出没有 Bug 的代码」。

评价

那么选择排序算法的时间复杂度、空间复杂度、以及稳定性又是怎么样的呢？

很明显，选择排序的时间复杂度是

,空间复杂度的话，没有占用额外的内存空间，

,是原地排序算法。

至于稳定性的话，选择排序不是稳定的排序算法，这个可以通过反例的方式进行判别，具体形式可以看下图。

经过一次交换后，数组就变得有序了，在接下来的迭代过程中也不会再发生变化，但是此时数组的第一个 5 和 第二个 5 的相对顺序已经发生了改变，所以它不是稳定的排序算法。

可能你会觉得两个数字都是 5，哪个在前，哪个在后，又有啥关系呢？

确实，在这个例子中，两个 5 是等价的，没啥区别。但是在实际的应用场景中，我们要排序的数据就不单单是整数了，它们一般都是类的对象，而整数只是类字段的一个属性罢了。所以稳定性也是一个重要的考量指标。

其实总结来看，一般来说，只要在排序过程只是在相邻元素之间进行比较、交换，比如冒泡排序，插入排序，那么这个排序算法就是稳定的。但是如果在排序过程中有大范围的交换操作，比如（选择排序、快速排序），那么这个算法很多时候是不稳定的。

总结

选择排序和冒泡排序算法一样，都是时间复杂度是

的排序算法，这种排序算法时间复杂度比较高，很少在实际场景中使用。

但是这两个排序算法都是非常经典的排序算法。另外我之前其实对选择排序算法有点误会。不知道你们有没有这样的想法。

有道面试题是这样的，就是求数组中的第 K 大元素，还有的问题直接是求数组的前 K 大元素或者是前 K 小元素，也就是 Top K 问题，我之前一直觉得这不就是选择排序算法的应用场景吗？ 不用完全排好序，还能提前终止循环。为此，我还一度洋洋得意，觉得自己真是太厉害了，都学会举一反三了。

后来才发现自己被打脸了。选择排序算法只是最普通的方法，还有其他高效的实现方法。

你知道这个问题还有啥更高效的方法吗？

下篇文章，我们一起学习插入排序算法，这是一个非常常用的排序算法，而且有很多优化的地方，你都知道吗？