11.3 多路平衡归并的实现

举报
C语言入门到精通 发表于 2021/02/18 00:52:38 2021/02/18
【摘要】 01多路平衡归并的实现1、2-路归并:令u个记录分布在两个归并段上,按merge过程进行归并。每得到归并后的一个记录,仅需一次比较即可,则得到含u个记录的归并段需进行u-1次比较。2、k-路归并:令u个记录分布在k个归并段上,显然,归并后的第一个记录应是k个归并段中关键字最小的记录,即应从每个归并段的第一个记录的相互比较中选出最小者,需要进行k-1次比较。每得到归并后的有序段中...

01多路平衡归并的实现


1、2-路归并:令u个记录分布在两个归并段上,按merge过程进行归并。每得到归并后的一个记录,仅需一次比较即可,则得到含u个记录的归并段需进行u-1次比较。

2、k-路归并:令u个记录分布在k个归并段上,显然,归并后的第一个记录应是k个归并段中关键字最小的记录,即应从每个归并段的第一个记录的相互比较中选出最小者,需要进行k-1次比较。每得到归并后的有序段中的一个记录,都要进行k-1次比较。显然为得到含u个记录的归并段需进行(u-1)(k-1)次比较。

3、由以上得,对n个记录的文件进行外排时,在内部归并过程中进行的总的比较次数为s(k-1)(n-1)。

4、若在进行k-路归并时利用“败者树”(Tree of Loser),则可使在k个记录中选出关键字最小的记录时仅需进行log2^k次比较。

5、败者树:是树形选择排序的一种变型。

C语言 | 冒泡排序 mp.weixin.qq.com图标

文章来源: zhuanlan.zhihu.com,作者:小林C语言,版权归原作者所有,如需转载,请联系作者。

原文链接:zhuanlan.zhihu.com/p/338804527

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。