《数据结构教程》第12章外排序

时间：2026-01-18

《数据结构教程》第12章外排序外排序概述文件存储在外存上,因此外排序方法与各种外存设备的特征有关,外存设备大体上可分为两类,一类是顺序存取设备,例如磁带,另一类是直接存取设备,例如磁盘,其结构......

12章第12章

外排序

12.1 外排序概述 12.2 磁盘排序 12.3 磁带排序本章小结

12.1 外排序概述文件存储在外存上, 文件存储在外存上 , 因此外排序方法与各种外存设备的特征有关, 外存设备的特征有关 , 外存设备大体上可分为两一类是顺序存取设备, 例如磁带, 类 , 一类是顺序存取设备 , 例如磁带 , 另一类是直接存取设备,例如磁盘,其结构如下图所示. 接存取设备,例如磁盘,其结构如下图所示.主轴盘片柱面磁道读写头

外排序的基本方法是归并排序法. 外排序的基本方法是归并排序法 . 它分为以下两个步骤: 两个步骤: (1) 生成若干初始归并段顺串这一过程也称为生成若干初始归并段(顺串顺串),这一过程也称为文件预处理: 文件预处理: 把含有n个记录的文件个记录的文件,按内存大小分成若干 ① 把含有个记录的文件按内存大小分成若干长度为L的子文件的子文件(段 ; 长度为的子文件段); 分别将各子文件(段调入内存调入内存,采用有效的内 ② 分别将各子文件段)调入内存采用有效的内排序方法排序后送回外存. 排序方法排序后送回外存. (2) 多路归并:对这些初始归并段进行多遍归并多路归并:对这些初始归并段进行多遍归并, 使得有序的归并段逐渐扩大,最后在外存上形成整个使得有序的归并段逐渐扩大最后在外存上形成整个文件的单一归并段,也就完成了这个文件的外排序也就完成了这个文件的外排序. 文件的单一归并段也就完成了这个文件的外排序.

12.2 磁盘排序12.2.1 磁盘排序过程磁盘是直接存取设备,读写一个数据块的时间磁盘是直接存取设备读 /写一个数据块的时间与当前读/写头所处的位置关系不大. 与当前读写头所处的位置关系不大. 写头所处的位置关系不大我们通过一个例子来说明磁盘排序的过程. 我们通过一个例子来说明磁盘排序的过程.设有一个文件,内含个记录: 现在有一个文件内含4500个记录 : A1,A2,…,A4500,现在内含个记录要对该文件进行排序,但可占用的内存空间至多只要对该文件进行排序但可占用的内存空间至多只能对750个记录进行排序.输入文件被排序的文件个记录进行排序.输入文件(被排序的文件被排序的文件) 能对个记录进行排序放在磁盘上,页块长为个记录. 放在磁盘上页块长为250个记录.排序过程可如下页块长为个记录进行: 进行:

6个归并段的归并过程个归并段的归并过程

12.2.2 多路平衡归并图所示的归并过程基本上是2路平衡归并的算上图所示的归并过程基本上是路平衡归并的算一般说来,如果初始归并段有如果初始归并段有m个那么这样的归法.

一般说来如果初始归并段有个,那么这样的归并树就有要对数据进行并树就有log2m+1层,要对数据进行log2m遍扫描. 层要对数据进行遍扫描. 采用k路平衡归并时则相应的归并树有采用路平衡归并时,则相应的归并树有logkm+1层, 路平衡归并时则相应的归并树有层要对数据进行要对数据进行logkm遍扫描. 遍扫描.

做内部归并时,在k个记录中选择最小者需要顺做内部归并时在个记录中选择最小者,需要顺个记录中选择最小者序比较k-1次每趟归并u个记录需要做个记录需要做(u-1)*(k-1) 序比较次 . 每趟归并个记录需要做次比较,s趟归并总共需要的比较次数为: 次比较趟归并总共需要的比较次数为: 趟归并总共需要的比较次数为 s …… 此处隐藏：4468字，全部文档内容请下载后查看。喜欢就下载吧 ……

《数据结构教程》第12章外排序.doc 将本文的Word文档下载到电脑

下载这篇word文档

上一篇：初二数学分式方程练习题及答案[1]_2

下一篇：幼儿园大班古诗《游子吟》.