CSP-J 入门级 · CSP 2025 入门级第一轮 第 12 题

某同学用冒泡排序对数组 $\{6, 1, 5, 2, 4\}$ 进行升序排序，请问需要进行多少次元素交换？

拿到题别急着套公式，直接拿笔在草稿纸上把数组抄下来，按照冒泡排序的规则，一趟趟地‘看’相邻两个数大不大，大就换，小就不换。数清楚一共换了几次，这就是答案。

这道题最大的坑就是审题不清，把‘交换次数’看成了‘比较次数’。冒泡排序不管数组乱不乱，比较次数都是固定的 n(n-1)/2，这道题 n=5，比较次数就是 10，很容易选错。还有学生可能会漏掉某一趟排序，或者在交换时算重了，一定要老老实实模拟每一趟的过程。

这道题考查的是排序算法中的冒泡排序，重点在于区分‘比较次数’和‘交换次数’这两个概念。

冒泡排序的核心逻辑很简单：每一趟从头到尾扫描数组，相邻两个元素如果逆序（前大后小），就交换它们的位置；如果顺序，就不动。每完成一趟扫描，当前未排序部分的最大值就像气泡一样‘浮’到了末尾。题目问的是‘元素交换’的次数，这意味着只有当两个相邻元素逆序时，交换计数器才加 1；仅仅是比较了但没换，计数器不加。

我们拿数组 {6, 1, 5, 2, 4} 来模拟这个过程，一步步看：

第 1 趟（目标是把最大的 6 冒到最后）：

• 比较 6 和 1：6>1，逆序，交换。数组变 {1, 6, 5, 2, 4}。（交换次数：1）
• 比较 6 和 5：6>5，逆序，交换。数组变 {1, 5, 6, 2, 4}。（交换次数：2）
• 比较 6 和 2：6>2，逆序，交换。数组变 {1, 5, 2, 6, 4}。（交换次数：3）
• 比较 6 和 4：6>4，逆序，交换。数组变 {1, 5, 2, 4, 6}。（交换次数：4）

这一趟一共交换了 4 次。

第 2 趟（目标是把剩下的最大值 5 冒到倒数第二）：

• 比较 1 和 5：1<5，顺序，不交换。（交换次数仍为 4）
• 比较 5 和 2：5>2，逆序，交换。数组变 {1, 2, 5, 4, 6}。（交换次数：5）
• 比较 5 和 4：5>4，逆序，交换。数组变 {1, 2, 4, 5, 6}。（交换次数：6）

这一趟一共交换了 2 次。

第 3 趟（检查剩余部分）：

• 比较 1 和 2：1<2，顺序。
• 比较 2 和 4：2<4，顺序。

这一趟没有发生任何交换，数组已经是有序的 {1, 2, 4, 5, 6} 了。

第 4 趟：虽然理论上冒泡排序会跑满 n-1 趟，但此时数组已完全有序，扫描过程中不会有任何交换发生。

把各趟的交换次数加起来：4 + 2 + 0 + 0 = 6。

这里要特别提醒，很多同学容易混淆‘比较次数’和‘交换次数’。比较次数是固定的，对于 n 个元素，无论怎么乱，冒泡排序都要进行 n(n-1)/2 次比较，这道题就是 5×4/2 = 10 次。但交换次数完全取决于输入数据的逆序程度，这是本题的考点所在。命题人特意把这两个概念放在一起考，就是为了看你是不是真的理解了冒泡排序的机制，而不是死记硬背了比较次数的公式。

从考频数据来看，排序基础在题库中非常热门，2026 年就有 50 题，2025 年更是高达 57 题，说明这类题目年年都有，而且出题人很喜欢在冒泡排序的细节上挖坑，比如交换次数、比较次数、最优/最坏情况下的交换次数等。未来的趋势依然是高频，建议大家一定要亲手模拟几道冒泡排序，把‘比较’和‘交换’的动作区分清楚，这样遇到类似的单选题才能一眼看穿命题人的意图，稳稳拿分。