GESP 四级 · GESP 202406 C++ 四级 第 25 题

插入排序算法中，平均时间复杂度是 $O(n^2)$，最坏的情况逆序情况下，达到最大时间复杂度。

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

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

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

GESP四级算法模块中，排序算法是重点，插入排序稳定因其简单且能体现“输入顺序对复杂度影响”而常被命题。该题故意用“平均”与“最坏”对比，检验考生是否真正理解复杂度的定义，而非死记。

插入排序的核心操作是逐次插入新元素到已排序区间，比较次数随元素位置线性增长。平均情况下每轮插入需 O(n) 次比较移动，整体为 O(n^2)；逆序输入时每次插入都需遍历已排序段末尾，达到理论最大移动次数，因此最坏情况确为 O(n^2)。平均时间复杂度指所有输入分布下的期望比较次数，而非特定输入的最优情况。算法复杂度分析是GESP四级核心内容。

若输入已有序，插入排序仅需 O(n) 次比较，但题干未限定此极端情况，故不能据此否定结论。插入排序是稳定算法，相等元素相对顺序不变，这也是其常被选作教学示例的原因。

常见陷阱是混淆“平均”与“最好”：若输入已有序，插入次数退化为 O(n)，但题干强调“平均”而非“最好”，故不能误判为错误。若误以为插入排序平均复杂度优于 O(n^2)，