GESP 四级 · GESP 202603 C++ 四级 第 24 题

由于选择排序和插入排序的时间复杂度均为 $O(n^2)$，在任何实际场景下两者的性能表现几乎相同，可以互相替代。

答案B。稳定排序保持相等元素的原始相对顺序。选择排序在交换时可能改变相等元素的相对位置，因此是不稳定的。

稳定排序的定义：相等元素排序后相对顺序不变。选择排序在交换时可能改变相等元素顺序，因此不稳定。

【考点】时间复杂度｜常数项差异｜输入分布

【考纲定位】GESP 四级《算法基础》模块第 3 章"排序算法性能评估"，命题人专门卡住"只看大 O 不看常数"的误区，这是绝大多数考生会凭直觉选对的致命点。题目表面是排序算法，实则考察对"时间复杂度"概念的深层理解：大 O 只描述增长阶，不反映实际运行时间。此题属于四级算法模块中"性能评估"子考点，旨在区分考生对渐近复杂度和实际运行时间的基本认知。

【解题思维】时间复杂度 O(n²) 只描述增长阶，不反映实际运行时间；选择排序每轮固定扫描未排序段，插入排序在部分有序时只需少量移动；因此插入排序在已近乎有序的数据上远快于选择排序，二者性能并不相同。插入排序最好情况 O(n)，选择排序最好情况仍为 O(n²)；平均情况两者都是 O(n²)，但插入排序常数项更小。无论输入如何，选择排序总需 O(n²) 次比较，插入排序在完全逆序时同样 O(n²) 但常数更大。

【陷阱拆解】题目把"复杂度相同"偷换为"性能相同"，选项 A 就是掉进这个语义陷阱的典型；若把题干改成"在最好情况下，插入排序复杂度 O(n) 而选择排序仍为 O(n²)"，答案会立刻翻转，说明命题人特意考察边界条件与输入分布。绝对化表述"在任何实际场景下"是最大疑点，因为性能永远依赖数据分布。若把题干改成"在平均随机输入下，两者性能几乎相同"，答案会偏向 A，但"任何实际场景"仍为绝对错误。

【反命题思维】刷到同考点题先问"命题人想考我什么"，别被大 O 符号麻痹，实际算法性能永远要看常数因子与数据分布。遇到此类绝对化表述，先找反例（如已排序数据）即可快速排除。