烧水时大气泡总比小气泡先冲出水面——轻的、位置合适的最先冒头。起泡排序借了这个画面：让每一轮扫描把最大的元素一路「顶」到末尾，一轮一个，逐个就位。

跟随数组 [5,3,8,2] 走完一趟扫描，看最大值如何沉底。

竖向流程图：每一轮扫描后无序前缀缩短一格，看 n-1 轮如何把气泡全部顶到右端。

从完整双重循环代码出发，逐行对照前面推演的扫描过程，落实每一趟到底做了什么。

外层 i 控制趟数，内层 n-1-i 正是让右侧已排好的最大值不再参与比较，逐趟缩短扫描区间。

上一页写好了朴素版：外层固定跑 n-1 轮，内层每轮扫一遍。但如果某一轮里一次交换都没发生呢？说明数组已经有序了，后面几轮却还在白跑——这就是朴素版最大的浪费。

用 sorted 标志检测「一趟无交换」，让已有序的数组提前收工，避免空跑。

每趟开始假设有序，一旦交换就推翻假设；若整趟未推翻，说明零交换即全局有序，break 提前结束。

同一输入，两条执行路径：左侧朴素版扫满轮次，右侧改进版遇有序即停，看出省掉的轮次。

上一页我们看到：只要某一轮一次交换都没发生，改进版就提前收工。那它到底还怕什么？反过来想：什么样的输入能让每一轮都被迫交换？找到它，就找到了改进版的死穴。

沿箭头逐轮追踪：每轮都有交换，标志位每轮都被置真，从未提前终止。

上一页的反例里，后半段早就排好了，标志位却还在白白扫描。换个角度想：一趟中最后一次交换发生的位置，意味着它之后再也没有元素需要换——那其后是不是天然有序？

最后一次交换之后的部分必然已有序，用 last 记下它，下一趟直接从那里截断扫描。

last 是本趟最靠后的交换下标：它右边的元素两两都比过且未换，天然有序，把 n 收缩到 last 即跳过整段冗余扫描。

用上一页的反例，看记录最后交换位置后，扫描区间如何一步步坍缩。

加了标志后最好情况变 O(n)，但有人误以为最坏也变了。逐维对齐，看清两版差别到底在哪。

起泡排序同时使用有序标志和最后交换位置两种优化，它们分别带来什么效果？

• ✓有序性由相邻交换逐趟向右扩张
• ✓标志位省掉无交换的多余整趟
• ✓最后交换位置让边界一次跳到位
• ✓改进都源于利用扫描中的免费信息

三个问题别急着看答案，先自己想十分钟，再对照参考思路。