GESP 五级 · GESP 202406 C++ 五级 第 23 题

插入排序有时比快速排序时间复杂度更低。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】算法复杂度分析｜排序算法｜大 O 表示法

命题人卡住的是"平均 vs 最坏"的混淆点。学生背熟快速排序 O(n log n) 就以为它永远占优，却忘了它最坏会退化成 O(n²)。插入排序虽然理论上是 O(n²)，但在已部分有序的数据集上，它的实际运行时间接近 O(n)，而快排可能频繁触发最坏情形。这正是题目里"有时"成立的根本原因。GESP 五级"算法复杂度分析"模块明确要求理解平均与最坏情况，这正是命题人设置此题的依据。

解题链：先识别考点是"排序算法在特定数据分布下的复杂度表现"，再对比两种算法在不同输入特征（随机 vs 已序）下的行为差异，最后结合"有时"这个限定词判断命题真假。这类题的通法是：不要只看平均复杂度，必须考虑极端输入场景，尤其是数据已排序、几乎有序、逆序等边界情况。

错误选项 B 的设计很典型：利用学生只记"快排优于插入排序"的结论，却忽略"有时"这个限定。命题人用绝对化表述（"快排总是更快"）来诱导误选，实际上在已序数据上插入排序更快。最阴险的细节是"有时"这个词——它把绝对判断变成了存在性判断，只背结论的学生会完全忽略这个限定条件，直接选错。

反命题视角：如果把题干改成"在已完全逆序的数据上，插入排序比快速排序时间复杂度更低"，答案会立刻变成 B（错误），因为此时快排退化为 O(n²) 而插入排序仍是 O(n²) 常数因子更小。提醒：刷到排序算法对比题，先问自己"命题人是否在特定输入分布下讨论复杂度"，而不是盲目套用平均情况。