《数据结构外排序专题教程.ppt》- 归并排序方法- 磁盘排序与多路平衡归并- 文件存储与外存设备- 磁盘排序过程与归并过程

数据结构外排序专题培训课件.ppt是一个关于外排序的培训课件，介绍了外排序的概述和磁盘排序的过程。外排序是一种文件存储在外存上进行排序的方法，与外存设备的特征有关，外存设备可分为顺序存取设备（如磁带）和直接存取设备（如磁盘）。外排序的基本方法是归并排序法，分为生成初始归并段和多路归并两个步骤。初始归并段是指根据内存大小将文件分成长度为L的子文件，并采用内排序方法排序后送回外存。多路归并是对初始归并段进行多遍归并，使得有序的归并段逐渐扩大，最后在外存上形成整个文件的单一归并段，完成文件的外排序。磁盘排序是一种特殊的外排序方法，磁盘是直接存取设备，通过一个例子来说明磁盘排序的过程。排序过程中，归并过程采用多路平衡归并算法，归并树的层数取决于初始归并段的个数，每次需要对数据进行遍历。