人民邮政出版社：《数据结构》课程教学资源（PPT课件）第11章 外排序

痰据结柄 李云清杨庆红揭安全

李云清 杨庆红 揭安全

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

第11章 外排序 在排序操作中，当待排序数据量很大而内存中 无法存储所有的数据时，仅仅使用内排序是无法完 成排序任务的，此时需要使用外存储器进行外排序。 11.1外存储器简介 11.1.1磁盘存储器 11.1.2磁带存储器

12文件简介 1121文件的逻辑结构 1122文件的存储结构 113外排序磁盘排序

11.2 文件简介 11.2.1 文件的逻辑结构 11.2.2文件的存储结构 11.3 外排序------磁盘排序

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

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

1131磁盘排序 外排序中使用的外存是磁盘存储器称为磁盘排序。 磁盘排序的思想用一个实例说明。 设有一个待排序文件含有54000记录只 R 54000° 计算机系统中现有可用内存 可以对9000个记录进行排序。待排序文件存放在磁盘 上,设盘上每个块可存放300个记录,排序过程如下 所述

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

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

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

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

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

圈圈圈圈圈缓圈 第 趟 圈多缓缓圈教缓圈教 第2趟 圈缓缓缓象 第3趟

用同样的方法将S3和S4、S5和S6分别归并。这样 整个文件经这一趟归并后可以得到3个有序串。这趟归 并需要对整个文件中的所有记录读写一次（即从磁盘 上读入内存一次，并从内存写到磁盘一次），并在内 存中参加一次归并。反复对每两个有序串进行归并， 最后得到一个有序串，即为排序结果。归并过程见图

1132多路归并(略)

11.3.2 多路归并(略)