Edd*_*man 6 c# java algorithm data-structures
我来
1)计算k-Way合并排序所需的比较次数,以对从0到N-1的数字的随机排列进行排序.
2)
计算K-Way合并排序所需的数据移动次数o对从0到N-1的数字的随机排列进行排序.
我理解双向合并排序如何正常工作,并很好地理解代码.我现在的问题是我不知道如何开始并需要一些帮助.如何将双向合并排序转换为K-Way,以便我可以解决上述问题.
我已经google了一段时间,但找不到任何教程,以帮助我理解"k-Way合并排序"非常好.
我需要很好的解释该做什么,以便我可以从那里接受并自己做.
就像我说我理解双向,所以我如何移动到K-Way合并排序？我如何实现K-way.
谢谢你的帮助.
编辑
**我读了一些帖子 http://bchalk.com/work/view/k_way_merge_sort ,必须使用BinaryHeap来实现k-Way合并.是这样还是有其他方法？
**我如何将我的名单分成K？有一种特殊的方式吗？
当k > 2来自每个输入流的前导元素通常保持在minheap结构中时.这使得很容易找到n值的最小值,从堆中弹出该值,并从相应的输入流中插入替换值.
堆O(lg2 k)对每个插入进行比较,因此n个项的k向合并的总工作量是n * lg2(k).
虽然你问过C#和Java,但是你可以通过查看用于k-way合并的Python标准库代码来学习如何实现它:http: //hg.python.org/cpython/file/2.7/Lib/heapq. PY#L323
要回答您的其他问题,没有特殊方法可以将您的列表划分为K组.只需取第一个数组中的第一个N/k元素,然后将下一个N/k元素放入下一个,等等.对每个数组进行排序,然后使用堆如上所述合并它们.
| 归档时间： |
|
| 查看次数： |
4028 次 |
| 最近记录： |