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

关于直接插入排序，下列说法错误的是（ ）

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

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

【考点】递推关系｜排序算法｜空间复杂度

🎯 考纲定位：本题出自GESP四级算法模块，命题人专门卡住"排序空间复杂度"这个高频易错点。四级要求掌握基础排序，但多数学生只背时间复杂度，对空间复杂度认知模糊。

🧠 解题思维：插入排序每次将新元素插入有序序列，只需临时变量暂存，无需开辟额外数组。因此：

• 最好情况（已有序）：n-1次比较，O(n)
• 最坏情况（逆序）：n(n-1)/2次比较，n-1次移动，O(n²)
• 平均情况：O(n²)
• 空间复杂度：就地排序，O(1)额外空间

🪤 陷阱拆解： A正确（有序时只需前驱比较） B正确（逆序需全部比较+插入移动） C正确（平均仍是二次方） D错误：直接插入是就地排序，空间复杂度为O(1)，不是O(n)。命题人利用"排序算法通常需要额外空间"的刻板印象，偷换概念。若学生只记结论不推导，必选错。

🔄 反命题思维：若将题干改为"下列属于空间复杂度O(n)的排序是？"，答案可能是归并排序或堆排序。刷到此类题先自问："这是考时间还是空间？"