14.5.1 排序算法知识点概述

排序算法不是一张孤立的复杂度表。课程里强调：软件设计师考试既会考“这个排序属于哪一类、稳定吗、复杂度是多少”，也会给一趟排序后的序列，让你判断算法过程。因此复习排序要同时抓住三层信息：分类、过程、代价。

排序题究竟在考什么

上午题更偏结论匹配：看到“基本有序”想到直接插入，看到“稳定且 $O(n\log n)$”想到归并，看到“大顶堆/小顶堆”想到堆排序。下午题若出现排序，常与分治思想、快速排序或归并排序代码结合，要求补充边界、循环条件或某一趟结果。

考查角度	题干常见信号	解题抓手
分类	插入类、选择类、交换类、归并、基数	先确定算法家族，再看优化版本
复杂度	最好、平均、最坏、辅助空间	注意“基本有序”“最坏情况”“大规模”这些限制词
稳定性	相等关键字、相对顺序	有隔空交换通常不稳定
过程模拟	一趟排序、建堆、归并、按位收集	按算法动作一步步写，不凭印象跳步
场景选择	数据量小、关键字范围小、要求稳定	条件优先于默认性能排名

排序分类的主线

排序的基本动作可以理解成五种思想。

类别	代表算法	核心动作	课程提醒
插入类	直接插入、希尔排序	把新元素插入前面已有序的局部序列	直接插入对基本有序序列很友好
选择类	简单选择、堆排序	每趟选出最值，放到最终位置	堆排序是选择思想的结构化优化
交换类	冒泡、快速排序	通过交换让逆序元素逐步归位	快排平均优秀，但最坏会退化
归并排序	二路归并	先分解，再合并有序子表	稳定，但需要 $O(n)$ 辅助空间
基数排序	LSD/MSD 基数排序	按关键字的各位分配、收集	不是比较排序，适合位数少且范围明确的关键字

用“技术迭代”的眼光看，很多优化算法都是在解决朴素算法的瓶颈：

朴素版本的问题	改进方向	新算法的代价
直接插入移动距离短，远处元素归位慢	希尔排序用大增量先做粗调整	增量分组会破坏稳定性，复杂度依赖增量序列
简单选择每趟都线性扫描找最值	堆排序用完全二叉树维护最值	建堆/调整过程更复杂，不稳定
冒泡一趟只移动相邻逆序	快速排序用枢轴一次划分大片区域	枢轴选得差会退化到 $O(n^2)$
比较排序受比较次数约束	基数/计数利用关键字范围直接分桶	依赖关键字位数、基数和额外存储

先记“大局表”，再理解原因

排序算法	类别	平均时间	最坏时间	辅助空间	稳定性	适用信号
直接插入	插入类	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	基本有序、规模较小
希尔排序	插入类	约与增量有关	约与增量有关	$O(1)$	不稳定	想改进直接插入
简单选择	选择类	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	过程简单、交换次数少
堆排序	选择类	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定	大规模、空间要求低
冒泡排序	交换类	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	基本有序时可提前结束
快速排序	交换类	$O(n\log n)$	$O(n^2)$	$O(\log n)$ 到 $O(n)$	不稳定	随机分布、内部排序平均最快
归并排序	归并	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定	稳定性要求高、外部排序
基数排序	分配收集	与位数、基数有关	与位数、基数有关	与基数和数据量有关	稳定	关键字位数少、取值范围明确

一张判断图

flowchart TD
  A["排序题条件"] --> B{"要求稳定?"}
  B -- 是 --> C{"还要求 O(n log n)?"}
  C -- 是 --> D["优先想归并排序"]
  C -- 否 --> E["直接插入、冒泡、基数等再看场景"]
  B -- 否 --> F{"强调空间少且大规模?"}
  F -- 是 --> G["堆排序"]
  F -- 否 --> H{"基本有序?"}
  H -- 是 --> I["直接插入常为最佳"]
  H -- 否 --> J{"平均速度优先?"}
  J -- 是 --> K["快速排序"]
  J -- 否 --> L["按过程/分类继续排除"]

考试中的常见陷阱

1. “最坏情况”与“平均情况”不能混用。快速排序平均 $O(n\log n)$，但最坏是 $O(n^2)$；归并和堆排序最坏仍是 $O(n\log n)$。
2. 稳定性只讨论相等关键字。如果关键字全不相等，稳定性看不出来，但算法本身仍有稳定/不稳定之分。
3. 空间复杂度看辅助空间，不看输入表本身。原始数组是输入，不计入辅助空间；归并需要额外数组，所以是 $O(n)$。
4. “基本有序”是直接插入的强信号。这类题不要被“大规模”一词单独带走，题干如果强调基本有序，插入排序可能近乎线性。

单选

若题目要求排序算法稳定，并且最坏情况下时间复杂度仍为 $O(n\log n)$，最可能选择哪种算法？

A快速排序B归并排序C简单选择排序D希尔排序

本节小结

排序算法要用“分类 -> 过程 -> 复杂度 -> 稳定性 -> 场景”的顺序理解。只背表容易在过程题和限制条件题中失分；理解每种算法为什么这样移动数据，复杂度和稳定性结论才会变得可靠。