1回答

liuyubobobo

2018-07-03

已采纳

抱歉，这个课程没有提供三路归并排序的代码：）

实际上，3路归并，乃至多路归并（k路归并），思想都和普通的二分归并排序是一样的，区别只在于归并的过程。课程中的普通二路归并，在归并的过程中，每次从两个子数组中选择最小的元素进行归并；在三路归并中，每次从三个子数组中选择最小的元素进行归并就好了：）进而，k路归并排序，每次就是从k个子数组中选择最小的元素进行归并过程：）如果有兴趣，强烈建议自己写一个三路归并的算法，是一个很好的编程训练：）

对于k路归并的过程中，比较k个元素的大小，可以使用最基础的线性扫描比较；也可以借助优先队列，还可以使用分治的思想解决。如果感兴趣，对于每种方法，都建议可以思考一下，甚至实践一下：）

对于归并k个子数组的元素，Leetcode上也有一道很好的练习题：

英文版：https://leetcode.com/problems/merge-k-sorted-lists/description/

中文版：https://leetcode-cn.com/problems/merge-k-sorted-lists/description/

不过这个问题处理的对象是链表，可以顺便学习（复习）一下和链表相关的操作：）强烈推荐一下。

在我的github上有这个问题的参考代码，如果需要可以参考。有四种解法。传送门：https://github.com/liuyubobobo/Play-Leetcode/tree/master/0023-Merge-k-Sorted-Lists/cpp-0023

加油！：）

2

1

慕码人1088981

非常感谢！

2018-07-03

共1条回复