数据结构——内部排序与外部排序：八大排序对比与多路归并

前面两篇讲了插入、快速、归并、堆排等主要排序算法这篇做一次完整的对比总结并讲 408 常考的外部排序。一、八大排序算法对比排序算法平均时间最好最坏空间稳定特点直接插入O(n²)O(n)O(n²)O(1)✅数据基本有序时很快希尔排序O(n^1.3)O(n)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(nr))O(d(nr))O(d(nr))O®✅适合整数排序选型建议数据量小1000插入排序简单且稳定 数据量中等1000-10万快速排序最快的通用排序 数据量大且需稳定10万归并排序 数据量大且需最坏也有保证堆排序 整数且范围小基数排序 内存不够外部排序多路归并二、排序算法的稳定性分析哪些排序是稳定的稳定插入排序、冒泡排序、归并排序、基数排序 不稳定选择排序、希尔排序、快速排序、堆排序为什么稳定很重要// 场景先按姓名排序再按分数排序// 如果排序是稳定的那么同分的人依然保持姓名顺序// 第一遍按姓名排序// 张三(85), 李四(90), 王五(85)// 第二遍按分数排序稳定排序// 张三(85), 王五(85), 李四(90)// 张三和王五的同分情况下仍保持第一次排序的姓名顺序三、外部排序当数据量太大无法全部加载到内存时需要使用外部排序。1. 外部排序的基本思想内存放不下用磁盘做中转 外部排序 排序阶段 归并阶段 排序阶段将大文件分成若干小块分别读入内存排序后写回 归并阶段将多个有序小块合并成一个有序大文件2. 两路归并初始数据4个有序段R1, R2, R3, R4每个段已内部排序 第一趟归并 R1 R2 → S1合并两个有序段结果仍有序 R3 R4 → S2 第二趟归并 S1 S2 → 最终有序文件 需要2个内存缓冲区每路一个 IO次数每趟归并读写所有数据一次 总共IO次数 2 × 趟数 × 数据量3. 多路归并k 路归并使用 k 个缓冲区每次从 k 个段中选最小的一个输出 优势减少归并趟数 m 个初始段k 路归并 → 需要 logₖ(m) 趟 代价需要更大的内存缓冲区 每路一个缓冲区k 路需要 k 个缓冲区 选最小元素需要比较 k-1 次或用败者树优化4. 败者树败者树用于在多路归并中快速选出最小的元素。败者树的工作原理 叶子节点存放 k 个段当前比较的元素 内部节点存放两两比较的败者较大的元素 根节点存放最终胜出者最小的元素 当选出最小元素后该段的下一个元素补充到叶子节点 重新调整败者树只需比较 log₂(k) 次 比每次比较 k-1 次快得多5. 外部排序的时间开销/** * 外部排序的总时间 * 内部排序时间 磁盘IO时间 归并比较时间 * * 主要瓶颈在磁盘 IO 上 * 因此优化重点是减少 IO 次数 * * 减少 IO 的方法 * 1. 增大内存缓冲区减少初始段数量 * 2. 增加归并路数减少归并趟数 * 3. 使用败者树减少内部比较时间 */6. 最佳归并树类似哈夫曼树但叶节点权值表示归并段长度 每次合并长度最短的 k 个段 总IO次数 Σ段长度 × 归并深度 与哈夫曼树的区别 哈夫曼树每次合并2个最小节点 最佳归并树每次合并k个最小节点 注意k 路归并的最佳归并树 初始段数 m 必须满足 (m-1) % (k-1) 0 如果不满足需要补充长度为 0 的虚段7. 置换选择排序置换选择排序用于生成更长的初始归并段 传统方法内存最多排多少段就有多长 置换选择可以生成≈2倍内存大小的段 思想 内存中维护一个堆 每次输出堆顶元素后从输入文件读入一个新元素 如果新元素 ≥ 刚输出的元素加入堆中继续 否则标记为下一段当前段结束 这样生成的段平均长度 ≈ 2 × 内存容量 初始段减少归并趟数也减少四、408 考研常见考题题1排序算法的稳定性判断题目对 {4, 2, 4, 1, 5} 用快速排序 第一次划分后{1, 2, 4, 4, 5} 两个 4 的相对位置看划分算法 如果选第一个元素 4 作为 pivot 划分后第一个 4 和第二个 4 可能交换位置 → 不稳定的题2外部排序的 IO 次数1000 个记录内存可容纳 100 个 初始段数1000/100 10 个 4 路归并的趟数log₄(10) 2 趟第一趟10→3第二趟3→1 总 IO 次数2 × 2 × 1000 4000 次 每趟读写各一次两趟共读写各两次题3最佳归并树的构造初始段长度{8, 6, 5, 4, 3, 2} 3 路归并 (6-1)%(3-1)5%2≠0需要补充1个虚段 构造 第一轮选最小的 3 个 → 2349 → {9, 8, 6, 5} 第二轮选最小的 3 个 → 56819 → {19, 9} 第三轮选最小的 3 个 → 919028 → {28} 总 IO 次数 86543228 56每块读写各算一次五、排序算法选择决策树数据量很小50 ├── 是 → 插入排序代码简单常数小 └── 否 → 数据基本有序 ├── 是 → 插入排序O(n) └── 否 → 内存够用 ├── 是 → 快速排序 └── 否 → 外部排序多路归并 需要稳定排序 ├── 是 → 归并排序 └── 否 → 快速排序或堆排序总结内部排序核心比较和交换 外部排序核心归并 排序算法选择根据数据规模、是否有序、是否稳定408 重点八大排序的时间空间复杂度对比必考、外部排序的 IO 次数计算、最佳归并树构造。 觉得有用的话点赞 关注【张老师技术栈】吧每周更新 Java/Python/爬虫 实战干货不让你白来。