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

插入排序的时间复杂度总是比冒泡排序低。

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

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

1. 🎯 考纲定位

【考点】算法时间复杂度｜排序算法分析｜最坏/平均/最好情况

GESP四级算法模块第2章"排序"专攻内容。命题人盯住考生一个致命弱点：混淆"通常更快"与"总是更快"，把实现层面的常数差异当成理论复杂度的差异。

2. 🧠 解题思维

看到"插入排序时间复杂度总是比冒泡排序低"，第一反应必须拆解"总是"二字——这意味着对任意输入序列都要成立。

先想两种极端情况：

• 最好情况：序列已完全有序。插入排序每个元素只需判断一次就停在原位，复杂度 O(n)；冒泡排序同样只需一轮比较就能确认无需交换，复杂度也是 O(n)。两者相等。
• 最坏情况：序列完全逆序。插入排序每个元素都要从当前位置一路往前挪，复杂度 O(n²)；冒泡排序每轮把最大元素"冒"到末尾，n-1轮后完成，复杂度也是 O(n²)。两者还是相等。

既然"总是更低"要求在所有情况下都严格小于，而两种算法在最好情况已相等，命题即假。