CSP-J 入门级 · CSP 2020 入门级第一轮 第 5 题

冒泡排序算法的伪代码如下：

输入：数组L, n ≥ k。输出：按非递减顺序排序的 L。
算法 BubbleSort：
   1. FLAG ← n //标记被交换的最后元素位置
   2. while FLAG > 1 do
   3.     k ← FLAG -1
   4.     FLAG ← 1
   5.     for j=1 to k do
   6.         if L(j) > L(j+1) then do
   7.              L(j)  ↔ L(j+1)
   8.              FLAG ← j

对 $n$ 个数用以上冒泡排序算法进行排序，最少需要比较多少次?（ ）。

这题考优化版冒泡排序的最好情况。拿到题先看FLAG初始值n，想到如果数组已经有序，第一轮遍历完就不会发生交换，FLAG会立刻变成1，循环直接结束。所以关键就是算出第一轮到底比了几次。

最容易犯的错误就是死记冒泡排序复杂度是O(n^2)，看到冒泡就以为不管怎么排都要比n(n-1)/2次。这道题特意给了优化代码，就是考你是否读懂了FLAG的作用。很多同学会忽略FLAG在没发生交换时会被重置为1，导致误以为要跑多轮；或者把题目问的'最少'看成了'最多'，算出n(n-1)/2选了A。还有人会纠结FLAG是不是从0开始，其实代码里FLAG初始就是n，第一轮k就是n-1，直接比n-1次。

这道题考什么

考排序基础里的冒泡排序优化。标准冒泡每轮把最大元素冒到最后，要跑n-1轮，总比较次数是n(n-1)/2。但这道题给的代码加了个FLAG，专门记录本轮最后发生交换的位置，下一轮就不用再比后面的元素了。题目问的是'最少'需要比较多少次，那就是问最好情况——数组原本就有序时，算法到底跑几步。

概念与命题视角

命题人挖坑很典型：代码看着像要跑多轮，但关键变量FLAG在没发生交换时会被重置为1，导致while循环直接退出。很多学生只背了'冒泡最坏O(n^2)'，却没细看优化逻辑，看到冒泡就默认要跑n-1轮，结果选了A（n^2）或者B（n-2）。这道题就是让你真正读懂伪代码，而不是靠印象做题。

思考心法：拿到题先想什么

1. 先看FLAG初始值：FLAG ← n。说明第一轮要遍历到n-1。 2. 看while条件：while FLAG > 1。只要FLAG大于1就继续，一旦FLAG变成1，循环直接结束。 3. 看for循环里有没有交换：if L(j) > L(j+1) then swap，并且swap后FLAG ← j。也就是说，只有真的交换了，FLAG才会更新成当前j，否则FLAG保持原来的值。 4. 所以如果数组已经有序，第一轮for循环跑下来，一次if都不成立，FLAG永远保持1，while条件不满足，程序结束。

具体怎么算

数组已有序时：

• 第一轮：FLAG从n开始，k = FLAG - 1 = n - 1。
• for j从1到n-1，比较相邻元素，因为有序，L(j) ≤ L(j+1)，if条件永远不成立，不会执行swap。
• FLAG在循环里从未被更新，始终保持为1。
• 第一轮比较次数就是n-1次。
• 循环结束后，while(FLAG > 1)即while(1 > 1)为假，直接退出。

因此，最少比较次数就是n-1。

避坑

• 别把'最少'看成'最多'。最多是n(n-1)/2，对应逆序，但题目明确问最少。
• 别忽略FLAG的初始值。如果误以为FLAG从1开始，就会算出0次比较，这是明显不对的。
• 别把优化版和普通冒泡混为一谈。普通冒泡即使有序也要跑n-1轮，每轮至少比1次，总次数远大于n-1；优化版只要一轮就能结束。
• 选项B是n-2，容易在计算时少算一次比较（比如把k当成n-2），但代码里k = FLAG - 1 = n - 1，所以第一轮比较次数严格是n-1，不是n-2。

考频与趋势

排序是入门级高频考点，题库共249题，覆盖9个级别。从近年数据看，2023年22题、2024年51题、2025年57题、2026年50题，呈现爆发式增长，说明命题人越来越喜欢考算法细节和边界情况。冒泡排序作为最基础算法，几乎每年都会出现，但考法在变化：以前多考最坏/平均复杂度，现在更爱考优化逻辑、最好情况、甚至让你手写代码填空。

预测

基于2023-2026年的趋势，未来几年排序相关题目会继续增多，而且更偏向考察对算法流程的精细理解，比如不同优化策略的比较、特定输入下的执行路径、或者结合其他数据结构（如链表）的排序实现。对于冒泡排序，可能不再单纯问复杂度，而是给出变形代码（如本题的FLAG优化），要求分析最好/最坏/平均情况，或者让你补全代码、判断输出。因此，复习时不能只背公式，一定要亲手模拟几遍代码，特别关注变量在循环中的变化，尤其是像FLAG这种控制循环次数的关键变量。