Appearance
排序的定义与基本概念
核心思想
排序的定义
排序（Sorting）是将一组数据元素按照关键字的递增（或递减）顺序重新排列的过程。
设有 n 个记录的序列 {R₁, R₂, ..., Rₙ}，其对应关键字为 {k₁, k₂, ..., kₙ}。排序就是确定一个排列 p₁, p₂, ..., pₙ，使得 k(p₁) ≤ k(p₂) ≤ ... ≤ k(pₙ)。
内部排序与外部排序
| 分类 | 定义 | 特点 |
|---|---|---|
| 内部排序 | 数据全部放在内存中进行排序 | 408 重点，涉及所有具体算法 |
| 外部排序 | 数据量太大，需要借助外存（磁盘）进行排序 | 涉及多路归并、置换-选择排序等 |
408 考纲中的排序算法绝大多数是内部排序，外部排序单独作为一个考点。
排序的稳定性
稳定性是区分排序算法的关键指标之一。
定义：若排序前后，关键字相同的两个元素的相对顺序保持不变，则称该排序算法是稳定的；否则是不稳定的。
排序前: 3a 1 3b 2 （3a 和 3b 关键字相同，3a 在 3b 前面）
稳定: 1 2 3a 3b （3a 仍在 3b 前面 ✓）
不稳定: 1 2 3b 3a （3a 跑到 3b 后面 ✗）判断不稳定只需要找到一个反例；判断稳定需要严格证明。
稳定性速查：
| 不稳定 | 稳定 |
|---|---|
| 快速排序 | 直接插入排序 |
| 简单选择排序 | 折半插入排序 |
| 希尔排序 | 冒泡排序 |
| 堆排序 | 归并排序 |
| 基数排序 |
口诀：快选希堆不稳定，其余全稳定。
排序算法分类
| 分类 | 核心操作 | 代表算法 |
|---|---|---|
| 插入类 | 将元素插入到已排序序列的合适位置 | 直接插入、折半插入、希尔 |
| 交换类 | 比较两个元素，若逆序则交换 | 冒泡、快速排序 |
| 选择类 | 每趟选出最小（或最大）元素放到最终位置 | 简单选择、堆排序 |
| 归并类 | 将两个或多个有序序列合并为一个有序序列 | 二路归并 |
| 分配类 | 不基于比较，利用关键字的位信息分配 | 基数排序 |
排序算法的评价指标
| 指标 | 说明 |
|---|---|
| 时间复杂度 | 关键字比较次数 + 记录移动次数 |
| 空间复杂度 | 算法执行过程中需要的辅助空间 |
| 稳定性 | 相同关键字的相对顺序是否保持 |
比较类排序的下界：基于比较的排序算法，最坏情况至少需要 O(n log n) 次比较。这可以用决策树模型证明：n 个元素有 n! 种排列，决策树至少需要 ⌈log₂(n!)⌉ 层，由 Stirling 公式得 Ω(n log n)。基数排序不基于比较，因此可以突破这个下界。
排序过程中的"趟"
408 真题常问"第 k 趟排序后的结果"，不同排序算法中"一趟"的含义不同：
| 算法 | 一趟的含义 |
|---|---|
| 插入排序 | 将第 k+1 个元素插入到前 k 个已排序元素中 |
| 冒泡排序 | 一次完整的相邻元素比较与交换过程 |
| 快速排序 | 一次 partition，确定一个 pivot 的最终位置 |
| 选择排序 | 选出当前未排序部分的最小元素，放到最终位置 |
| 堆排序 | 取出堆顶元素并调整堆 |
考研高频考点
- ⭐ 排序稳定性判断（选择题必考）
- ⭐ 各排序算法的时间/空间复杂度对比（选择题高频）
- ⭐ 根据场景选择排序算法（综合题）
- ⭐ "第 k 趟排序后的序列"的推导（选择题/填空题）
- 比较类排序的 O(n log n) 下界（概念题）
- 内部排序与外部排序的区分
易错：排序的稳定性与效率无关。快速排序平均最快但不稳定，归并排序稳定但需要 O(n) 额外空间——没有"全面最优"的排序算法，408 综合题考的就是根据具体约束做取舍。