Lecture 29：排序
408 学习笔记：Lecture 29：排序。保留原有知识内容、公式与图示；有对应原件时提供查看和下载入口。
本页目录
排序是把记录按关键字重新排列为有序序列。408 中不只问“结果是否有序”，还常考稳定性、存储位置、时间/空间复杂度，以及外存场景下的 I/O 代价。
29.1 排序的基本概念
定义：#排序
描述：排序是将一组记录按关键字的非递减（或非递增）次序重新排列的过程。默认升序时，结果满足：
$$ K_1\le K_2\le\cdots\le K_n $$
- 排序对象是记录，关键字只是排序依据；交换或移动时记录的其他字段应随关键字一起移动。
- 关键字可以重复，因此“有序”并不能唯一确定所有记录的相对次序；这正是稳定性的意义。
- 题目未说明升降序时，要先结合比较条件或最终序列判断，不能把算法名直接等同于升序。
29.1.1 稳定性
定义：#稳定排序
描述：若排序前两个记录 $R_i,R_j$ 满足 $key_i=key_j$ 且 $R_i$ 在 $R_j$ 之前，排序后 $R_i$ 仍在 $R_j$ 之前，则该排序算法稳定；否则不稳定。
- 稳定性只讨论关键字相等的记录；关键字不同的记录相对位置改变是排序的正常目的。
- 当记录还有次关键字或附带信息时，稳定排序可保留原来的次序。例如先按姓名排序、再稳定地按班级排序，可保留同班同学的姓名序。
- 同一算法的稳定性取决于实现细节。典型例子：归并时相等元素优先取左表元素才稳定；冒泡仅在
A[j-1] > A[j]时交换才稳定。 - 判定某个具体实现“不稳定”，只需构造一组相等关键字次序被颠倒的反例；但某一次运行恰好没有颠倒相等元素，不能据此证明算法稳定，稳定性要求对所有合法输入都成立。
紫色 $3$ 原先在红色 $3$ 前：左侧排序结果仍保持这个次序，右侧结果把两者颠倒。注意图中比较的是两条记录的身份，不只是数值都等于 $3$。
29.1.2 衡量排序算法
| 指标 | 关注内容 |
|---|---|
| 时间复杂度 | 关键字比较、记录移动、递归等总耗时的量级 |
| 空间复杂度 | 排序过程额外占用的存储空间 |
| 稳定性 | 相等关键字记录的相对次序是否保持 |
| 适用存储结构 | 是否依赖随机访问、连续数组或链式结构 |
| 外存 I/O | 数据无法全部装入内存时，读写磁盘块的次数 |
- “比较次数少”不必然意味着整体更快：插入排序即使通过二分减少比较，记录后移仍可能达到 $O(n^2)$。
- “原地”有两种常见口径：严格按全部辅助空间计，只有 $O(1)$ 才算原地；若仅指在原数组内划分、不另开线性缓冲区，递归快排也常被称作原地。无论采用哪种说法，递归栈都须单独计入：快排平均 $O(\log n)$、最坏 $O(n)$，不能把整套递归实现误写为 $O(1)$ 辅助空间。
29.2 内部排序与外部排序
29.2.1 内部排序
定义：#内部排序
描述：待排序记录在排序过程中可全部放入内存的排序，称为内部排序。
- 主要分析比较、移动、递归和辅助数组等内存代价。
- 本章的插入、交换、选择、归并、基数排序均可作为内部排序算法讨论。
- 数据量并非按文件大小绝对划分，而看可用内存能否同时容纳待排数据。
29.2.2 外部排序
定义：#外部排序
描述：待排序数据量过大，无法一次全部读入内存，需要在外存与内存之间分批读写并完成排序，称为外部排序。
- 外存以块为单位读写，数据必须先进入内存才能比较和修改。
- 外部排序通常先生成多个有序的初始归并段，再做多路归并。
- 磁盘 I/O 远慢于内存运算，所以优化重点是减少归并趟数和读写块次数，而不仅是减少关键字比较。
相关知识
29.3 本节复盘
- 排序将记录按关键字有序排列；记录的其他字段必须随记录整体移动。
- 稳定性只针对相等关键字：原先靠前者排序后仍靠前才稳定。
- 内部排序关注时间和空间，外部排序还要重点计算磁盘块 I/O。
- 后续做算法对比题时，至少同时检查稳定性、最坏复杂度、辅助空间与存储结构前提。