外部排序算法由两个阶段构成:
-
按照内存大小,将大文件分成若干长度为 l 的子文件(l 应小于内存的可使用容量),然后将各个子文件依次读入内存,使用适当的内部排序算法对其进行排序(排好序的子文件统称为“归并段”或者“顺段”),将排好序的归并段重新写入外存,为下一个子文件排序腾出内存空间; -
对得到的顺段进行合并,直至得到整个有序的文件为止。
例如,有一个含有 10000 个记录的文件,但是内存的可使用容量仅为 1000 个记录,毫无疑问需要使用外部排序算法,具体分为两步:
-
将整个文件其等分为 10 个临时文件(每个文件中含有 1000 个记录),然后将这 10 个文件依次进入内存,采取适当的内存排序算法对其中的记录进行排序,将得到的有序文件(初始归并段)移至外存。 -
对得到的 10 个初始归并段进行如图 1 的两两归并,直至得到一个完整的有序文件。
注意:此例中采用了将文件进行等分的操作,还有不等分的算法,后面章节会介绍。
如图 1 所示有 10 个初始归并段到一个有序文件,共进行了 4 次归并,每次都由 m 个归并段得到 ⌈m/2⌉ 个归并段,这种归并方式被称为 2-路平衡归并。
注意:在实际归并的过程中,由于内存容量的限制不能满足同时将 2 个归并段全部完整的读入内存进行归并,只能不断地取 2 个归并段中的每一小部分进行归并,通过不断地读数据和向外存写数据,直至 2 个归并段完成归并变为 1 个大的有序文件。
对比 图 1 和图 2可以看出,对于 k-路平衡归并中 k 值得选择,增加 k 可以减少归并的次数,从而减少外存读写的次数,最终达到提高算法效率的目的。除此之外,一般情况下对于具有 m 个初始归并段进行 k-路平衡归并时,归并的次数为:s=⌊logkm ⌋(其中 s 表示归并次数)。
从公式上可以判断出,想要达到减少归并次数从而提高算法效率的目的,可以从两个角度实现:
-
增加 k-路平衡归并中的 k 值; -
尽量减少初始归并段的数量 m,即增加每个归并段的容量;
其增加 k 值的想法引申出了一种外部排序算法:多路平衡归并算法;增加数量 m 的想法引申出了另一种外部排序算法:置换-选择排序算法。两种外部排序算法会在后序章节中详细介绍。
原文始发于微信公众号(汇编语言):什么是外部排序算法
免责声明:文章中涉及的程序(方法)可能带有攻击性,仅供安全研究与教学之用,读者将其信息做其他用途,由读者承担全部法律及连带责任,本站不承担任何法律及连带责任;如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截,联系方式见首页),望知悉。
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论