08-8.6.1 外部排序

👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com

---

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

外存、内存之间的数据交换

操作系统以“块”为单位对磁盘存储空间进行管理

原理

数据元素太多，无法一次全部读入内存进行排序。
使用归并排序，最少只需要在内存中分配3块大小的缓冲区即可对任意一个大文件进行排序

时间开销分析

外部排序->生成初始归并段->第一趟归并->第二趟归并->……

如何优化？

多路归并：将四个有序归并段归并为一个

重要结论：采用多路归并可以减少归并次数，从而减少磁盘I/O（读写）次数

对于 r 个初始归并段，做 k 路归并，则归并树可用 k 叉树表示
若树高为 h，则归并次数$=h-1=lo{g}_{k}r$

什么是多路平衡归并？

k路平衡归并：

1. 最多只能有 k 个段归并为一个
2. 每一趟归并中，若有 m 个归并段参与归并，则经过这一趟处理得到 $m/k$ 个新的归并段