11.3 多路平衡归并的实现
【摘要】 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语言 | 冒泡排序
文章来源: zhuanlan.zhihu.com,作者:小林C语言,版权归原作者所有,如需转载,请联系作者。
原文链接:zhuanlan.zhihu.com/p/338804527
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)