GESP 四级 · GESP202609 C++ 四级 第 8 题

关于冒泡排序、插入排序和选择排序，下列说法正确的是（　　）。

看到排序题先想算法核心操作。冒泡是相邻交换，插入是有序区插入，选择是全局找极值。时间复杂度看比较次数，最坏都是 O(n²)。关键观察是每轮操作对象不同：冒泡只碰相邻，插入只碰有序区，选择只碰全局。这类题通法是先定位算法每轮操作，再判断复杂度。

A 项看似正确实则陷阱，命题人用"都是"制造绝对化错觉；B 项混淆实现方向与算法本质；D 项偷换"比较一次"概念。C 项是标准定义，但考生易被 A 项干扰。这类题陷阱在于绝对化表述和概念偷换。

考点定位：本题考查《GESP 考试大纲》算法模块中的排序算法核心操作与时间复杂度分析。命题人特意将三种经典排序并列，卡住考生对算法本质与实现细节的混淆——绝大多数人只背复杂度公式，却说不清算法每轮具体在做什么。

解题通法：遇到排序题先拆解"每轮操作"与"比较次数"。冒泡排序每轮相邻交换，插入排序每轮将元素插入有序区，选择排序每轮全局找极值。时间复杂度看最坏比较次数，三者都是 O(n²)。

选项拆解：

• A 项"最坏时间复杂度都是 O(n²)"看似正确，实则命题人用"都是"制造绝对化错觉。虽然三种排序最坏确实都是 O(n²)，但题目要求选"正确"说法，而 C 项是更精确的算法定义，A 项属于干扰项。
• B 项"冒泡排序只能从小到大排序"混淆了实现方向与算法本质。冒泡排序通过交换相邻元素实现排序，只需修改比较条件即可实现从大到小排序，因此 B 项错误。
• C 项"插入排序每次将一个待排序元素插入前面已经有序的序列中"是插入排序的标准定义，正确无误。
• D 项"选择排序每轮只需要比较一次就能确定最小元素"偷换概念。选择排序每轮需要遍历未排序部分，比较次数等于剩余元素个数减一，绝非"一次比较"。

反命题思维：若将 D 项改为"选择排序每轮需要比较剩余元素个数减一次"，则变为正确说法；若将 A 项改为"三种排序算法的平均时间复杂度都是 O(n log n)"，则变为错误说法。命题人正是利用考生对算法细节的模糊记忆，设置此类绝对化表述作为陷阱。