因 COVID-19 漫延各自居家，也更有闲时，便拣起一本关于算法的书籍来研究。本不是科班出身，算法方面自然是自己的薄弱环节。平时用各种 SDK，只大概听说了些算法，仅能就自己如何选择哪种实现而作为参考。
如今阅读的是一本入门的书籍，名为 《算法图解》，英文版书名是 《Grokking Algorithms》。 该书图文并茂，十分适合初学者，关于排序最基本莫过于冒泡与选择排序。该书并未提及冒泡，而是直接从选择排序切入，在阅读本书之前我就一直对这两咱排序方式傻傻不分。一直以为头脑中的选择排序就是冒泡排序，那就来看下什么是真正的冒泡排序。
冒泡排序
以 Python 代码为例：
|
1 2 3 4 5 6 7 8 9 |
items = [6, 5, 3, 1, 8, 7, 2, 4] length = len(items) for i in range(length): #1 for j in range(length - i - 1): if items[j] > items[j + 1]: items[j], items[j + 1] = items[j + 1], items[j] #2 print(items) |
#1: range(length) 和 range(0, length) 是一样的
#2: 这是 Python 交换两个值的写法，相当于用临时变量的方式 tmp = items[j]; items[j] = items[j + 1]; items[j + 1] = tmp
网上找了一张非常直观的动态演示了整冒泡排序的过程
该图来自于 Sorting Algorithms - Bubble Sort
下面可以看到的更生动现实的排序执行过程
前面代码中的数字列表也是基于这个图来选择的。对冒泡排序大意的理解可以这样的
- 冒泡排序的每一步只作相邻两元素的交换
- 交换后的右端元素继续与下一个元素比较
- 大循环每次向左收缩一个元素
- 每次大循环都能把当前子列表中最大的元素冒泡到最右端
冒泡排序的时间复杂度是 O(n2)
冒泡排序效率最低效，存在过多的比较与交换，但它却有一个其他排序算法没有的好处，当某轮大循环(比如第一轮大循环) 中没有发生一次交换，那么说明排序已完成，可以立即返回。比如说对于有序集合，扫一遍就能完成 "排序"，效率就是 O(n)。看下面冒泡排序也能处理 100 百有序集合的 "排序"
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
def bubble_sort(items): exchanges = True for i in range(len(items)): if not exchanges: return exchanges = False for j in range(len(items) - i - 1): if items[j] > items[j + 1]: exchanges = True items[j], items[j + 1] = items[j + 1], items[j] bubble_sort(list(range(1000000))) |
选择排序
相对于冒泡排序，选择排序我认为是一种更好理解最直截了当的排序方式，下面用 Python 代码演示
|
1 2 3 4 5 6 7 8 9 |
items = [6, 8, 3, 5, 9, 10, 7, 2, 4, 1] length = len(items) for i in range(length): for j in range(i+1, length): if items[i] > items[j]: items[i], items[j] = items[j], items[i] print(items) |
看实际执行过程：
同样找来了一张图
选择排序的意图非常明确，假如是从小到大的顺序排序，从左至右一个个位置上选择出剩余列表中最小的值
- 位置 1 处要放最小值，循环从右端子列表中选择谁比它还小，是的话交换值
- 然后同样的办法确定位置 2 处的值，子列表向右边收缩
- 每次大循环确定左边一个位置上的值
选择排序的时间复杂度也是是 O(n2)，但操作上比冒泡排序少一些，因为冒泡排序邻近元素相比较，交换次数要多，效率上选择排序比冒泡排序高那么一点点。
具体比较 10 万次对列表 [6, 8, 3, 6, 9, 10, 7, 2, 4, 1] 的排序，我测试选择和冒泡排序的平均时间分别为 1.58608 和 1.87929 秒，选择排序比冒泡快 15.6%。
链接：
本文链接 https://yanbin.blog/two-basic-sorting-algorithms/, 来自 隔叶黄莺 Yanbin Blog
[版权声明] 
本文采用 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 进行许可。
前两年看过这本书，最大的问题是算法在日常开发中很少用到，看完当下记住了，但很快就会忘记。
我一直也是这么想的，但多了解些概念与原理对现有算法的选择上就不会盲目了。