how to Implement MSD string sorting using queues ?

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

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
图片描述

图片描述

阅读 1.9k
评论
    0 个回答
    撰写回答

    登录后参与交流、获取后续更新提醒