how to Implement MSD string sorting using queues ?

lgqfhwy
  • 62

见到一个题,无论如何也想不出来,网上搜竟然也没有。

Queue sort. Implement MSD string sorting using queues, as follows:
Keep one queue for each bin. On a first pass through the items to be
sorted, insert each item into the appropriate queue, according to its
leading character value. Then, sort the sublists and stitch together
all the queues to make a sorted whole. Note that this method does not
involve keeping the count[] arrays within the recursive method.

题目中说用了队列就不用count数组了,而且应该先把队列内的元素排序再拼接起来。我唯一能够想到的就是在每一个递归创建队列数组,递归排序。这样以来太浪费空间,要比使用count数组多了好几倍,我感觉这应该不是作者的本意。还有就是作者说

Then, sort the sublists and stitch together all the queues to make a
sorted whole.

如果不用递归,直接在队列内排序,那样时间复杂度直接上了O(nlgn), 就不是MSD的O(n)了,也应该是不合适的。
这个问题google, stackoverflow 上都没有。如果各位大神有好的想法请分享一下。
原题在 algorithm P727
图片描述

图片描述

回复
阅读 2.4k
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏