01先从一个问题出发
把一排身高不同的人从矮到高排列。每次只允许相邻两个人交换位置，该如何保证最终有序？
一个具体的例子
[5, 2, 4, 1] → 比较 5 和 2 后交换 → [2, 5, 4, 1] → 5 一路向右，第一轮结束得到 [2, 4, 1, 5]。
02最直接的办法，为什么慢？
枚举所有排列，检查哪一个升序。
暴力 · O(n · n!)
有 n! 种排列，每个候选还要线性检查。我们完全忽略了局部大小关系。
03一步步，推导出优化思路
1
把全局问题变成局部问题
若数组无相邻逆序对，它就是有序的。因此只需要找到并消除相邻逆序。
2
发现一轮扫描的保证
较大值每次向右移动，完整一轮后，本轮最大值必然到达末尾。
3
缩小工作区间
末尾元素已经就位，下轮少比较一个位置。如果一轮无交换，整段已经有序。
贯穿算法的不变量
每轮结束后，右侧已处理区间有序，且其中所有值不小于左侧未处理区间。
04让每一步，都看得见
试着先预测下一步，再点击「下一步」验证。变量、动画与代码会同步变化。
Bubble Sort交互演示
STEP 01 / 4835
018
152
227
343
412
560
631
7当前处理已处理 / 已确定未处理
01
从左到右观察数组。橙色表示当前比较，绿色表示已确定的位置。
bubble_sort.py参考实现 · 当前第 2 行
正在载入代码编辑器…
动画展示参考实现的执行轨迹。切换语言时，当前操作会定位到对应代码行。
05复杂度，来自具体的工作量
时间复杂度
最坏比较 (n−1)+(n−2)+…+1 = n(n−1)/2 次。有提前退出时，已排序输入只扫描一轮，为 O(n)。
辅助空间
原地交换只需要临时变量，辅助空间 O(1)。示例为了保留输入复制了数组，所以示例函数总额外空间是 O(n)；动画快照另外占用空间。
06看到什么，应该想到它？
关键词只是线索，继续检查适用条件07这些细节，容易踩坑
01
比较范围越界
访问 j+1 时，j 必须小于本轮 end。
02
稳定性的条件
只在左值严格大于右值时交换；相等元素不交换，保留原来次序。
03
不要用于大规模排序
二次复杂度增长很快，工程中应考虑归并、快速排序或语言标准库。
08把想法带进真实题目
先说出模式和适用条件，再开始写代码。
09不用背模板，回答这几个问题
01第一轮完成后，能保证什么？
02带提前退出的冒泡排序，已排序数组的时间复杂度是？
03为什么比较时使用 > 而不是 ≥？
你已经走完了这次推导。
能用自己的话解释复杂度和不变量，再标记为掌握。