原创力文档- 1、本文档共26页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
- 5、该文档为VIP文档，如果想要下载，成为VIP会员后，下载免费。
- 6、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
第11章外部排序;[外部排序的应用对象]
保存在外存储器上的信息量很大的数据记录文件。
[外排序与内排序的差别]
内部排序充分利用内存可以随机存取的特点，如
希尔排序中，相隔di的记录关键字可作比较；
堆排序中，完全二叉树中的父R[i]与子R[2i]、R[2i+1]可比；
快速排序中，需正向和逆向访问记录序列
外存信息的定位和存取受其物理特性的限制
[外部排序的实现手段]
在排序过程中，进行多次内外存之间的数据交换;11.1外部信息的存取;磁带信息的存取;磁盘信息的存取;11.2外部排序的方法;外部排序的基本方法—归并排序法;[例]某文件共10000个记录，设每个物理块可以容纳200个记录，内存缓冲区可以容纳5个物理块
1)经过10次内排序后得到10个初始归并段R1~R10
2)采用两路归并，需四趟可以得到排好序的文件
R1R2R3R4R5R6R7R8R9R10
20002000200020002000
400040002000
外排序总时间：80002000
内排序：10tIS10000
I/O操作：100tIO(排序)+(100+80+80+100)tIO(归并)=460tIO
内部归并：(10000+8000+8000+10000)tmg=46000tmg;减少合并趟数s，以减少I/O次数
s=?logkm?
途径1：扩大初始归并段长度，从而减少初始归并段个数m
途径2：进行多路(k路)归并
增加k需要增加内存使用，还可能增加内部归并的时间;11.3多路平衡归并的实现;多路(k路)平衡归并;68
6898
96890915890
1092068121092015812
1092068129010920*81290
1422241516179214222415161792
2638302550189726383025501897
??????????:???
7路合并胜者树重构后的胜者树
将左图第一轮???小值6取走后，重构胜者树时，需要和兄弟结点比较，然后从根结点至新补入记录的叶结点的路径上的所有结点都必须更新;;[数据结构](依据：败者树为完全二叉树)
主：b[0..k]
b[0..k-1]——k个叶结点，存放k个输入归并段中当前参加归并的记录
b[k]——虚拟记录，用于建败者树（该关键字取比所有值都小的最小值minkey）
辅：ls[0..k-1]——不含叶结点的败者树
存放最后胜出的编号（ls[0]）以及所记录的败者编号
[处理步骤]
1)建败者树ls[0..k-1]
2)重复直至k路归并完毕
2.1)将b[ls[0]]写至输出归并段
2.2)补充记录(某归并段变空时,补?)，调整败者树;
文档评论（0）