麥据结构 李云清杨庆红揭安全
第11章外排序 在排序操作中,当待排序数据量很大而内存中 无法存储所有的数据时,仅仅使用内排序是无法完 成排序任务的,此时需要使用外存储器进行外排序 111外存储器简介 11.1.1磁盘存储器 11.1.2磁带存储器
112文件简介 11.2.1文件的逻辑结构 11.2.2文件的存储结构 113外排序磁盘排序
113外排序-磁盘排序 外排序中的主要方法是归并排序法。这种排序方 法主要由两大步骤构成。 第一步,根据内存可用空间的大小将待排序文件 分成若干个子文件逐个调入内存,保证每个子文件都 能利用选定的内排序算法进行排序,并将排序后的所 有有序子文件再依次写入外存。这些已排序的子文件 称为初始有序串 第二步,对这些有序串进行逐趟归并,使有序串 的长度不断增大,而有序串的个数不断减少。反复执 第二步,直至得到整个有序文件为止。第一步的实 质是内排序,第二步是外排序的主要内容
1131磁盘排序 外排序中使用的外存是磁盘存储器称为磁盘排序 磁盘排序的思想用一个实例说明。 设有一个待排序文件含有54000个记录:R R R 54000° 计算机系统中现有可用内存空间 可以对9000个记录进行排序。待排序文件存放在磁盘 上,设盘上每个块可存放300个记录,排序过程如下 所述