顯示n個正整數可以按Nlogk時間排序

顯示在1到k範圍內的n個正整數可以按O（n log k）時間排序。顯示n個正整數可以按Nlogk時間排序

我只能使用Mergesort，因爲我知道如何使用堆。這不是硬件問題，它來自Skiena的書。我看到，如果我有K = 3，那麼在3個步驟中，我可以合併列表;但是這樣做足以回答或「顯示」嗎？

2013-03-03 NoNameY0

請參閱：基數排序。 – 2013-03-03 17:03:25

我想我只能使用合併排序，因爲問題在合併排序部分 – NoNameY0 2013-03-03 17:03:55

實踐中沒有理由爲什麼必須將自己限制到特定的排序函數。 StackOverflow適用於實際的編程問題，而不是理論上的問題。 – 2013-03-03 17:05:52

Here是一對有效排序的想法。正如用戶templatetypedef所說，radix sort可能是你正在尋找的。

希望它有幫助

2013-03-03 18:25:57

它是完全可以排序在O（N日誌K）時間 - 只需使用基數排序。 – templatetypedef 2013-03-03 18:28:59

@templatetypedef我會看看它並編輯我的答案。謝謝 – 2013-03-03 18:30:09

回答