河池学院：《数据结构》课程电子教案（PPT教学课件）第10章 排序 10.8 外排序

外排序是指数据存放在外存中，数据排序时涉及内、外存数据交换的排序方法。 存储在外存上的数据以文件为基本单位。 文件 内存 数据交换 1/44

（1）生成初始归并段（顺串）：将一个文件（含待排序数据）中的数 据分段读入内存，每个段在内存中进行排序，并将有序数据段写到外存 文件上，从而得到若干初始归并段。 （2）多路归并：对这些初始归并段进行多路归并，使得有序归并段逐 渐扩大，最后在外存上形成整个文件的单一归并段，也就完成了这个文 件的外排序。 2/44

文件 内存 数据交换 外排序的时间是上述两个阶段的时间和。 主要包含内外存数据交换时间和元素比较时间（元素移动次数相对较少）。 3/44

外存设备大体上可分为两类： 外排序方法与各种外存设备的特征有关。 顺序存取设备，例如磁带。 直接存取设备，例如磁盘。 仅仅讨论磁盘排序 4/44

文件abc.dat： 5，6，3，4，9，8，1，7，10，2 进行递增排序 应用程序可用的内存空间大小w=2。 示例 5/44

5，6，3，4，9，8，1，7，10，2 外排序过程 w=2 内存 abc.dat ① abc1.dat：5，6 ② abc2.dat：3，4 ③ abc3.dat：8，9 ④ abc4.dat：1，7 ⑤ abc5.dat：2，10 6/44

k=2 内存 abc1.dat abc2.dat abc12.dat：3，4，5，6 abc1.dat：5，6 abc2.dat：3，4 7/44

w=2 内存 abc3.dat abc4.dat abc34.dat：1，7，8，9 abc3.dat：8，9 abc4.dat：1，7 abc3.dat和abc4.dat中每个元素读一次写一次（写入abc34.dat） 8/44

k=2 内存 abc12.dat abc34.dat abc1234.dat：1，3，4， 5，6，7，8，9 abc12.dat：3，4，5，6 abc34.dat：1，7，8，9 abc12.dat和abc34.dat中每个元素读一次写一次（写入abc1234.dat） 9/44

k=2 内存 abc1234.dat abc5.dat abc.dat：1，2，3，4， 5，6，7，8，9，10 abc1234.dat：1，3，4，5，6，7，8，9 abc5.dat：2，10 abc1234.dat和abc5.dat中每个元素读一次写一次（写入abc.dat） 10/44