《数据结构》课程教学资源：第十一章 外排序

麥据结构 李云清杨庆红揭安全

第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个记录,排序过程如下 所述

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

其次,取3个内存块,每块可放300个记录。用其 中两块作为输入缓冲区,另一块作为输出缓冲区。先对 有序串S1和S2进行归并,为此,可把这两个有序串中各 自的第一个块读入分别写入两个输入缓冲区,这两个输 入缓冲区的记录分别是有序的。利用上一章讲述的归并 排序方法的思路,对两个输入缓冲区的记录进行归并, 将归并结果写入输出缓冲区。归并过程中,当输出缓冲 区满时,就将输出缓冲区中的内容写入磁盘;当一个输 入缓冲区腾空时,便把同一有序串的一下块读入,这样 不断进行,直到有序串S1和有序串S2的归并完成

Ss 圈圈圈圈察圈 第 趟 第2趟 圈後缓缓缓察 第3趟

113.2多路归并(略)