软件设计师 · 数据结构 · 排序算法

排序稳定性和时间复杂度怎么一起判断？

排序题最容易出现一种情况：你背会了时间复杂度表，却在稳定性上丢分；或者记住了稳定排序，又忘了题目问的是平均复杂度。软件设计师考试喜欢把“复杂度”和“稳定性”放在同一道题里考，所以复习时要把它们放在同一张脑图里。

软件设计师专题软考题库编辑部持续更新

内容整理：软考题库编辑部最近更新：2026-06-13

稳定性说的是相等关键字的相对次序

稳定排序不是说算法运行过程很稳定，而是说两个关键字相等的元素，排序以后相对先后顺序不变。比如两名同学成绩都是 90 分，原来 A 在 B 前面，按成绩排序后 A 仍然在 B 前面，这才叫稳定。

考试题干如果出现“相同关键字”“相对次序不变”“二次排序”，大概率在考稳定性。这个时候不要被 O(n log n) 之类复杂度符号带走，先判断题目问的性质是什么。

快速排序是最典型的易错点。它平均情况下效率很好，通常为 O(n log n)，但在某些划分极不均衡的情况下，最坏时间复杂度可能退化到 O(n²)。如果题干明确写“平均情况下”，不要因为记得最坏情况就选错。

归并排序时间复杂度比较稳定，通常是 O(n log n)，并且可以做到稳定，但它往往需要额外空间。堆排序时间复杂度也能做到 O(n log n)，空间表现不错，但稳定性通常不是优势。题目问哪一个维度，答案就按哪一个维度判断。

先看题目问时间、空间，还是稳定性。

再看它限定的是平均情况、最坏情况，还是一般性质。

最后才回到具体算法名称，不要一眼看到快排就条件反射。

稳定性最有价值的场景，是多关键字排序。比如先按姓名排序，再按成绩排序，如果第二次按成绩排序是稳定的，那么相同成绩内部还能保留前一次姓名排序的结果。这就是“相等关键字相对次序不变”的实际意义。

如果只是把一组数字从小到大排出来，稳定性看起来没那么明显；但一旦元素除了关键字还有其他属性，稳定性就会影响最终结果。软件设计师题目喜欢用“记录”“关键字”“相同关键字”这些词来暗示这一点。

排序算法没有一个在所有场景都绝对最好。快速排序平均性能好，但稳定性和最坏情况要注意；归并排序稳定、时间表现稳定，但空间开销较大；堆排序时间复杂度好，适合关注空间和最坏情况，但不是稳定排序的代表。

复习时建议把每个算法写成一句话，而不是只背表格。比如：快排平均快但通常不稳定，归并稳定但要额外空间，堆排最坏也能 O(n log n) 但不稳定。这样遇到综合题时，就能按题干要求取舍。