文档介绍：李云清杨庆红揭安全

第第1111章章外排序外排序
在排序操作中,当待排序数据量很大而内存中
无法存储所有的数据时,仅仅使用内排序是无法完
成排序任务的,此时需要使用外存储器进行外排序。

1111..22 文文件件简介简介
文件的文件的逻逻辑结构辑结构

1111..33 外外排序排序------------磁盘磁盘排序排序

1111..33 外外排序排序------------磁盘磁盘排序排序
外排序中的主要方法是归并排序法。这种排序方
法主要由两大步骤构成。
第一步,根据内存可用空间的大小将待排序文件
分成若干个子文件逐个调入内存,保证每个子文件都
能利用选定的内排序算法进行排序,并将排序后的所
有有序子文件再依次写入外存。这些已排序的子文件
称为初始有序串。
第二步,对这些有序串进行逐趟归并,使有序串
的长度不断增大,而有序串的个数不断减少。反复执
行第二步,直至得到整个有序文件为止。第一步的实
质是内排序,第二步是外排序的主要内容。

1111..33..11 磁盘排序磁盘排序
外排序中使用的外存是磁盘存储器称为磁盘排序。
磁盘排序的思想用一个实例说明。
设有一个待排序文件含有54000个记录:R1,
R2,……,R54000。计算机系统中现有可用内存空间
可以对9000个记录进行排序。待排序文件存放在磁盘
上,设盘上每个块可存放300个记录,排序过程如下
所述。

首先,从磁盘上读入30个块共9000个记录放入内
存,在内存中进行内排序,得到一个有序串,反复进
行,整个文件每9000个记录作一次内排序,可以得到
6个有序串S1,S2,S3,S4,S5,S6。
每个初始有序串有30个块组成,其中每个初始
有序串在图示中用3个小方框表示,每个小方框代表
10个块。

其次,取3个内存块,每块可放300个记录。用其
中两块作为输入缓冲区,另一块