冒泡排序的提前终止：同一批数据上少跑了几趟
提前终止改的只有一处判断
冒泡排序的骨架是两层循环：外层跑 n−1 轮，内层把相邻两个数比一遍，前大后小就交换。问题出在外层——它不管数据有没有排好，反正把 n−1 轮跑完。
演示台上的伪代码多了一件事：每轮开始前把 swapped 置为 false，只要发生过交换就改成 true；一轮跑完若 swapped 仍是 false，说明这一轮一次交换都没发生，整个数组已经有序，直接结束。
这就是提前终止的全部。它的触发条件只有一个：某整整一轮没有发生任何交换。想判断它在某份输入上生不生效，就去数这一份输入到底跑了几轮。
先数一遍站上默认的那 8 个数
打开冒泡排序演示页，默认输入是 8 个数，首帧显示「步 001 / 054」，这份输入从头跑到尾一共 54 帧。
一边点「下一步」，一边数两件事：出现了几次「第 i 轮开始」，以及计数面板里的比较次数和交换次数。在这份随机输入上数出来的是：比较 27 次、交换 13 次、实际跑了 6 轮，最后一轮提前结束。
对照满轮的情形：8 个数跑满 7 轮，比较次数是 7+6+5+4+3+2+1 = 28（每轮结束后末尾就多一个就位的数，所以内层每轮少比一次）。也就是说，这份随机输入上提前终止省下的是 1 轮、1 次比较。有，但很小。
四种输入上各跑几轮
把输入换成不同的 8 个数，分别单步数完，得到这张表：
| 输入（n=8） | 冒泡比较 | 冒泡交换 | 实际轮数 | 是否提前结束 |
|---|---|---|---|---|
| 已经有序 | 7 | 0 | 1 | 是 |
| 随机（站上默认） | 27 | 13 | 6 | 是 |
| 基本有序（末位放 1） | 28 | 7 | 7 | 否 |
| 完全逆序 | 28 | 28 | 7 | 否 |
表里的「实际轮数」是从演示的步进过程里数出来的（数「第 i 轮开始」出现了几次），它是这份演示在这个实现上的实测值，不是冒泡排序在任何实现下都成立的一般性质。
有序输入上它确实生效：8 个有序数比较 7 次、交换 0 次、1 轮就停；换成 16 个有序数是 15 次比较、1 轮；32 个有序数是 31 次比较、1 轮。都是 n−1 次比较收工。
逆序输入上它完全不生效：8 个逆序数跑满 7 轮、比较 28 次、交换 28 次；16 个逆序数跑满 15 轮、比较 120 次、交换 120 次。28 = 8×7/2，120 = 16×15/2，都是满轮的 n(n−1)/2。提前终止没有改变最坏情况，因为逆序输入每一轮都有交换，swapped 从头到尾没机会保持 false。
「基本有序」是最容易误判的一种
常见的期待是：冒泡加上提前终止，就能吃下基本有序的数据。在演示台上试一下就知道不是。取一列已经有序的 8 个数，把最小的 1 挪到末位——这就是典型的基本有序输入，结果冒泡跑满 7 轮、比较 28 次，一次都没提前结束。
原因在冒泡的推进方式：每轮只把未排序部分的最大值向右推一格。末位的 1 要一路换到最左边，需要 7 次交换，也就需要 7 轮；等到第 7 轮结束数组才刚好有序，这时已经没有下一轮可省了。提前终止省的是「排好之后剩下的空轮」，不是「排好之前的轮」。数据本身需要几轮，一轮也少不了。
同一批数据上的插入排序
把同样的输入放进插入排序演示页，再单步数一遍：
| 输入（n=8） | 冒泡比较 | 插入比较 | 冒泡交换 | 插入移动 |
|---|---|---|---|---|
| 已经有序 | 7 | 7 | 0 | 7 |
| 随机（站上默认） | 27 | 18 | 13 | 20 |
| 基本有序（末位放 1） | 28 | 13 | 7 | 14 |
| 完全逆序 | 28 | 28 | 28 | 35 |
有序时两者都是 7 次比较：提前终止让冒泡追平了插入排序的最好情况，这是这份优化真正值钱的地方。
随机时插入 18 次、冒泡 27 次，插入已经更省。差距最大的是基本有序那一行：冒泡 28 次，插入只要 13 次——优化在这里帮不上忙，换算法才有效。所以判断标准可以这么说：如果你的数据属于「排好之后还剩很多空轮」那一类，提前终止就够了；如果属于「基本有序、少数元素要长途搬家」那一类，直接在演示台上换成插入排序，别指望 swapped 标记。
顺带可以验证一个计数规律：逆序 8 个时冒泡交换 28 次，恰好等于这份输入的逆序对个数；随机 8 个时交换 13 次，也就是这份输入有 13 个逆序对。交换次数和比较次数是两件事，别混着数。
怎么自己在演示台试
- 把输入改成
1 2 3 4 5 6 7 8，单步，看它第一轮比完 7 次就停，交换计数停在 0。 - 改成
8 7 6 5 4 3 2 1，单步到结束，数「第 i 轮开始」出现 7 次，比较 28、交换 28。 - 改成
2 3 4 5 6 7 8 1，看它跑满 7 轮；再到插入排序页用同一串输入，比较只有 13 次。 - 想对照随机数据就用页面原始那 8 个数，对着 001/054 的进度自己数一遍轮数。
数完这四组，提前终止在哪种输入上少跑了几轮、在哪种输入上一轮没少，就是你自己数出来的结论了。