GESP 四级 · GESP 202509 C++ 四级 第 22 题

虽然插入排序的时间复杂度为 $O(n^2)$，但由于单元操作相对较少，因此在小数据量的排序任务中非常受欢迎。

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

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

【考点】算法复杂度｜插入排序｜小数据量性能

1. 🎯 考纲定位 GESP 四级算法模块，考的是"算法复杂度"这个核心概念。命题人把 $O(n^2)$ 和"小数据量受欢迎"绑在一起，就是卡住那些只会背结论、不懂"渐近复杂度 vs 实际运行时间"区别的考生。

2. 🧠 解题思维 看到"插入排序"，第一时间反应出它的复杂度是 $O(n^2)$。但题目后半句强调"小数据量"，这提示我们：虽然渐近时间复杂度是平方级，可常数因子极小，且内层操作只是单次比较和移动，在小规模数据上反而比归并、快排这类递归开销大的算法更快。因此原句前后逻辑自洽，选 A 正确。

3. 🪤 陷阱拆解 若只记"$O(n^2)$ 就是慢"，就会掉进 B 的坑。命题人故意用"小数据量"这个定语，把"渐近复杂度"和"实际表现"拆开考。再比如把"插入排序"换成"冒泡排序"，虽然复杂度相同，但冒泡交换次数多，常数因子大，小数据时就不一定占优——这题就是利用这种细微差别来筛选真正理解算法本质的考生。

4. 🔄 反命题思维 如果改成"大数据量下插入排序是否仍占优"，答案立刻反转为 B，因为平方复杂度在大 $n$ 下会爆发。刷到这类题先问自己：命题人想考"复杂度定义"还是"实际性能权衡"？前者看公式，后者看场景。