数据结构 第12章 外排序.ppt

* * 第12章 外 排 序 12.1 外排序概述 12.2 磁盘排序 12.3 磁带排序 本章小结 12.1 外排序概述 文件存储在外存上,因此外排序方法与各种外存设备的特征有关,外存设备大体上可分为两类,一类是顺序存取设备,例如磁带,另一类是直接存取设备,例如磁盘,其结构如下图所示 外排序的基本方法是归并排序法它分为以下两个步骤 (1) 生成若干初始归并段(顺串,这一过程也称为文件预处理 把含