14.5.2 排序的基本概念
排序是把一组记录按照某个关键字重新排列。课程里先讲概念，是因为后面所有算法的复杂度和稳定性都依赖这些前提：排序的是“记录”，比较的是“关键字”，移动时可能移动整条记录。
记录、关键字与有序序列
一条记录可以有很多数据项，例如学生记录包含学号、姓名、成绩、班级。排序时选其中一个或多个数据项作为依据，这个依据叫关键字或关键码。
| 概念 | 说明 | 例子 |
|---|---|---|
| 记录 | 被排序的完整对象 | 一名学生、一条订单、一条日志 |
| 关键字 | 用于比较的字段 | 成绩、时间戳、订单金额 |
| 主关键字 | 能唯一标识记录的关键字 | 学号、身份证号 |
| 次关键字 | 不能唯一标识，但可参与排序 | 成绩、年龄 |
| 升序/递增 | 从小到大排列 | |
| 降序/递减 | 从大到小排列 |
考试中常把“关键字相同的记录”拿来考稳定性。注意：两个记录的关键字相同，不代表它们是同一条记录。例如 21a 与 21b 都以 21 为关键字，但 a、b 标记了它们原来的先后顺序。
稳定性：相等关键字的相对次序
如果排序前 21a 在 21b 前面，排序后仍然是 21a 在 21b 前面，这个排序过程就是稳定的；如果排序后变成 21b 在 21a 前面，就是不稳定的。
mermaid
flowchart LR
A["排序前: 35, 21a, 48, 21b"] --> B{"按关键字升序"}
B --> C["稳定结果: 21a, 21b, 35, 48"]
B --> D["不稳定结果: 21b, 21a, 35, 48"]稳定性的重要性在于多关键字排序。比如先按“姓名”排，再按“班级”稳定排序，班级相同的记录内部还能保留姓名顺序。如果第二趟排序不稳定，第一趟结果可能被破坏。
内部排序与外部排序
| 分类 | 判断标准 | 常见算法/思想 | 关注点 |
|---|---|---|---|
| 内部排序 | 待排序记录能全部放入内存 | 插入、选择、交换、堆、归并、基数 | 比较次数、移动次数、辅助空间 |
| 外部排序 | 数据太大，需要外存参与 | 外部归并排序、多路归并 | 磁盘读写次数、归并趟数 |
软考中级通常重点讲内部排序，但归并思想也会自然延伸到外部排序：内存中先排出多个有序段，再把有序段归并成更大的有序文件。
排序算法的评价维度
一个排序算法不能只看平均时间复杂度。课程里反复提醒，题目可能从不同角度设限制。
| 维度 | 你要问的问题 | 典型影响 |
|---|---|---|
| 时间复杂度 | 比较和移动大概执行多少次？ | 大规模数据时决定运行速度 |
| 空间复杂度 | 除输入外还需要多少辅助存储？ | 内存紧张时堆排序优于归并 |
| 稳定性 | 相等关键字是否保持相对顺序？ | 多关键字排序、业务记录排序 |
| 初始状态 | 原序列是否基本有序？ | 直接插入最好情况可接近 |
| 数据规模 | ||
| 关键字范围 | 关键字是否在有限范围内？ | 计数/基数排序可绕开比较排序 |
“隔空交换”与稳定性的直觉
直接相邻比较并且在相等时不交换，通常能保持稳定；如果算法可能把远处元素直接换到前面，就容易破坏相等关键字的原始顺序。
例如简单选择排序从后面找到一个最小值，直接与当前位置交换。若当前位置前后存在相等关键字，这个远距离交换可能让同关键字记录越过彼此，所以简单选择排序不稳定。
考试判断口诀
- 看到“相等关键字相对次序不变”，答稳定性。
- 看到“全部记录在内存中排序”，答内部排序。
- 看到“数据量太大、外存、文件”，考虑外部排序和归并。
- 看到“关键字取值有限，例如 0 到 9”，考虑计数或基数思路。
- 看到“基本有序”，优先考虑直接插入排序。
排序算法的稳定性指什么？
本节小结
排序的基础概念要抓三点：排序依据是关键字，稳定性只关心相等关键字，内部/外部排序的分界是数据是否需要外存参与。后面比较各种算法时，所有结论都要回到这些概念上。