提及选择排序算法,我是一点都不陌生,我大一上学期在 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 问题,我之前一直觉得这不就是选择排序算法的应用场景吗? 不用完全排好序,还能提前终止循环。为此,我还一度洋洋得意,觉得自己真是太厉害了,都学会举一反三了。
后来才发现自己被打脸了。选择排序算法只是最普通的方法,还有其他高效的实现方法。
你知道这个问题还有啥更高效的方法吗?
下篇文章,我们一起学习插入排序算法,这是一个非常常用的排序算法,而且有很多优化的地方,你都知道吗?