GESP 五级 · GESP 202312 C++ 五级 第 21 题

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

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

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

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

🎯 考纲定位：本题锁定GESP五级“算法设计与分析”模块。命题人刻意用“有时”二字，卡住死记$O(n^2)$最坏情况的考生——他们只知快排最坏退化成平方级，却忽略插入排序在近乎有序数组上可做到$O(n)$线性时间。

🧠 解题思维：解题先想“有时”对应什么场景？插入排序在近乎有序数组上仅需$O(n)$，而快排若枢轴选择不当，对已排序数据退化为$O(n^2)$。比较两者：当数据近乎有序时，插入排序的线性表现显著优于快排的平方退化，故“有时更低”成立。这类题通法是：不只看最坏/最好，要对比“特定场景下的实际表现”。

🪤 陷阱拆解：错误选项B的陷阱在于“只记结论、不看场景”——死磕快排最坏$O(n^2)$却忽略插入排序$O(n)$的最优场景。题目最阴险处是“有时”二字，它不是问“是否总慢”，而是问“是否存在某种情况比快排快”。若只背“快排平均$O(n \log n)$”，就会误判。你必须意识到：对近乎有序数据，插入排序的线性优势足以碾压快排的平方退化。

🔄 反命题思维：若改问“何种数据分布下插入排序优于快排”，答案指向“近乎有序”；若将快排改为随机枢轴，平方退化概率骤降，原命题即失效。这类题刷到先问：命题人想考我“最坏/最好”的对比，还是“特定场景下实际表现”的对比？