打开网易新闻 查看精彩图片

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、败者树：是树形选择排序的一种变型。