【精品课件】外排序_第1页
【精品课件】外排序_第2页
【精品课件】外排序_第3页
【精品课件】外排序_第4页
【精品课件】外排序_第5页
已阅读5页，还剩4页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

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个记录进行排序。待排序文件存放在磁盘上，设盘上每个块可存放300个记录，排序过程如下所述。,首先，从磁盘上读入30个块共9000个记录放入内存，在内存中进行内排序，得

3、到一个有序串，反复进行，整个文件每9000个记录作一次内排序，可以得到6个有序串S1,S2,S3,S4,S5,S6。,每个初始有序串有30个块组成，其中每个初始有序串在图示中用3个小方框表示，每个小方框代表10个块。,其次，取3个内存块，每块可放300个记录。用其中两块作为输入缓冲区，另一块作为输出缓冲区。先对有序串S1和S2进行归并，为此，可把这两个有序串中各自的第一个块读入分别写入两个输入缓冲区，这两个输入缓冲区的记录分别是有序的。利用上一章讲述的归并排序方法的思路，对两个输入缓冲区的记录进行归并，将归并结果写入输出缓冲区。归并过程中，当输出缓冲区满时，就将输出缓冲区中的内容写入磁盘；当一个输入缓冲区腾空时，便把同一有序串的一下块读入，这样不断进行，直到有序串S1和有序串S2的归并完成。,用同样的方法将S3和S4、S5和S6分别归并。这样整个文件经这一趟归并后可以得到3个有序串。这趟归并需要对整个文件中的所有记录读写一次（即从磁盘上读入内存一次，并从内存写到磁盘一次），并在内存中参加一次归

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论