学习顺序主线第 03 / 22 课 · 阶段 2

为什么现在学:第一次练习循环不变量:每轮建立一个可验证的保证。

返回算法课程
排序入门

冒泡排序Bubble Sort

反复比较相邻元素,把较大的值一步步推向右端。

35 分钟前置:数组 · 循环 · 元素交换

学完这一课,你应该能做到

  • 能逐次写出相邻比较后的数组
  • 区分『这一轮最大值就位』与『整个数组有序』
  • 推导比较次数并解释提前退出的条件

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 轮完整扫描,每次相邻逆序就交换。

暴力 · O(n²)

已经就位的后缀仍被重复比较,输入原本有序也照做全部轮数。下面通过缩短范围与无交换退出减少冗余;最坏情况仍为平方级,优化不一定改变最坏增长阶。

03一步步,推导出优化思路

1

把全局问题变成局部问题

若数组无相邻逆序对,它就是有序的。因此只需要找到并消除相邻逆序。

2

发现一轮扫描的保证

较大值每次向右移动,完整一轮后,本轮最大值必然到达末尾。

3

缩小工作区间

末尾元素已经就位,下轮少比较一个位置。如果一轮无交换,整段已经有序。

贯穿算法的不变量

每轮结束后,右侧已处理区间有序,且其中所有值不小于左侧未处理区间。

拿一个小输入,逐步手算

[3,1,2],第一轮 end=2,第二轮 end=1。下方动画已使用同一输入。

轮次 / j比较数组变化已保证什么
第 1 轮 / 03>1,交换[1,3,2]前三项还没有序
第 1 轮 / 13>2,交换[1,2,3]最大值 3 就位
第 2 轮 / 01≤2,不交换[1,2,3]本轮无交换,可结束

第一次看见数组似乎有序,不等于程序已证明有序。第二轮无交换提供了证据;它仍需一次比较,不是 O(1) 的免费检测。

初始化、保持、结束:证明一轮也证明整体

  1. 初始已就位后缀为空,『后缀有序且不小于前缀』自然成立。
  2. 当前扫描把未处理区间的最大值送到 end,接在此前更大的后缀前面,后缀仍有序并扩展一格。
  3. 所有区间处理完时,整个数组有序。若某轮完全无交换,未处理区间相邻关系全正确,也可以提前结束。

04让每一步,都看得见

试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。

Bubble Sort交互演示
STEP 01 / 9
3
0
1
1
2
2
当前处理已处理 / 已确定未处理
01

从左到右观察数组。橙色表示当前比较,绿色表示已确定的位置。

bubble_sort.py参考实现 · 当前第 2 行
正在载入代码编辑器…

动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。

代码里的每个关键决定

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复杂度,来自具体的工作量

时间复杂度
O(n2)O(n^2)

最坏比较 (n−1)+(n−2)+…+1 = n(n−1)/2 次。有提前退出时,已排序输入只扫描一轮,为 O(n)。

辅助空间
O(1)O(1)

原地交换只需要临时变量,辅助空间 O(1)。示例为了保留输入复制了数组,所以示例函数总额外空间是 O(n);动画快照另外占用空间。

拖动 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这些细节,容易踩坑

01

比较范围越界

访问 j+1 时,j 必须小于本轮 end。

02

稳定性的条件

只在左值严格大于右值时交换;相等元素不交换,保留原来次序。

03

不要用于大规模排序

二次复杂度增长很快,工程中应考虑归并、快速排序或语言标准库。

用反例检查前提

一轮结束不代表全部有序

[3,2,1] 第一轮得到 [2,1,3]。最大值 3 确实已经就位,但左侧 2、1 还需要下一轮。

怎样修正:只把 end 及右侧视为已完成。若使用提前退出,必须确认整轮都没有交换。相等时也不交换,才能保留稳定性。

08把想法带进真实题目

合上答案,自己推一次

预测第二轮前的状态

对 [4,1,3,2] 手算第一轮,再回答:第二轮 end 是多少?整个过程最坏需要比较几次?

需要一点提示

当前最大值会连续向右;比较次数是 3+2+1。

查看完整推导与答案
  1. 依次得到 [1,4,3,2]、[1,3,4,2]、[1,3,2,4],第一轮只保证 4 就位。
  2. 第二轮 end=2,只比较下标 0–1 与 1–2,得到 [1,2,3,4]。
  3. 最多比较 6 次。最后 end=1 的无交换扫描才能确认提前结束;空数组和单元素不进入比较循环。

完成上面的手算练习,再把思路迁移到这些题目。

09不用背模板,回答这几个问题

01第一轮完成后,能保证什么?

02带提前退出的冒泡排序,已排序数组的时间复杂度是?

03为什么比较时使用 > 而不是 ≥?

你已经走完了这次推导。

能用自己的话解释复杂度和不变量,再标记为掌握。

把知识连起来

继续阅读

本课例子与推导为本站编写。需要另一种表述或进一步学习时,可对照这些公开课程与文档:

MIT 6.006 · 算法讲义Princeton Algorithms · 课程资料

能独立完成本课练习,再标记掌握。也可以直接用上面的链接继续学习。