冒泡排序与选择排序
复习
- 排序问题与稳定性：稳定性的含义
- 数组：可按下标访问与交换元素
- 大 O 记号：衡量算法增长趋势
TL;DR
- 冒泡排序反复比较相邻元素并交换
- 选择排序每轮选出最小元素放到前面
- 两者都很直观，代价却都是
O(n²) - 它们适合教学与理解，不适合大规模数据
正文
先从两种最直观的排序说起。它们效率不高，却非常适合用来建立“排序是怎么回事”的直觉。
冒泡排序：大的往上冒
冒泡排序（bubble sort）的做法是：反复比较相邻的两个元素，如果顺序不对就交换。
每一轮从头到尾走一遍，最大的元素就会像气泡一样，一路“冒”到末尾。下一轮就不必再管它，继续处理前面剩下的部分。经过若干轮，整个数组就有序了。
因为每一轮都可能做很多次比较和交换，总共要走大约 n 轮、每轮比较 n 次，代价是 O(n²)。数据一大，就慢得难以忍受。
选择排序：每轮挑最小的
选择排序（selection sort）换个做法：
- 在未排序的部分里，找出最小的元素
- 把它和未排序部分的第一个位置交换
- 未排序范围缩小一格，重复
每轮只做一次交换，比冒泡的交换次数少；但每轮都要完整扫一遍找最小，比较次数仍是 O(n²)。
关于稳定性
这里可以顺便体会前面说的“稳定性”：
- 冒泡排序：只有相邻元素严格逆序时才交换，相等元素不会互换，因此是稳定的
- 选择排序：交换时可能把某个相等元素甩到后面，因此通常不稳定
看，同样的 O(n²)，稳定性却可能不同。这也是为什么评价排序不能只看时间。
这两种算法更适合理解原理，真实场景里几乎不会用它们处理大数据。但它们引出的“把新元素插到已排好部分”的想法，会带出一个在特定情况下相当好用的算法。
思考题 1
冒泡排序和选择排序，各自每一轮在做什么？
思考题 2
为什么这两种算法在数据量大时会很慢？
小结
知识点
- 冒泡排序反复交换相邻的逆序元素
- 选择排序每轮选出最小值放到前面
- 两者时间复杂度均为
O(n²) - 冒泡稳定，选择排序通常不稳定
参考资料
- Wikipedia(zh)：冒泡排序：反复交换相邻元素的排序
- Wikipedia(zh)：选择排序：每轮选出最小值的排序
思考题答案（仅供参考）
思考题 1
冒泡排序每一轮从头到尾比较相邻元素并交换，让当前最大元素“冒”到末尾；选择排序每一轮在未排序部分中找出最小元素，把它交换到未排序部分的起始位置，然后缩小范围。
思考题 2
因为它们都要进行大约 n 轮，每轮又比较大约 n 个元素，总操作数约为 n²。数据规模翻倍，耗时约变为四倍，因此数据一大就非常慢。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪