为什么你的冒泡排序总是“差一点”才排对？ - 每日分享

你有没有过这样的经历：代码写完了，逻辑看起来没问题，运行结果却总是差那么一点点——要么最后一个数字没排对，要么程序多跑了一轮才停下来。你盯着屏幕反复检查，明明每一行都对，可它就是不肯乖乖听话。

如果你正在学冒泡排序，我几乎可以断定，你遇到的“差一点”，八成栽在同一个地方：循环边界。

那个让无数人翻车的 `-1`

先看一段代码，这是冒泡排序最核心的部分：

for (int j = 0; j < n - 1 - i; j++) {
    if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
    }
}

就这一行 j < n - 1 - i，我见过太多人写成 j < n - 1，甚至 j < n。写 j < n - 1 的人，结果通常是对的，但程序会多跑几轮无用的比较；写 j < n 的人，程序直接崩溃，因为 arr[j + 1] 在最后一轮会越界访问。

为什么会这样？我们得从冒泡排序的本质说起。

每一轮，到底在干什么？

冒泡排序的每一轮，做的都是一件事：把当前未排序部分的最大值，推到它最终应该在的位置。

拿 [5, 2, 9, 1] 举例。第一轮，9 这个最大值会被一路交换到末尾，数组变成 [2, 5, 1, 9]。这时候，9 已经“归位”了，它不需要再参与后面的比较。

第二轮，我们只需要处理前三个数 [2, 5, 1]，把其中的最大值 5 推到这三个数的末尾。数组变成 [2, 1, 5, 9]。

第三轮，只剩 [2, 1] 两个数，比较一次，交换，得到 [1, 2, 5, 9]。排序完成。

看到规律了吗？第 i 轮（从 0 开始数）结束时，数组末尾已经有 i + 1 个元素排好了。所以第 i 轮需要比较的范围，是前 n - i 个元素，也就是下标从 0 到 n - i - 2。因为我们要比较 arr[j] 和 arr[j+1]，所以 j 的最大值是 n - i - 2，循环条件就是 j < n - 1 - i。

少减一个 i，你的程序就会去比较已经排好的元素，做无用功；少减一个 1，你的程序就会越界，直接崩溃。

一个真实的题目：统计数字

来看一道题，它看起来跟排序关系不大，但骨子里考的就是排序的基本功。

给 n 个自然数，每个数不超过 15 亿，其中不相同的数不超过 10000 个。要求统计每个数出现的次数，并按数字从小到大的顺序输出。

样例输入是 8 个数：2, 4, 2, 4, 5, 100, 2, 100。输出应该是：

这道题有两个关键点：去重和排序。不相同的数不超过 10000 个，但 n 可能很大，所以不能简单地对所有数排序后遍历——那样遇到大量重复数字时效率太低。

一个自然的思路是：先排序，然后遍历一遍，统计连续相同数字的个数。排序这一步，冒泡排序当然可以，但 n 可能达到几十万甚至更大，冒泡排序的 O(n²) 复杂度会让程序超时。这道题真正想让你用的，是更高效的排序，比如快速排序或归并排序，配合去重统计。

但这里我想说的是：如果你连冒泡排序的边界都搞不清楚，你写快速排序的边界只会错得更离谱。 冒泡排序是训练循环边界感的绝佳工具，因为它的边界变化规律非常清晰——每一轮少比较一个，每一轮少比较一个，就这么简单。

提前结束：一个容易被忽略的优化

再看一个细节。如果某一轮比较中，一次交换都没有发生，说明什么？

说明数组已经有序了。

这时候后面的轮次全是无用功，应该直接跳出循环。代码里加一个标记：

bool swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
    if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
        swapped = true;
    }
}
if (!swapped) break;

这个优化在数组基本有序时效果惊人。比如 [1, 2, 3, 5, 4]，第一轮交换一次变成 [1, 2, 3, 4, 5]，第二轮没有交换，直接结束。原本需要四轮，现在两轮搞定。

但注意，swapped 必须在每轮开始时重置为 false。如果你把它定义在循环外面，第二轮开始它还是上一轮的 true，提前结束的判断就失效了。这是一个非常隐蔽的 bug，因为程序不会报错，只是默默地多跑几轮。

稳定性：一个看似不起眼但很重要的性质

冒泡排序是稳定的。什么意思？如果两个元素相等，排序后它们的相对顺序不变。

为什么？因为冒泡排序只在 arr[j] > arr[j+1] 时才交换。相等的时候不交换，所以相等元素的先后顺序自然保持。

这个性质在实际中很有用。比如你先按成绩排序，再按姓名排序，如果用的排序算法是稳定的，那么成绩相同的学生之间，姓名的顺序会保持不变。冒泡排序虽然慢，但它的稳定性是天然的，不需要额外处理。

从冒泡到区间合并：排序思想的应用

再看一道题，它把排序思想用在了更复杂的场景里。

给定 n 个闭区间 [ai, bi]，任意两个相邻或相交的区间可以合并。判断这些区间最终能否合并为一个区间，如果能，输出合并后的区间。

样例输入：

输出是 1 10。

这道题的思路是：先按区间左端点排序，然后依次检查相邻区间是否能合并。如果能合并，就扩展当前区间的右端点；如果不能，就说明出现了断档，无法合并成一个区间。

排序在这里的作用是：让区间的处理有顺序可循。如果不排序，你根本不知道从哪个区间开始合并，也无法判断两个区间是否“相邻”。

而排序这一步，用的正是冒泡排序的思想——把区间按左端点从小到大排好，然后从左到右扫描一遍。

新手最容易犯的四个错误

总结一下，冒泡排序的坑基本集中在这四个地方：

第一，内层循环边界写错。 正确是 j < n - 1 - i，不是 j < n - 1，更不是 j < n。

第二，交换标记忘记重置。 swapped 必须在每轮开始时设为 false。

第三，交换逻辑写反。 经典写法是 temp = a; a = b; b = temp;，不能写成 a = b; b = a;。

第四，数组下标越界。 比较 arr[j] 和 arr[j+1] 时，j+1 最大是 n-1，所以 j 最大是 n-2。循环条件必须保证这一点。

写在最后

冒泡排序可能是你学的第一个排序算法，但它绝不是最没用的那个。它的价值不在于效率，而在于它用最直观的方式，让你理解排序的本质：比较、交换、缩小范围、重复。

每一轮把最大值推到末尾，然后缩小范围，这个思想在快速排序、堆排序里都有影子。你把冒泡排序的边界搞清楚了，后面学更复杂的排序时，就不会在循环边界上栽跟头。

如果你现在还在为 n - 1 - i 纠结，不妨拿一张纸，画四个格子，手动模拟一遍每一轮 j 的取值范围。写下来，比在脑子里想清楚得多。

排序算法没有捷径，但每一步都算数。

关于作者

我是赵老师，持有 NOI 信息学奥赛教练证书，拥有 15 年以上的软件开发经验，从事信息学少儿编程教学已有 8 年时间。

这些年累计帮助多名学生通过编程特长升入自己心仪的目标学校。

如果你在编程学习上有任何疑问，欢迎联系我：18620372957（微信同号）

那个让无数人翻车的 -1