14.5.8 排序算法对比

排序算法对比是软件设计师上午题高频考点。课程里把它分成三张表来记：时间复杂度、空间复杂度、稳定性/适用场景。真正做题时不要从第一行背到最后一行，而是抓题干限制词。

时间复杂度总表

排序算法	最好情况	平均情况	最坏情况	备注
直接插入	$O(n)$	$O(n^2)$	$O(n^2)$	基本有序时最好
希尔排序	与增量有关	常记约低于 $O(n^2)$	与增量有关	软考通常记“不稳定、插入类优化”
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	有提前结束标志时最好为 $O(n)$
快速排序	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	基本有序且枢轴极端时退化
简单选择	$O(n^2)$	$O(n^2)$	$O(n^2)$	比较次数与初始状态关系小
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	大规模且空间少时有优势
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	稳定但需 $O(n)$ 辅助空间
基数排序	$O(d(n+r))$	$O(d(n+r))$	$O(d(n+r))$	$d$ 为位数，$r$ 为基数

其中最容易被题目利用的特殊情况：

• 直接插入：基本有序时接近 $O(n)$。
• 快速排序：平均很好，但最坏会退化到 $O(n^2)$。
• 归并排序：最好、平均、最坏都稳定在 $O(n\log n)$。
• 堆排序：同样最坏 $O(n\log n)$，但不稳定、空间更省。

空间复杂度对比

大多数简单内部排序只需要一个临时变量，空间复杂度为 $O(1)$。例外主要是递归栈或辅助数组。

排序算法	辅助空间	原因
直接插入、简单选择、冒泡、希尔、堆排序	$O(1)$	主要使用临时变量交换或移动
快速排序	$O(\log n)$ 到 $O(n)$	递归调用栈，取决于划分是否均衡
归并排序	$O(n)$	合并两个有序表需要辅助数组
基数排序	与 $n+r$ 有关	需要桶/队列进行分配收集

题目如果强调“空间复杂度最小”且备选有归并和堆排序，通常优先考虑堆排序。

稳定性对比

课程里给了一个好用的判断方向：选择类排序全都不稳定；带隔空交换的希尔和快速也不稳定。其余常见算法多为稳定。

稳定排序	不稳定排序
直接插入、冒泡、归并、基数	简单选择、堆排序、希尔排序、快速排序

为什么这样记：

• 简单选择、堆排序：选择最值时可能跨越相等关键字。
• 希尔排序：分组插入会隔空移动。
• 快速排序：划分时元素可能跨越枢轴和相等关键字。
• 归并排序：相等时优先取左表元素，可以保持稳定。

应用场景选择

场景	优先考虑	原因
记录数较少	直接插入、简单选择	实现简单，常数开销小
序列基本有序	直接插入	比较和移动都少，最好近似 $O(n)$
大规模且空间受限	堆排序	$O(n\log n)$ 且 $O(1)$ 辅助空间
大规模且要求稳定	归并排序	稳定，最坏仍 $O(n\log n)$
随机分布内部排序，追求平均速度	快速排序	平均运行时间通常优秀
关键字位数少、范围明确	基数排序/计数排序	利用关键字结构，不做两两比较

技术替代关系：为什么有“优化版”

原始算法	痛点	优化算法	优化后优点	仍然存在的代价
直接插入	元素只能逐格移动	希尔排序	大步预排序，减少远距离逆序	不稳定，复杂度难精确表达
冒泡排序	相邻交换效率低	快速排序	一次划分确定枢轴位置	最坏退化，不稳定
简单选择	每趟线性找最值	堆排序	用堆降低选最值成本	建堆复杂，不稳定
普通内存排序	数据量超过内存	外部归并	能处理大文件	需要关注磁盘 I/O
比较排序	受比较模型限制	基数/计数排序	特定数据下接近线性	依赖关键字范围和额外空间

选择题的排除流程

flowchart TD
  A["读题干限制词"] --> B{"要求稳定?"}
  B -- 是 --> C["排除简单选择、堆、希尔、快排"]
  B -- 否 --> D["继续看复杂度/空间"]
  C --> E{"还要求 O(n log n)?"}
  E -- 是 --> F["归并排序"]
  E -- 否 --> G["直接插入/冒泡/基数按场景判断"]
  D --> H{"基本有序?"}
  H -- 是 --> I["直接插入"]
  H -- 否 --> J{"最坏 O(n log n) 且空间 O(1)?"}
  J -- 是 --> K["堆排序"]
  J -- 否 --> L{"平均最快的内部排序?"}
  L -- 是 --> M["快速排序"]
  L -- 否 --> N["回到算法过程判断"]

典型考点辨析

题干说法	不要误选	正确理解
“最坏情况下时间复杂度最低”	快速排序	快排最坏 $O(n^2)$，归并/堆更稳
“基本有序”	堆排序	直接插入可近似 $O(n)$
“稳定且 $O(n\log n)$”	快速排序	快排不稳定，归并稳定
“辅助空间为 $O(n)$”	堆排序	常对应归并排序
“关键字均在 0 到 9”	直接插入	可考虑计数排序
“十进制三位数按位排序”	快速排序	常考基数排序，3 趟，基数 10

单选

若待排序序列已经基本有序，通常哪种排序算法能取得接近线性的时间复杂度？

A快速排序B直接插入排序C堆排序D归并排序

单选

下列哪种排序在最坏情况下仍可保持 $O(n\log n)$，且辅助空间通常为 $O(1)$，但不稳定？

A直接插入排序B冒泡排序C快速排序D堆排序

本节小结

排序对比题不能只背“谁最快”。正确做法是先看题目条件：稳定性、最坏情况、空间限制、是否基本有序、关键字范围。每个条件都会改变最优选择。