GESP 七级 · GESP 202503 C++ 七级 第 5 题

下列关于排序的说法，正确的是（ ）。

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

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

【考点】排序算法｜时间复杂度｜稳定性

本题考查排序算法的稳定性与时间复杂度，属于 GESP 第 7 级算法模块中的"排序"知识点。命题人意在卡住考生对算法本质理解的薄弱点——许多同学只背结论，却混淆了各排序算法的时间复杂度与稳定性。

看到题先回忆各排序算法特性：选择排序 O(n²)，归并排序 O(n log n) 且稳定，快速排序平均 O(n log n) 但最坏 O(n²) 不稳定，插入排序最好 O(n) 且稳定。关键观察是归并排序在合并两个有序子序列时，若元素相等，则先出现的元素排在前面，因此是稳定的。通法：判断排序说法时，先回忆时间复杂度（最好/平均/最差）和稳定性定义，再逐个核对。

A 错在将选择排序误认为"最快"（实际 O(n²)）；C 错在最差情况快速排序应为 O(n²) 而非 O(n)；D 错在最好情况插入排序应为 O(n) 而非 O(n²)。命题人利用绝对化表述（"最快""最差""最好"）和偷换概念（混淆稳定性与时间复杂度）制造陷阱，只背结论者必掉坑。

若将题干改为"下列排序算法中时间复杂度为 O(n log n) 且稳定的有？"，答案为归并排序与堆排序；若改为"快速排序最坏情况下的时间复杂度是？"，答案为 O(n²)；若改为"插入排序最好情况下的时间复杂度是？"，答案为 O(n)。刷到类似题时，先问自己"命题人想考我什么"，再调动算法本质而非死记结论。