01先从一个问题出发
把一排身高不同的人从矮到高排列。每次只允许相邻两个人交换位置,该如何保证最终有序?
[3,1,2],第一轮 end=2,第二轮 end=1。下方动画已使用同一输入。
相邻逆序与全局有序之间有什么关系
升序数组需要满足 a[0]≤a[1]≤…≤a[n−1]。只要每一对相邻元素都满足这个关系,传递性就保证任意较早元素不大于较晚元素。因此可以从局部检查入手:看到 a[j]>a[j+1],就把这一对换过来。
但只交换一对并不能让全局立刻有序。[3,1,2] 先变成 [1,3,2],仍然有 3>2。我们继续向右比较,让刚遇到的较大值有机会和下一个元素比较。
一轮扫描为什么能减少下一轮的工作
比较下标 0、1 后,位置 1 保存前两项的较大值;再与位置 2 比较后,位置 2 保存前三项的最大值。沿这个过程走到 end,本轮最大值必然到达 end。这个结论不依赖元素是否重复、是否为负数。
所以第二轮不必再碰最后一项。每完成一轮,右侧多一个最终就位的元素。这里的『就位』比『这一段目前有序』更强:之后不用再移动它。与下一课插入排序的有序前缀比较,能看清两个算法的不同保证。
02最直接的办法,为什么慢?
固定做 n 轮完整扫描,每次相邻逆序就交换。
已经就位的后缀仍被重复比较,输入原本有序也照做全部轮数。下面通过缩短范围与无交换退出减少冗余;最坏情况仍为平方级,优化不一定改变最坏增长阶。
03一步步,推导出优化思路
把全局问题变成局部问题
若数组无相邻逆序对,它就是有序的。因此只需要找到并消除相邻逆序。
发现一轮扫描的保证
较大值每次向右移动,完整一轮后,本轮最大值必然到达末尾。
缩小工作区间
末尾元素已经就位,下轮少比较一个位置。如果一轮无交换,整段已经有序。
每轮结束后,右侧已处理区间有序,且其中所有值不小于左侧未处理区间。
拿一个小输入,逐步手算
[3,1,2],第一轮 end=2,第二轮 end=1。下方动画已使用同一输入。
| 轮次 / j | 比较 | 数组变化 | 已保证什么 |
|---|---|---|---|
| 第 1 轮 / 0 | 3>1,交换 | [1,3,2] | 前三项还没有序 |
| 第 1 轮 / 1 | 3>2,交换 | [1,2,3] | 最大值 3 就位 |
| 第 2 轮 / 0 | 1≤2,不交换 | [1,2,3] | 本轮无交换,可结束 |
第一次看见数组似乎有序,不等于程序已证明有序。第二轮无交换提供了证据;它仍需一次比较,不是 O(1) 的免费检测。
初始化、保持、结束:证明一轮也证明整体
- 初始已就位后缀为空,『后缀有序且不小于前缀』自然成立。
- 当前扫描把未处理区间的最大值送到 end,接在此前更大的后缀前面,后缀仍有序并扩展一格。
- 所有区间处理完时,整个数组有序。若某轮完全无交换,未处理区间相邻关系全正确,也可以提前结束。
04让每一步,都看得见
试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。
从左到右观察数组。橙色表示当前比较,绿色表示已确定的位置。
动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。
代码里的每个关键决定
for end in range(len(numbers) - 1, 0, -1):- end 表示本轮最后参与比较的位置。它从 n−1 逐步减少到 1,不是数组长度。
for j in range(end):- j 最大为 end−1,所以 j+1 最大恰好为 end;这个边界避免越界并跳过已就位后缀。
swapped = False- 每一轮开始都重新清零。如果只在整个函数开始设一次,早先的交换会妨碍后面的提前退出。
if not swapped:- 这个判断在内层循环结束后执行;只比较一对未交换,不能说明整个区间都没有逆序。
05复杂度,来自具体的工作量
最坏比较 (n−1)+(n−2)+…+1 = n(n−1)/2 次。有提前退出时,已排序输入只扫描一轮,为 O(n)。
原地交换只需要临时变量,辅助空间 O(1)。示例为了保留输入复制了数组,所以示例函数总额外空间是 O(n);动画快照另外占用空间。
把工作量具体数出来
逆序的 5 项依次比较 4、3、2、1 次,共 10 次。一般总数为 (n−1)+…+1=n(n−1)/2,最坏 O(n²)。
有序输入第一轮比较 n−1 次而没有交换,立即结束,最好 O(n)。交换次数与比较次数并非同一个量。
排序操作本身可以原地、辅助空间 O(1)。页面参考函数复制输入以免改变调用者的数据,复制占 O(n);动画为回看保存的快照也不计入原算法的辅助空间。
06看到什么,应该想到它?
关键词只是线索,继续检查适用条件07这些细节,容易踩坑
比较范围越界
访问 j+1 时,j 必须小于本轮 end。
稳定性的条件
只在左值严格大于右值时交换;相等元素不交换,保留原来次序。
不要用于大规模排序
二次复杂度增长很快,工程中应考虑归并、快速排序或语言标准库。
一轮结束不代表全部有序
[3,2,1] 第一轮得到 [2,1,3]。最大值 3 确实已经就位,但左侧 2、1 还需要下一轮。
怎样修正:只把 end 及右侧视为已完成。若使用提前退出,必须确认整轮都没有交换。相等时也不交换,才能保留稳定性。
08把想法带进真实题目
预测第二轮前的状态
对 [4,1,3,2] 手算第一轮,再回答:第二轮 end 是多少?整个过程最坏需要比较几次?
需要一点提示
当前最大值会连续向右;比较次数是 3+2+1。
查看完整推导与答案
- 依次得到 [1,4,3,2]、[1,3,4,2]、[1,3,2,4],第一轮只保证 4 就位。
- 第二轮 end=2,只比较下标 0–1 与 1–2,得到 [1,2,3,4]。
- 最多比较 6 次。最后 end=1 的无交换扫描才能确认提前结束;空数组和单元素不进入比较循环。
完成上面的手算练习,再把思路迁移到这些题目。
09不用背模板,回答这几个问题
01第一轮完成后,能保证什么?
02带提前退出的冒泡排序,已排序数组的时间复杂度是?
03为什么比较时使用 > 而不是 ≥?
你已经走完了这次推导。
能用自己的话解释复杂度和不变量,再标记为掌握。