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

外排序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

外排序过程（1）生成5个初始归并段W=2abc1.dat:5.6内存abc2.dat:3,4abc3.dat:8,9abc.databc4.dat:1.7abc5.dat:2.105634.981.71026/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

（2）多路归井：W=22路归井（k=2）abc1.dat :5. 6abc2.dat:3,4内存abc12.dat:3.4.5.6abc1.datk=2abc2.dat7/44

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

abc3.dat :8,9abc4.dat:1.7内存abc34.dat:1.7,8.9abc3.datW=2abc4.databc3.dat和abc4.dat中每个元素读一次写一次（写入abc34.dat）8/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

abc12.dat:3.4,5,6abc34.dat:1.7.8.9内存abc1234.dat:1,3,45,6,7,8,9abc12.datk=2abc34.databc12.dat和abc34.dat中每个元素读一次写一次（写入abc1234.dat）9/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

abc1234.dat:1.3.4.56.7.8.9abc5.dat:2,10abc.dat:1.2.3.4内存5,6.7,89,10abc1234.datk=2abc5.databc1234.dat和abc5.dat中每个元素读一次写一次（写入abc.dat）10/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