8.7.2 外部排序的方法

教材导航 · 第8章

原书定位

印刷页P387起,对应PDF第399页。下文为目视整理的知识提要;完整内容见原书对照。

kk 路归并通常需 kk 个输入缓冲区和至少 1 个输出缓冲区。每个输入段当前块用完再读下一块,输出缓冲满则写回;各段均耗尽后结束该组归并。

rr 个初始段平衡做 kk 路归并,所需趟数约 s=⌈log⁡kr⌉s=\lceil\log_k r\rceil。若文件占 NN 块,每趟全量读写为 2N2N 次,含初始段形成的简化总 I/O 为 2N(1+s)2N(1+s);题目不写回最终结果或有缓存时应按实际修正。

增加 kk 可减少趟数,但会占更多缓冲,也增加每次选最小段首的工作。提高初始段长度可减少 rr,同样可能减少归并趟数。

二路外部归并的缓冲区与归并树

二路外部归并的缓冲区与归并树,原书P388。

四路外部归并过程

四路外部归并过程,原书P388。

对应练习

8.7 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P387,PDF第399页

原书对照,原书P388,PDF第400页