GESP 四级 · GESP 202309 C++ 四级 第 3 题

对包含 $n$ 个元素的数组进行冒泡排序，平均时间复杂度一般为（ ）。

这题考的是基础排序算法的时间复杂度，别被冒泡排序要 n-1 趟的直观印象带偏，直接按比较次数推导。

最容易栽跟头的就是看到冒泡排序就选 O(n log n)，因为学生脑里总挂着‘排序算法’都该是高效的那类，或者只记住了冒泡要 n 趟就误以为总复杂度是 O(n)。其实每趟都要扫一遍，总比较次数是 n 的平方级，平均情况也逃不过这个量级。

【考点】冒泡排序机制｜时间复杂度分析｜平均情况推导

冒泡排序的核心动作就是两两比较并交换，一趟下来能把当前未排序部分的最大值‘冒’到末尾。对 n 个元素，最多需要 n−1 趟，第 i 趟要比较 n−i 次，总比较次数就是 1+2+…+(n−1) = n(n−1)/2，这已经是 Θ(n²) 了。

题目问的是平均时间复杂度。在随机排列下，任意一对元素是逆序的概率是 1/2，因此期望交换次数 = C(n,2) × 1/2 = n(n−1)/4，同样是 Θ(n²)。比较次数和交换次数量级相同，相加还是 Θ(n²)。

命题人挖坑点：

• 选项 A O(n)：利用‘冒泡只需 n−1 趟’的直观印象，把趟数误当成复杂度。
• 选项 B O(n log n)：这是归并、快排等高效排序的平均复杂度，诱导学生无差别套用。
• 选项 D 以上都不正确：一旦你确认冒泡平均就是 O(n²)，D 自然排除。

反命题思维：若改成‘已排好序的数组冒泡排序’，答案立刻变成 O(n)；改成‘最坏情况’，仍是 O(n²)。刷到这类题，先问自己：命题人想让我区分最坏/平均/最好，还是考算法归类？

考频与趋势：排序基础在题库共考过 249 题，覆盖 9 个考试级别，2023 年考了 22 题、2024 年 51 题、2025 年 57 题、2026 年 50 题，呈明显上升趋势；GESP 四级考了 39 题。复杂度分析专题共 39 题，2026 年考了 11 题，null 年 28 题，CSP 入门级占 38 题。可见复杂度分析正从入门级向更高级别渗透。

预测：基于数据，未来排序算法的复杂度辨析将更频繁地出现在选择题中，且可能结合‘最好/最坏/平均’三种情况一起考，要求考生能准确区分。暂无足够依据预测具体年份或题型变化。