考频地图
排序每年 2–3 道选择题,偶有综合题。考法几乎都是:给出某种排序第几趟后的结果,或比较各算法的复杂度、稳定性、适用场景。下面每个算法都可以在模拟器里逐趟看结果。
| 考点 | 考频 | 常见问法 |
|---|---|---|
| 各算法的趟过程 | ★★★★★ | “第一趟 / 第二趟后的序列是” |
| 复杂度与稳定性 | ★★★★★ | “下列排序中不稳定的是”“与初始序列无关的是” |
| 快速排序 | ★★★★★ | “第二趟后可能的结果”“最坏情况” |
| 堆 | ★★★★☆ | “建堆后的序列”“插入 / 删除后的比较次数” |
| 外部排序 | ★★★☆☆ | “归并趟数”“败者树”“最佳归并树虚段数” |
插入类排序
直接插入:把第 i 个元素插入前面已排好的 i − 1 个元素中(从后往前比较、后移)。初始越有序越快,最好 O(n)。折半插入:用折半查找确定插入位置,比较次数降为 O(n log n),但移动次数不变,仍是 O(n²)。
希尔排序:先按增量 d 把序列分成若干子序列,各自直接插入排序;逐步缩小 d,最后 d = 1 再做一次整体插入排序。前面几趟让序列“基本有序”,最后一趟插入就很快。
- 希尔排序的趟数和结果依赖于增量序列,题目会给出;d = 1 那趟就是直接插入。
- 希尔排序不稳定(相同关键字可能被分到不同子序列),且只能用于顺序存储。
交换类排序:冒泡与快排
冒泡:每趟从后往前(或从前往后)两两比较相邻元素,逆序就交换;每趟把一个最小(或最大)元素放到最终位置。某趟没有发生交换就说明已有序,可提前结束——所以最好 O(n)。
快速排序
选一个枢轴(通常是第一个元素),一趟“划分”把比它小的放左边、比它大的放右边,枢轴落在最终位置;再对左右两部分递归。
int Partition(int A[], int low, int high) { int pivot = A[low]; // 第一个元素作枢轴,留出“坑” while (low < high) { while (low < high && A[high] >= pivot) high--; A[low] = A[high]; // 比枢轴小的移到左边坑里 while (low < high && A[low] <= pivot) low++; A[high] = A[low]; // 比枢轴大的移到右边坑里 } A[low] = pivot; // 枢轴归位 return low; }
- 最坏情况:初始序列有序或逆序,每次划分只分出一个元素,O(n²),递归栈深度 O(n)。改进:随机选枢轴或三数取中。
- 平均 O(n log n),是所有内部排序中平均性能最好的。递归栈平均 O(log n)。
- “第 k 趟后的结果”判断(2019 真题考法):每趟划分后枢轴到达最终位置。第二趟结束后,至少有 2 个元素在最终位置;若第一趟的枢轴不在端点(左右两边都要继续划分),则第二趟后至少有 3 个元素归位。
选择类排序:简单选择与堆排序
简单选择:每趟在未排序部分选出最小的,与未排序部分第一个交换。比较次数恒为 n(n − 1)/2,与初始序列无关;不稳定(交换可能跨过相同关键字)。
堆排序
大根堆:完全二叉树中每个结点 ≥ 其孩子(L(i) ≥ L(2i),L(i) ≥ L(2i + 1))。排序过程:
- 建堆:从最后一个非叶结点 ⌊n/2⌋ 到 1,依次向下调整(与较大的孩子比较,小于它就交换并继续向下)。建堆时间 O(n)。
- 输出:堆顶(最大)与最后一个元素交换,堆大小减 1,对新堆顶向下调整(O(log n))。
- 重复 n − 1 次。总 O(n log n),空间 O(1),不稳定。
堆的插入与删除(2015 真题):小根堆 8, 15, 10, 21, 34, 16, 12,删除 8 后重建堆,比较几次?→ 把末尾 12 放到堆顶:先比较两个孩子 15 和 10(1 次),再拿较小的 10 和 12 比(2 次),交换;12 来到位置 3,只有一个孩子 16,比较一次(3 次),不交换。共 3 次。插入则放在末尾向上调整,每层只和父结点比较一次。
归并、基数与计数排序
二路归并:把相邻的两个有序子序列合并成一个,第一趟子序列长 1,第二趟长 2,……,共 ⌈log₂n⌉ 趟,每趟 O(n)。需要 O(n) 辅助空间,稳定。
基数排序(LSD):不比较关键字,按位“分配 + 收集”。从最低位开始,按该位的值把元素放入 r 个队列(桶),再按桶号顺序收集;做 d 趟(d 为位数)。必须用稳定的分配方式,否则高位排序会打乱低位结果。
计数排序:关键字是 0 ~ k 的整数时,先统计每个值出现的次数,再算出每个值的最终位置(前缀和),从后往前把元素放到输出数组(保证稳定)。时间、空间 O(n + k),k 很大时不适用。
复杂度与稳定性总表
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定 | 备注 |
|---|---|---|---|---|---|---|
| 直接插入 | O(n) | O(n²) | O(n²) | O(1) | ✓ | 基本有序时最快 |
| 折半插入 | O(n log n) 次比较 | O(n²) | O(n²) | O(1) | ✓ | 只减少比较,移动不变 |
| 希尔 | — | 约 O(n^1.3) | O(n²) | O(1) | ✗ | 只能用于顺序表 |
| 冒泡 | O(n) | O(n²) | O(n²) | O(1) | ✓ | 每趟一个元素归位 |
| 快速 | O(n log n) | O(n log n) | O(n²) | O(log n) ~ O(n) | ✗ | 平均最快;有序时最差 |
| 简单选择 | O(n²) | O(n²) | O(n²) | O(1) | ✗ | 比较次数与初始序列无关 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | ✗ | 建堆 O(n);适合选前 k 个 |
| 二路归并 | O(n log n) | O(n log n) | O(n log n) | O(n) | ✓ | 趟数 ⌈log₂n⌉;外部排序基础 |
| 基数(LSD) | O(d(n + r)) | O(d(n + r)) | O(d(n + r)) | O(r) | ✓ | 不基于比较;d 位、基数 r |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | ✓ | 关键字范围 k 较小时适用 |
| 问题 | 答案 |
|---|---|
| 比较次数与初始序列无关 | 简单选择(还有基数排序不比较) |
| 趟数与初始序列有关 | 冒泡(可提前结束)、快排 |
| 每趟至少一个元素到最终位置 | 冒泡、简单选择、堆排序、快排(枢轴) |
| 基本有序时最好的 | 直接插入、冒泡(O(n)) |
| 从大量数据中选前 k 个 | 堆排序(O(n log k)) |
| 链表上能用的 | 直接插入、冒泡、简单选择、归并、基数(希尔、堆、折半插入不行) |
| 基于比较的排序时间下界 | ⌈log₂(n!)⌉ 次比较,即 Ω(n log n) |
外部排序
数据太大放不进内存时:① 分批读入内存排序,生成若干初始归并段写回磁盘;② 对归并段做多路归并。时间主要花在磁盘 I/O 上,所以要减少归并趟数。
一、败者树:让多路归并时选最小值更快
二、置换-选择排序:生成更长的初始归并段
用一个大小为 w 的工作区:每次输出工作区中“不小于上一个输出值”的最小者,再读入一个新记录;工作区里全是比上一个输出值小的记录时,当前归并段结束,开始下一段。得到的初始归并段平均长度约为 2w,且长度不等。
三、最佳归并树:长度不等的归并段怎么合并 I/O 最少
把每个归并段的长度(块数)当作权值,构造 k 叉哈夫曼树,WPL × 2 就是总读写次数。若 (n₀ − 1) % (k − 1) = u ≠ 0,需要补 k − 1 − u 个长度为 0 的虚段。例:8 个归并段做 3 路归并,(8 − 1) % 2 = 1,补 2 − 1 = 1 个虚段。
真题与自测
一、真题问法
问法 1:“对 {46, 79, 56, 38, 40, 84} 用快速排序(以第一个元素为枢轴),第一次划分后的结果是?”→ 40, 38, 46, 56, 79, 84。
问法 2(2015 真题):“小根堆 8, 15, 10, 21, 34, 16, 12,删除 8 后重建堆的比较次数?”→ 3 次。
问法 3:“下列排序算法中,元素的移动次数和关键字的初始排列次序无关的是:直接插入、冒泡、基数、快速?”→ 基数排序。
问法 4:“对 10 TB 的数据文件排序,应使用的方法是?”→ 外部排序(归并排序)。
二、折叠自测
1. 稳定的排序有哪些?
直接插入、折半插入、冒泡、归并、基数、计数。
2. 快速排序什么时候最慢?
初始序列有序或逆序(枢轴总是最大或最小),O(n²)。
3. 建堆的时间复杂度?
O(n)。
4. 二路归并排序 n = 1000 需要几趟?
⌈log₂1000⌉ = 10 趟。
5. 100 个初始归并段做 4 路归并要几趟?
⌈log₄100⌉ = 4 趟。
6. 5 个元素排序至少需要几次比较(最坏情况下)?
⌈log₂(5!)⌉ = ⌈log₂120⌉ = 7 次。
三、考前速览
稳定:插冒归基。
平均最快:快排;最坏也 O(n log n):堆、归并。
归并趟数 ⌈log_k r⌉。
① 简单选择比较次数与初始序列无关。
② 希尔、堆排序不能用于链表。
③ 快排有序时最慢,插入有序时最快。