大纲对照
- 一排序的基本概念→ 01
- 二直接插入排序→ 01
- 三折半插入排序→ 01
- 四起泡排序(bubble sort)→ 02
- 五简单选择排序→ 03
- 六希尔排序(shell sort)→ 01
- 七快速排序→ 02
- 八堆排序→ 03
- 九二路归并排序(merge sort)→ 04
- 十基数排序→ 04
- 十一外部排序→ 06
- 十二排序算法的分析和应用→ 05
计数排序、桶排序等其他线性时间排序。
基本概念与插入类排序
一、基本概念
- 稳定性:关键字相同的两个元素,排序后相对次序不变就是稳定。它只是性质,不代表好坏。
- 成绩单先按学号排好,再按总分排序。如果排序算法稳定,同分的同学仍然按学号从小到大排列;不稳定的话,同分同学的先后就乱了。所以“多关键字排序”(先按次要关键字、再按主要关键字)要求后一趟必须稳定。
- 内部排序:全部数据在内存;外部排序:数据太多,要在内存和外存之间来回搬。
- 基于比较的排序,最坏情况下至少要 ⌈log2(n!)⌉ 次比较,即下界 O(n log n)。
二、直接插入排序
- 最好(已有序)O(n):每趟只比 1 次不移动;最坏(逆序)O(n²);空间 O(1);稳定。
- 适合基本有序或 n 较小的情况;顺序表、链表都可以用。
三、折半插入排序
找插入位置用折半查找,只减少了比较次数(约 O(n log n)),移动次数不变,所以时间仍是 O(n²);稳定;只能用于顺序表。比较次数与初始序列无关。
四、希尔排序
原来 49 在 49* 前面,排序后 49* 跑到了 49 前面——希尔排序不稳定的实例。
- 时间依赖增量序列,约 O(n1.3),最坏 O(n²);空间 O(1);不稳定(相同关键字可能分在不同组);只能用于顺序表。
交换类:冒泡排序与快速排序
一、冒泡排序
- 最好 O(n)(有序,1 趟 n − 1 次比较、0 次交换);最坏/平均 O(n²);空间 O(1);稳定(相等时不交换)。
- 每趟确定一个元素的最终位置。
二、快速排序(最常考)
对 49 38 65 97 76 13 27 49' 以第一个元素为枢轴做一次划分。
结果:27 38 13 49 76 97 65 49'。
- 时间:每次划分都均匀时 O(n log n);初始有序或逆序时最坏 O(n²)(每次只划出一个元素)。平均 O(n log n),是内部排序中平均性能最好的。
- 空间:递归栈,最好 O(log n),最坏 O(n)。不稳定。
- 判断“第几趟后的结果”:第 i 趟结束时,至少有 i 个元素处于最终位置(枢轴左边都比它小、右边都比它大)。第 2 趟若第一次的枢轴在边界上,只多 1 个;否则左右两边各多 1 个。
- 快排的递归次数与划分是否均匀有关,与“先处理左还是右”无关;先处理较短的子区间可把栈深度控制在 O(log n)。
- 算法题常用划分思想:找第 k 小的元素(平均 O(n))、把负数移到正数前面、荷兰国旗问题。
选择类:简单选择排序与堆排序
一、简单选择排序
- 比较次数恒为 n(n − 1)/2,与初始序列无关;移动次数最多 3(n − 1)。时间 O(n²),空间 O(1)。
- 不稳定:例
2 2' 1,第一趟 1 与 2 交换 →1 2' 2。
二、堆排序
大根堆 87 45 78 32 17 65 53 09,进行第一趟排序(输出堆顶并调整)后的序列?
09 45 78 32 17 65 53 | 87;09 下沉:与较大孩子 78 交换,再与 65 交换 → 78 45 65 32 17 09 53 | 87。- 只需要选出前 k 个最大(最小)值时,堆排序(或其思想)最合适:O(n + k log n)。
- 堆排序适合 n 很大的情况;但元素少时建堆开销不划算。
二路归并排序与基数排序
一、二路归并排序
- 时间恒为 O(n log n)(与初始序列无关);空间 O(n)(辅助数组);稳定。
- k 路归并:趟数 ⌈logk n⌉——外部排序的基础。
二、基数排序
278 109 063 930 589 184 505 269 008 083 按个位进行第一趟分配收集。
收集:930 063 083 184 505 278 008 109 589 269。
- 基数排序适合关键字位数少、n 很大的情况,例如对 10000 个 0–999 的整数排序。
计数排序、桶排序
计数排序:统计每个值出现的次数,再按次数直接输出,O(n + k),适合值域 k 不大的整数。桶排序:按值域划分桶,桶内再排序。都是非比较排序,大纲未列。
排序算法的分析和应用:必背总表
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定 | 每趟定一个终位 |
|---|---|---|---|---|---|---|
| 直接插入 | O(n) | O(n²) | O(n²) | O(1) | ✔ | ✘ |
| 折半插入 | O(n log n) | O(n²) | O(n²) | O(1) | ✔ | ✘ |
| 希尔 | 约 O(n1.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(1) | ✘ | ✔ |
| 堆 | O(n log n) | O(n log n) | O(n log n) | O(1) | ✘ | ✔ |
| 二路归并 | O(n log n) | O(n log n) | O(n log n) | O(n) | ✔ | ✘ |
| 基数 | O(d(n + r)) | O(r) | ✔ | ✘ | ||
怎么选(应用题思路)
- n 小(≤ 50):直接插入或简单选择;记录本身很大(移动代价高)时选简单选择(移动少)。
- 基本有序:直接插入、冒泡(O(n));别用快排(退化成 O(n²))。
- n 大:快排(平均最快)、堆排序(空间 O(1)、最坏也 O(n log n))、归并(要求稳定时选它)。
- n 很大、关键字位数少:基数排序。
- 链表上排序:直接插入、冒泡、简单选择、归并、基数都行;希尔、折半插入、堆排序、快排(一般实现)依赖随机访问。
| 与初始序列的关系 | 算法 |
|---|---|
| 比较次数与初始序列无关 | 简单选择、折半插入、基数(不比较)、二路归并(次数有小幅差异,量级不变) |
| 排序趟数与初始序列无关 | 直接插入(n − 1 趟)、简单选择、基数、归并 |
| 趟数与初始序列有关 | 冒泡(可提前结束)、快排(递归深度) |
外部排序
一、败者树:让 k 增大时比较不变慢
- k 路归并时每次要从 k 个段头中选最小的。普通方法要比较 k − 1 次,k 一大内部比较就变多,抵消了趟数减少的好处。
- 败者树:一棵完全二叉树,叶子是 k 个段的当前元素,内部结点记录“比赛的败者”,胜者继续向上比,根上面再放总冠军。每选出一个最小值后,只需沿着该叶子到根的路径重赛:比较 ⌈log2k⌉ 次。
- 使用败者树后,总比较次数与 k 无关,k 可以放心增大(但受内存缓冲区数量限制)。
输出 6 后,b3 段的下一个元素补进来,只需沿 b3 → 根这一条路重赛 ⌈log₂4⌉ = 2 次。
二、置换-选择排序:让初始归并段更长(r 更小)
工作区 w = 3,输入 17 21 05 44 10 12 56 32 29,求初始归并段。
第 2 段:输出 10 读入 29 → 输出 12 → 输出 29 → 输出 32:10 12 29 32。
三、最佳归并树:段长不等时怎么合并 I/O 最少
8 个初始段长度 2 3 6 9 12 17 18 24,做 3 路最佳归并,求 I/O 次数(每个记录读写各计 1 次)。
{0, 2, 3} → 5;{5, 6, 9} → 20;{12, 17, 18} → 47;{20, 24, 47} → 91。
WPL = 5 + 20 + 47 + 91 = 163 → I/O = 2 × 163 = 326。
- 败者树减少的是内部比较次数;置换-选择减少的是初始段数 r;最佳归并树减少的是段长不等时的总 I/O。别混。
- k 路归并需要 k 个输入缓冲区 + 1 个输出缓冲区(考虑并行时还要加倍)。
自测与考前速览
1. 数据基本有序时,哪种排序最快?哪种最慢?
直接插入(和冒泡)接近 O(n) 最快;快速排序退化为 O(n²) 最慢。
2. 要求稳定且 O(n log n),选哪个?
二路归并排序。
3. 空间 O(1) 且最坏 O(n log n),选哪个?
堆排序。
4. 序列 68 11 18 69 23 93 73 可能是升序快排第二趟后的结果吗?
不可能。排好后应为 11 18 23 68 69 73 93,对照发现没有任何元素处在最终位置;而快排第二趟后至少有 2 个元素已归位。
5. 败者树中 k = 8,每选出一个记录需比较几次?
⌈log28⌉ = 3 次。
6. 120 个初始段做 5 路平衡归并,需要几趟?
⌈log5120⌉ = 3 趟(5² = 25 < 120 ≤ 125 = 5³)。
7. 简单选择排序的比较次数与初始序列有关吗?
无关,恒为 n(n − 1)/2。
不稳定:快些选堆。
每趟定终位:冒泡、选择、快排、堆。
快排平均最快,有序时最坏 O(n²)。
归并 O(n) 空间换稳定;基数 O(d(n+r))。
外排:败者树增 k,置换-选择减 r,哈夫曼省 I/O。
① 折半插入只减比较不减移动。
② 建堆 O(n),堆排序 O(n log n)。
③ 快排空间不是 O(1)。
④ 直接插入的有序部分不是最终位置。
⑤ 最佳归并树要先补虚段。