外排序10.8外排序是指数据存放在外存中，数据排序时涉及内、外存数据交换的排序方法。内存数据交换文件存储在外存上的数据以文件为基本单位。1/44
外排序是指数据存放在外存中，数据排序时涉及内、外存数据交换的排序方法。 存储在外存上的数据以文件为基本单位。 文件 内存 数据交换 1/44
外排序基本过程(1)生成初始归并段（顺串）：将一个文件（含待排序数据）中的数据分段读入内存，每个段在内存中进行排序，并将有序数据段写到外存文件上，从而得到若干初始归并段。(2)多路归并：对这些初始归并段进行多路归并，使得有序归并段逐渐扩大，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。2/44
（1）生成初始归并段（顺串）：将一个文件（含待排序数据）中的数 据分段读入内存，每个段在内存中进行排序，并将有序数据段写到外存 文件上，从而得到若干初始归并段。 （2）多路归并：对这些初始归并段进行多路归并，使得有序归并段逐 渐扩大，最后在外存上形成整个文件的单一归并段，也就完成了这个文 件的外排序。 2/44
内存数据交换文件外排序的时间是上述两个阶段的时间和。主要包含内外存数据交换时间和元素比较时间（元素移动次数相对较少）3/44
文件 内存 数据交换 外排序的时间是上述两个阶段的时间和。 主要包含内外存数据交换时间和元素比较时间（元素移动次数相对较少）。 3/44
外排序方法与各种外存设备的特征有关。外存设备大体上可分为两类：顺序存取设备，例如磁带。直接存取设备，例如磁盘。仅仅讨论磁盘排序4/44
外存设备大体上可分为两类： 外排序方法与各种外存设备的特征有关。 顺序存取设备，例如磁带。 直接存取设备，例如磁盘。 仅仅讨论磁盘排序 4/44
示例文件abc.dat：5，6，3，4，9，8，1，7，10，2←进行递增排序应用程序可用的内存空间大小W=2。5/44
文件abc.dat： 5，6，3，4，9，8，1，7，10，2 进行递增排序 应用程序可用的内存空间大小w=2。 示例 5/44