夜雨聆风学习资料网 资料列表 开通 VIP 用登录 / 注册 ⌄
PDF

010-第十讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt

查看资料信息、公开预览和下载状态。

共 69 页PDF · 1.2MB
下载

文档在线预览

公开展示前 10 页
100%
1
《010-第十讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第1页预览
2
《010-第十讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第2页预览
3
《010-第十讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第3页预览
4
《010-第十讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第4页预览
5
《010-第十讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第5页预览
6
《010-第十讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第6页预览
7
《010-第十讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第7页预览
8
《010-第十讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第8页预览
9
《010-第十讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第9页预览
10
《010-第十讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第10页预览

本文档共 69 页 剩余 59 页未展示,请下载后查阅

下载

文档文本内容

第十讲:外部排序
主讲人:刘财政
B站:@计算机考研刘财政考纲要求CON T EN T S
目录
考点一 外部排序的概念
考点二 置换-选择排序算法
考点三 多路平衡归并和败者树
考点四 最佳归并树CON T EN T S
目录
考点一 外部排序的概念
考点二 置换-选择排序算法
考点三 多路平衡归并和败者树
考点四 最佳归并树【基本概念】考点一:外部排序的概念
外排序是指数据存放在外存中,数据排序时涉及内、外存数据交换的
排序方法。
内存
数据交换
文件
存储在外存上的数据以文件为基本单位。考点一:外部排序的概念
外排序的基本方法是归并排序法。它分为以下两个步骤:
(1)生成若干初始归并段(顺串):这一过程也称为文件预处理。
一种常规的方法如下:
 把含有n个记录的文件,按内存大小w分成若干长度为w的子文件
(归并段);
 分别将各子文件(归并段)调入内存,采用有效的内排序方法排序
后送回外存。 产生m=n/w个初始归并段。
某内排序算法
abc .dat
1
abc.dat 内存 abc .dat
2 均有序
…
abc .dat
m考点一:外部排序的概念
(2)多路归并:对这些初始归并段进行多遍归并,使得有序的归并段逐
渐扩大,最后在外存上形成整个文件的单一归并段,也就完成了这个文件
的外排序。
采用归并算法
abc .dat
1
abc .dat 内存 有序
2 abc.dat
…
abc .dat
m【基本过程】考点一:外部排序的概念
磁盘中的F ,文件包括待排序的数据,通过相关算法将F 文件中的记录一部分
in in
一部分地调入内存处理,产生若干个文件F ~F ,它们都是有序的,称为顺串(runs)。
1 n
然后再次将F ~F ,文件中的记录调入内存,通过相关归并算法产生一个有序文件
1 n
F ,从而达到数据排序的目的。
out考点一:外部排序的概念
设有一个文件F ,内含4500个记录,即R ,R ,…,R ,现在要对该文件
in 1 2 4500
进行排序,但内存空间最多只能对w=750个记录进行排序,并假设磁盘
每次读写单位为250个记录的数据块,其排序过程如下。考点一:外部排序的概念
(1)生成初始归并段:每次读3个数据块(750个记录)进行内排序(由于这些
数据全部在内存中,可以采用第八讲介绍的内排序方法),整个文件得到6
个归并段F ~F 。(即初始归并段),把这6个归并段存放到磁盘上。
1 6
某种内排序方法
产生6个长度为750
文件Fin.dat
个记录的有序文件
容量为750个记录
(含4500个记录) F ~F 。
1 6考点一:外部排序的概念
(2)二路归并:将内存工作区分为3块,每块可容纳250个记录,把其中两块
作为输入缓冲区,另一块作为输出缓冲区。
可用内存空间大小为750个记录
可以使用多种归并方案来完成考点一:外部排序的概念
归并段F 和F ,进行归并,为此可把这两个归并段中每一个归并段的
1 2
第一个物理块(250个记录)读入输入缓冲区,再把输入缓冲区的这两个归
并段的物理块加以归并(采用内排序的二路归并过程),送入输出缓冲区。
当输出缓冲区满时,就把它写入磁盘;当一个输入缓冲区腾空时,便把同一
归并段中的下一物理块读入,这样不断进行,直到归并段F 与归并段F ,的
1 2
归并完成为止(将其结果存放在F 文件中)。
7
F F
1 2
F
7考点一:外部排序的概念
归并F 和F (结果存放在F 文件中),最后归并F 和F (结果存放在F 文
3 4 8 5 6 9
件中),到此为止归并过程已对整个文件的所有记录扫描一遍。扫描一
遍意味着文件中的每一个记录被读写一次(即从磁盘上读入内存一次,并
从内存写到磁盘一次),并在内存中参加一次归并。这一遍扫描所产生的
结果为3个归并段F ~F ,每个段含6个物理块,合1500个记录。
7 9
F F
3 4
F
8考点一:外部排序的概念
归并F 和F (结果存放在F 文件中),最后归并F 和F (结果存放在F 文
3 4 8 5 6 9
件中),到此为止归并过程已对整个文件的所有记录扫描一遍。扫描一
遍意味着文件中的每一个记录被读写一次(即从磁盘上读入内存一次,并
从内存写到磁盘一次),并在内存中参加一次归并。这一遍扫描所产生的
结果为3个归并段F ~F ,每个段含6个物理块,合1500个记录。
7 9
F F F F F F
1 2 3 4 5 6
F F F
7 8 9考点一:外部排序的概念
其中的F 和F 两个归并段归并起来(将其结果存放在F 文件中,其大小为
7 8 10
3000个记录的归并段);最后将F 和F 两个归并段进行归并,从而得到所求
9 10
的排序文件 F 。
out考点一:外部排序的概念
F F F F F F
1 2 3 4 5 6
F F F
7 8 9
F
10
F
out
注意:
① 内存大小为750个记录,但任意大小的两个归并段都可以进行归并。
② 每归并一次,参与归并的每个记录都要读一次和写一次。考点一:外部排序的概念
F F F F F F
1 2 3 4 5 6
F F F
7 8 9
F 和F 中
1 2
每个记录
读3次、 F
10
写3次
F
out
总的读记录数(写记录数与之相同):
[(F +F +F +F 的记录数)×3+(F +F 的记录数)×2]=12000=8/3遍
1 2 3 4 5 6
该数越大,效率越差 等于哈夫曼树的WPLTHANKSCON T EN T S
目录
考点一 外部排序的概念
考点二 置换-选择排序算法
考点三 多路平衡归并和败者树
考点四 最佳归并树考点二:置换-选择排序算法
设有一个文件F ,内含4500个记录,即R ,R ,…,R ,现在要对该文件
in 1 2 4500
进行排序,但内存空间最多只能对w=750个记录进行排序,并假设磁盘
每次读写单位为250个记录的数据块,其排序过程如下。考点二:置换-选择排序算法
(1)生成初始归并段:每次读3个数据块(750个记录)进行内排序(由于这些
数据全部在内存中,可以采用第八讲介绍的内排序方法),整个文件得到6
个归并段F ~F 。(即初始归并段),把这6个归并段存放到磁盘上。
1 6
某种内排序方法
产生6个长度为750
文件Fin.dat
个记录的有序文件
容量为750个记录
(含4500个记录) F ~F 。
1 6考点二:置换-选择排序算法
归并方案1:二路归并1
F F F F F F
1 2 3 4 5 6
F F F
7 8 9
F
10
F
out考点二:置换-选择排序算法
F F F F F F
1 2 3 4 5 6
F F F
7 8 9
F 和F 中
1 2
每个记录
读3次、 F
10
写3次
F
out
总的读记录数(写记录数与之相同):
[(F +F +F +F 的记录数)×3+(F +F 的记录数)×2]=12000=8/3遍
1 2 3 4 5 6
该数越大,效率越差 等于哈夫曼树的WPL考点二:置换-选择排序算法
归并方案2:二路归并2
F F F F F F
1 2 3 4 5 6
F
7
F
8
F
9
F
10
F
out
方案2:总的读记录数WPL=15000考点二:置换-选择排序算法
归并方案3:三路归并
F F
7 8
F
out
总的读记录数(写记录数与之相同):
方案3 :WPL=(750+750+750)×2+(750+750+750)×2=9000
不同的归并方案所需要的读写记录数是不同的!考点二:置换-选择排序算法
生成前面的初始归并段的方法
某内排序算法
abc .dat
1
abc.dat 内存 abc .dat
2 均有序
…
abc .dat
m
另一种方法:采用一种称为置换-选择排序方法用于生成初始归并段。
可以减少生成的初始归并段个数考点二:置换-选择排序算法
置换-选择排序就是一种减小n的、在外部排序中创建初始归并段时用到
的算法。它可以让初始归并段的长度增减,从而减小初始归并段的段数考点二:置换-选择排序算法
初始待排序文件为FI,初始归并段文件为输出文件FO,内存工作区为WA,
FO与WA的初始状态为空,并假设内存工作去WA的容量可容纳w个记录,则置
换-选择排序的操作的过程为:
(1)、从FI输入w个记录到工作区WA。
(2)、从WA中选出其中关键字最小的记录,记为MINIMAX记录。
(3)、将MINIMAX记录输出到FO中去。
(4)、若FI不为空,则从FI输入下一个记录到WA中。
(5)、从WA中所有关键字比MINIMAX记录关键字大的记录中选出最小关键
字记录,作为新的MINIMAX记录
(6)、重复(3)~(5),直至WA中选不出新的MINIMAX记录为止,由此
得到一个初始归并段,输出一个归并段的结束标记到FO中去。
(7)、重复(2)~(6),直至WA为空。由此得到全部归并段。考点二:置换-选择排序算法
设磁盘文件中共有18个记录,记录的关键字分别为(15,4,97,64,17,32,
108,44,76,9,39,82,56,31,80,73.255,68),若内存工作区可容纳5个记录,用置换-选
择排序算法可产生几个初始归并段,每个初始归并段包含哪些记录?考点二:置换-选择排序算法
设磁盘文件中共有18个记录,记录的关键字分别为(15,4,97,64,17,32,
108,44,76,9,39,82,56,31,80,73.255,68),若内存工作区可容纳5个记录,用置换-选
择排序算法可产生几个初始归并段,每个初始归并段包含哪些记录?考点二:置换-选择排序算法
设磁盘文件中共有18个记录,记录的关键字分别为(15,4,97,64,17,32,
108,44,76,9,39,82,56,31,80,73.255,68),若内存工作区可容纳5个记录,用置换-选
择排序算法可产生几个初始归并段,每个初始归并段包含哪些记录?考点二:置换-选择排序算法
• 在置换-选择排序算法中,内存工作区WA内频繁的操作是,从w个记录
中选择一个关键字最小的记录。如果采用基于简单选择排序方法,每次
操作需要u-1次比较,若输人文件有n个记录,则算法的时间复杂度为
(n*w)。
• 这种频繁的操作可以采用败者树来实现,从w个记录中选择一个关键字
最小的记录的时间为O(1og w),从而使置换-选择排序算法的时间复杂
2
度降低为O(n log w)。
2THANKSCON T EN T S
目录
考点一 外部排序的概念
考点二 置换-选择排序算法
考点三 多路平衡归并和败者树
考点四 最佳归并树考点三:多路平衡归并和败者树
1、k路平衡归并概述
 什么是k路平衡归并
2路平衡归并:每一趟从m个归并段得到m/2个归并段。
例如:
m=8,k=2
log m=3
2
遍考点三:多路平衡归并和败者树
2路平衡归并:每一趟从m个归并段得到m/2个归并段。
m=6,k=2,增加两个长度为0的虚段
log m=3
2
遍
 可以推广到k路平衡归并考点三:多路平衡归并和败者树
影响k路平衡归并的效率的因素:
归并时需要读写磁盘的次数
归并时需要关键字比较的次数。考点三:多路平衡归并和败者树
例如 m=8,假设每个归并段4个记录:k=2
读记录次数 = WPL= 8×4×3 = 96
(如果每个记录占用一个物理块,读写磁盘次数=96×2=192次)
采用k路平衡归并时,通常k越大,读写磁盘次数会减少。考点三:多路平衡归并和败者树
采用k路平衡归并时,则相应的归并树有log m+1层,要对数据进
k
行log m趟扫描。
k
m=8
k=2
log m趟
k考点三:多路平衡归并和败者树
每一趟需(u-1)×(k-1)
u个记录 次关键字比较
log m趟
k
总共需要的关键字比较次数为:
log m×(u-1)×(k-1)
k
= log m/ log k×(u-1)×(k-1)
2 2
= log m×(u-1)×(k-1)/log k
2 2考点三:多路平衡归并和败者树
总共需要的关键字比较次数:
(k-1)/log k在k增大时会增大
2
log m × (u-1) × (k-1)/log k
2 2
在初始归并段个数m与记录个数u确定时是常量
结论:增大归并路数k,读写磁盘次数减少,而关键字比较次数会增
大。若k增大到一定的程度,就会抵消掉由于减少读写磁盘次数而赢得的
时间。考点三:多路平衡归并和败者树
2、利用败者树实现k路平衡归并过程
败者树用于在k个记录中选取最小关键字的记录。败者树类似于堆排序
中的堆。
利用败者树实现k路平衡归并的过程是:
先建立败者树。
然后对k个输入有序段进行k路平衡归并。考点三:多路平衡归并和败者树
2、利用败者树实现k路平衡归并过程
败者树的构建
(1)初始化:假设有n个节点,每个节点都有一个唯一的编号和一个初始值。
这些节点被组织成一棵完全二叉树,根节点的值为其子节点的最小值。
(2)比较过程:从叶子节点开始,每个叶子节点代表一个归并段,其值是该归
并段中的最小值。将这些叶子节点的值进行比较,找出最小值,并将其父节点
设置为该最小值对应的节点。这个过程会一直向上进行,直到达到根节点。
(3)重构:当某个归并段的新元素进入时,需要重新调整败者树。将新元素与
当前节点的父节点进行比较,根据比较结果更新败者树的结构。考点三:多路平衡归并和败者树
2、利用败者树实现k路平衡归并过程
基于败者树的K路平衡归并过程
(1)取每个输入有序段的第一个记录作为败者树的叶子结点,建立初始败者树:两
两叶子结点进行比较,在双亲结点中存放比较的败者(关键字较大者),而让胜者去
参加更高一层的比赛, 如此在根结点之上胜出的“冠军”是关键字最小者。
(2)将胜出的记录写至输出归并段,在对应的叶子结点处补充其输入有序段的下一
个记录,若该有序段变空,则补充一个大关键字(比所有记录关键字都大,设为 k.)的
虚记录。
(3)调整败者树,选择新的关键字最小的记录:从补充记录的叶子结点向上和双亲
点的关键字比较,败者留在该双亲结点,胜者继续向上,直到树的根结点,最后将胜
者放在根结点的双亲结点中。
(4)若胜出的记录关键字等于k ,则归并结束;否则转(2)继续。
out考点三:多路平衡归并和败者树
2、利用败者树实现k路平衡归并过程
设有5个初始归并段,它们中各记录的关键字分别是:
F :{17,21,∞}
0
F :{5,44,∞}
1
F :{10,12,∞}
2
F :{29,32,∞}
3
F :{15,56,∞}
4
其中,∞是段结束标志。说明利用败者树进行k=5路平衡归并排序的过程。考点三:多路平衡归并和败者树
 构建败者树
k=5:创建含有k个叶子结点的完全二叉树(结点个数最少)。
n=n-1=k-1,n=n+n+n=2k-1+n,让n=0,总共2k-1=9
2 0 0 1 2 1 1
个结点,另外添加一个冠军结点。
冠军(最小者)
17 5 10
F F F
0 1 2
F 29 F 15
3 4考点三:多路平衡归并和败者树
冠军(最小者)
5(-∞)
5(-∞) 5(-∞)
5(-∞)
17 5 10
F F F
0 1 2
F 29 F 15
3 4
每个叶子结点对应一个归并段,段号为0~4。
初始时每个分支结点取值“5(-∞)”,5表示段号(此时为虚拟段
号),- ∞表示最小关键字。例如,某结点取值为“4(15)”,表示
结点值来自4号段的关键字15对应的记录。考点三:多路平衡归并和败者树
调整产生冠军(最小者)的过程
从F F 操作:将当前结点的关键字与父结点比较,将大的(败者)放
4 0
在父结点中,小者(胜者)继续进行,直到根结点。最后将胜者放在冠
军结点中。
冠军(最小者)
51((-5∞) )
514(((-51∞)5))
045(((11-∞75))) 25((1-∞0))
543(((-12∞59)))
17 5 10
F F F
0 1 2
F 29 F 15
3 4
败者树构建完毕考点三:多路平衡归并和败者树
 用败者树进行归并
过程:取出的冠军为1(5),从1号段中取下一个记录,沿着个分支向上操作,产生次小的记录。…
冠军(最小者) 152(((5-1)∞0))
归并文件: 5 10
514(((-51∞)5))
045(((11-7∞5))) 125(4((1-4∞0)))
354(((2-1∞95))) F 17 F 5 F 10
0 1 2
21 44 12
∞ ∞ ∞
F 29 F 15
3 4
依此进行,直到冠军为∞才结束。
32 15
∞ ∞ 每次产生一个冠军,比较次数约为log k。
2考点三:多路平衡归并和败者树
2、利用败者树实现k路平衡归并过程
利用败者树实现k路平衡归并时,总共需要的关键字比较次数为:
log m×(u-1)×log k
k 2
= log m×(u-1)×log k/log k
2 2 2
= log m×(u-1)
2
结论:关键字比较次数与k无关  总的内部归并时间不会随k的增大而
增大。
利用败者树实现k路平衡归并
只要内存空间允许,尽可能增大归并路数k。考点三:多路平衡归并和败者树
采用败者树,置换-选择排序中关键字比较次数分析
共有n个记录,内存工作区WA的容量为w:
若在w个记录中选取最小关键字的采用败者树方法,每次需要
log w次比较。
2
总的时间复杂度为O(nlog w)。
2THANKSCON T EN T S
目录
考点一 外部排序的概念
考点二 置换-选择排序算法
考点三 多路平衡归并和败者树
考点四 最佳归并树考点四:最佳归并树
最佳归并树
k路平衡归并适合初始归并段中的记录个数相同的情况,当初始归并
段中的记录个数不同时,怎么办 ?
当初始归并段和k已确定的情况时
归并方案转化为
哪些初始归并段先归并,哪些后归并的问题。考点四:最佳归并树
例如:k=2,4个初始归并段含记录个数分别是4、6、3、8。
4 6 3 8
 
归并方式1
10 11
WPL=(4+6+3+8)*2=42

21考点四:最佳归并树
例如:k=2,4个初始归并段含记录个数分别是4、6、3、8。
3 4 6 8
归并方式2
7
WPL=(3+4)*3+6*2+8=
41
13
21
显然采用k叉哈夫曼树的归并方案。考点四:最佳归并树
采用k叉哈夫曼树的归并方案  最佳归并树。
WPL最小
在内存中归并时,利用败者树减少关键字比较次数
 存在的问题(假设k=3):
剩下只有2个归并
段了,怎么办?考点四:最佳归并树
最佳归并树补段
采用k叉哈夫曼树的归并方案  最佳归并树。
WPL最小
在内存中归并时,利用败者树减少关键字比较次数
 存在的问题(假设k=3):
剩下只有2个归并
段了,怎么办?考点四:最佳归并树
解决的方法是加虚段(长度为0的段),每次恰好k个段进行归并!
加多少个虚段呢?
因为归并树补虚段的原则为:设参加归并的是只有度为0和度为k的结
点的正则次树,设度为0的结点有m个(因为初始归并段有m个,对应归并
树的叶子结点就有m),度为k的结点有m个,则有m=(k-1)*m +1。
k考点四:最佳归并树
解决的方法是加虚段(长度为0的段),每次恰好k个段进行归并!
加多少个虚段呢?
可以得出m*=(m-1)/(k-1),如果该除式能整除,即(m-1)/(k-1)=0,
则说明这m个叶子结点正好可以构造k次归并树,不需加虚段,此时分支
结点有m个。如果(m-1)%(k-1)=u≠0,则需要补入k-u-1个虚段,这样就
可以建立归并树。考点四:最佳归并树
解决的方法是加虚段(长度为0的段),每次恰好k个段进行归并!
加多少个虚段呢?
应加(k-1)-(m-1) Mod (k-1)个虚段
前面问题的解决方法:加上1个虚段:考点四:最佳归并树
最佳归并树构建过程
最佳归并树(m个初始归并段)是带权路径长度最短的k叉(阶)哈夫
曼树,构造步骤如下:
 若x=(m-1) Mod (k-1)≠0,则需附加(k-1)-x个虚段,以使
每次归并都可以对应k个段。
 按照哈夫曼树的构造原则(权值越小的结点离根结点越远)
构造最佳归并树。
k=2时,x=(m-1) Mod 1=0,所以二路归并(哈夫曼树构造中)不需要
增加虚段考点四:最佳归并树
设文件经预处理后,得到长度为
(49,9,35,18,4,12,23,7,21,14,26)
的11个初始归并段,试为4路归并设计一个读写文件次数最少的归并方
案(假如每个记录占用一个物理块)。
各个初始归并段中的记录个数,而非关键字序列考点四:最佳归并树
初始归并段个数m=11,k=4。x=(m-1) Mod (k-1)=1≠0,因此需
附加:
(k-1)-x=2
个长度为0的虚段。根据集合:
(49,9,35,18,4,12,23, 7,21,14,26,0,0)
构造4阶哈夫曼树。考点四:最佳归并树
按记录个数递增排序:
(0,0,4,7,9,12,14,18,21,23,26,35,49)
4路最佳归并树的构造过程:
0 0 4 7
9 11 12 14 18 21 23 26
35 46 49 88
218
WPL=(4+7)×3+(9+12+14+18+21+23+26)×2+(35+49)×1=363
最少的读写次数=2×WPL=726次。考点四:最佳归并树
平衡归并树 ≡ 最佳归并树
满足k路平衡归并的前提
例如:
初始归并段个数m=8,每个段的记录数=10,k=2
对应的平衡归并树:
10个记录 10个记录 10个记录 10个记录 10个记录 10个记录 10个记录 10个记录
20个记录 20个记录 20个记录 20个记录
40个记录 40个记录
80个记录
与2路最佳归并树相同。 WPL=8×10×3=240
满足k路平衡归并的前提  采用平衡归并树;
归并方案设计:
否则  采用最佳归并树THANKS