理解和求解K-路合併排序

點到理解和求解K-路合併排序

1）計數用k路合併排序排序號碼從0到N-1隨機置換所需的比較的數量。

2）

以計數由K-路所需的數據的移動的數目歸併排序號碼鄰排序隨機置換從0到N-1。

我明白雙向合併排序如何正常工作，並且很好地理解代碼。我現在的問題是我不知道如何開始，需要一點幫助。我如何將2路合併排序轉換爲K-Way，以便我可以解決上述問題。

我已經搜索了一段時間，但無法找到任何教程來幫助我理解「k-way合併排序」。

我需要很好的解釋該怎麼做，以便我可以從那裏把它做到我自己。

就像我說的我理解2路，那麼我如何移動到K-way合併排序？我如何實施K-way。

感謝您的幫助。

編輯

**我看了一些帖子 http://bchalk.com/work/view/k_way_merge_sort 是二叉堆必須被用來實現K-路合併。這是或那麼其他方式？

** 如何將我的列表分爲K？有沒有特殊的做法？

來源

2011-10-31 Eddy Freeman

二叉堆對於k路合併不是必需的。所有你需要的是快速找到k項目列表中最小的一種方法，刪除該項目，並將另一項目放入列表中。二進制堆經常被使用，因爲它很容易實現並且對於小列表來說非常有效。但是您可以使用跳過列表或任何其他堆實現或其他優先級隊列實現。 –

當k > 2時，來自每個輸入流的主要元素通常保持在minheap結構中。這可以很容易地找到n值的最小值，將該值從堆中彈出，並從相應的輸入流中插入替換值。

對於每個插入，一個堆做了O(lg2 k)比較，因此n項的k路合併的總工作量爲n * lg2(k)。

雖然你們問C＃和Java，你可以學習如何做到這一點，通過查看一個k路合併Python標準庫代碼：http://hg.python.org/cpython/file/2.7/Lib/heapq.py#l323

爲了回答您的其他問題，有沒有特殊的方式把你的名單分成K組。只需取第一個數組中的第一個N/k元素，接下來的N/k個元素，等等。對每個數組進行排序，然後使用上面提到的堆合併它們。

來源

2011-10-31 01:40:39

感謝您的答覆。我感謝它 –

沒問題。祝你好運與你合併:-) –

您總是可以將k路合併想象爲一系列雙向合併，也就是說，與第一個和第二個以及第三個：Merge(Merge(L1, L2), L3)等的結果進行雙向合併。更快將分裂兩次：Merge(Merge(L1, L2), Merge(L3, L4))。正如你所看到的，對於k-way排序，你將需要某種循環（遞歸）。

來源

2011-10-31 00:50:50 Z1MM32M4N

感謝您的回答。我已經編輯了我的文章一點點。你可以幫我嗎？謝謝 –

理解和求解K-路合併排序

回答

相關問題