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

关于插入排序的时间复杂度，下列说法正确的是（ ）。

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

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

【考点】插入排序｜最好/最坏时间复杂度｜输入序列有序性

【解题思维】插入排序的核心是"逐个插入"——外层循环遍历元素，内层循环在已排部分找位置并移动。关键观察：内层循环的终止条件直接决定比较次数。当输入数组已完全有序时，每个元素只需与前面最后一个元素比较一次（不满足移动条件），内层循环执行 O(1) 次，外层执行 n 次，总比较次数为 n-1 次，即 O(n)。反之，当数组逆序时，每个元素都要与前面所有元素比较并移动，内层循环执行 O(i) 次，总和为 O(n²)。因此 B 选项正确——它抓住了"有序性"这一决定性因素。

【陷阱拆解】A 选项是典型"经验主义陷阱"。很多考生凭刷题经验记住"插入排序是 O(n²)"，却没意识到那是最坏情况。命题人利用的就是这种机械记忆——如果你只背结论、不理解算法行为，就会选 A。C 选项的 2ⁿ是故意误导：学生容易把插入排序和某些递归分治算法（如朴素归并）混淆，误以为内层有递归导致指数级，但插入排序是纯迭代，比较次数始终是多项式级。D 选项则同时踩了两个坑——把最好情况说成 O(n²) 违背基本事实，还强行塞进 2ⁿ这个看起来唬人的项，纯粹为了凑选项。

【反命题思维】如果题目改成"对已排好序的数组使用插入排序，移动元素次数是多少？"答案仍是 O(n)，因为移动次数等于比较次数（只比较不移动）。若问"对随机数据期望时间复杂度"，插入排序实际是 O(n²) 但常数极小，命题人有时会考这个"理论与实际的差距"——刷到此类题先问自己：题目给的数据有什么特殊性质？命题人想卡我哪一步推理？