【精品课件】外排序.ppt

《【精品课件】外排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构李云清杨庆红揭安全第11章外排序在排序操作中，当待排序数据量很大而内存中无法存储所有的数据时，仅仅使用内排序是无法完成排序任务的，此时需要使用外存储器进行外排序。11.1外存储器简介11.1.1磁盘存储器11.1.2磁带存储器11.2文件简介11.2.1文件的逻辑结构11.2.2文件的存储结构11.3外排序------磁盘排序11.3外排序------磁盘排序外排序中的主要方法是归并排序法。这种排序方法主要由两大步骤构成。第一步，根据内存可用空间的大小将待排序文件分成若干个子文件逐个调入内存，保证每个子文件都能利用选定

2、的内排序算法进行排序，并将排序后的所有有序子文件再依次写入外存。这些已排序的子文件称为初始有序串。第二步，对这些有序串进行逐趟归并，使有序串的长度不断增大，而有序串的个数不断减少。反复执行第二步，直至得到整个有序文件为止。第一步的实质是内排序，第二步是外排序的主要内容。11.3.1磁盘排序外排序中使用的外存是磁盘存储器称为磁盘排序。磁盘排序的思想用一个实例说明。设有一个待排序文件含有54000个记录：R1，R2，……，R54000。计算机系统中现有可用内存空间可以对9000个记录进行排序。待排序文件存放在磁盘上，设盘上每个块可

3、存放300个记录，排序过程如下所述。首先，从磁盘上读入30个块共9000个记录放入内存，在内存中进行内排序，得到一个有序串，反复进行，整个文件每9000个记录作一次内排序，可以得到6个有序串S1,S2,S3,S4,S5,S6。每个初始有序串有30个块组成，其中每个初始有序串在图示中用3个小方框表示，每个小方框代表10个块。其次，取3个内存块，每块可放300个记录。用其中两块作为输入缓冲区，另一块作为输出缓冲区。先对有序串S1和S2进行归并，为此，可把这两个有序串中各自的第一个块读入分别写入两个输入缓冲区，这两个输入缓冲区的记录

4、分别是有序的。利用上一章讲述的归并排序方法的思路，对两个输入缓冲区的记录进行归并，将归并结果写入输出缓冲区。归并过程中，当输出缓冲区满时，就将输出缓冲区中的内容写入磁盘；当一个输入缓冲区腾空时，便把同一有序串的一下块读入，这样不断进行，直到有序串S1和有序串S2的归并完成。用同样的方法将S3和S4、S5和S6分别归并。这样整个文件经这一趟归并后可以得到3个有序串。这趟归并需要对整个文件中的所有记录读写一次（即从磁盘上读入内存一次，并从内存写到磁盘一次），并在内存中参加一次归并。反复对每两个有序串进行归并，最后得到一个有序串，即

5、为排序结果。归并过程见图11.3.2多路归并(略)