GESP 四级 · GESP 202606 C++ 四级 第 20 题

如果使用带 flag 的冒泡排序，且待排序数组一开始就是有序的，那么算法只需一轮扫描即可结束，时间复杂度为 $O(n)$。

答案A。考点: 数组/字符串的基本操作。

数组下标从0开始，a[n]访问的是第n+1个元素。越界不报编译错但结果不可预测。

冒泡和插入排序是稳定的，选择排序不稳定。稳定=相等元素的相对顺序不变。

【考点】冒泡排序｜时间复杂度分析｜排序优化

---

🎯 考纲定位 本题考查《GESP 四级 C++ 算法》中「冒泡排序」与「时间复杂度」两个核心知识点的结合。命题人把这两者揉在一起，就是要筛掉只背结论不追过程的学生——四级考生里，大概 70% 人知道冒泡排序是 O(n²)，但很少有人真正理解「带 flag 优化」这个考点在教材里是单独列出的。

---

🧠 解题思维 看到题先想冒泡排序的基本流程：每一轮都会把当前未排序部分的最大值「冒泡」到末尾。带 flag 的优化是：每轮开始前设 flag=false，每发生一次交换就把 flag 置为 true。一轮结束若 flag 仍为 false，说明这一轮没有交换，数组已经有序，可以提前终止循环。因此当数组初始就是有序的，第一轮扫描就不会发生任何交换，flag 保持 false，循环直接结束，共执行 n-1 次比较（一轮），时间复杂度降为 O(n)。这一套路适用于所有「提前终止」的排序优化题，比如插入排序在有序时也是 O(n)。

---

🪤 陷阱拆解 选项 A 说「只需一轮扫描即可结束，时间复杂度为 O(n)」，这恰恰是带 flag 冒泡排序在最好情况下的正确描述。命题人特意把「一轮扫描」和「O(n)」放在一起，就是为了筛掉那些只背结论的学生——很多人会误以为冒泡排序最坏 O(n²) 就代表所有情况，或者忘记 flag 的作用。最阴险的细节在于「带 flag 的冒泡排序」这个限定，如果不带 flag，即使初始有序也得跑完所有轮，时间复杂度仍是 O(n²)。如果你不理解 flag 的提前终止机制，就会掉进「冒泡排序总是 O(n²)」的陷阱。

---

🔄 反命题思维 站在命题人角度，这道题其实是在考你对排序算法「最好/平均/最坏」三种时间复杂度的区分，以及优化手段的具体实现。如果把「带 flag」改成「插入排序」，答案依然正确，因为插入排序在有序时也是 O(n)；如果把「只需一轮扫描」改成「只需一次比较」，答案就错了，因为即使有序也需要 n-1 次比较。刷到类似题时，先问自己「命题人想考我排序的哪一类时间复杂度？」，就能快速锁定考点。