GESP 五级 · GESP 202403 C++ 五级 第 17 题

插入排序的时间复杂度是 $O(N \log N)$。

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

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

【考点】排序算法复杂度比较｜算法最坏情况分析｜绝对化表述陷阱

GESP C++ 五级「排序算法」模块基础题，卡住的是把“排序”和“高效排序”混为一谈的粗心考生。

插入排序本质是线性扫描 + 局部交换：外层循环 N 次，内层 while 在最坏情况下也遍历 N 个元素。总比较次数约 \frac{N(N+1)}{2}，即 O(N²)。只有当数组已经有序时，才可能退化为 O(N)，但命题人没说“最好情况”，所以必须按最坏情况判定。真正的 O(N log N) 排序是归并、快排、堆排，它们靠分治或堆结构降低比较次数，和插入排序的机制完全不同。

命题人专门挖了“把 O(N²) 算法当成 O(N log N)”的坑。C 语言里 O(N log N) 只出现在归并、快排、堆排，插入排序永远属于 O(N²) 家族。如果你只背“排序 = O(N log N)”这种绝对化口诀，就会掉进这个语义陷阱——题目里那个“是”字太绝对，没有任何限定词，这就是硬伤。

若把“插入排序”换成“归并排序”，答案就反了。刷到类似题先问自己：命题人想考我“算法复杂度”还是“算法分类”？