我尝试编写C++代码来对整数进行基数排序。在看了在线教程后,我发现我们必须将每个整数放到正确的桶中,从最低有效数字开始。我的问题是,在基数排序的普通算法中,我是否需要从0到9的10个存储桶?如果我将这些存储桶指定为链表(例如,*list1 ~ *list9),会不会有点奇怪?
谢谢您抽时间见我。这不是家庭作业,只是出于好奇心。
发布于 2012-03-04 05:52:26
我不认为这是一个基数问题(尽管基数排序显然可以在C++中实现),而且它可能与链表无关,至少不是你所认为的那样:排序是在每个数字的基础上进行的,你可以有效地访问每个数字的桶。在这种情况下,列表不能很好地工作,但是向量可以。在每个存储桶中,您可以使用一个列表。
至于您需要的存储桶数量,答案是:视情况而定!您可以使用任何大于1的整数基数,并且您需要相应数量的存储桶。由于计算机特别擅长计算2的幂,因此使用2的幂可能比使用其他基(如10 )更有效,尽管10也可以。奇怪的是,Wikipedia's article on Radix Sort使用了基数10 -可能是为了避免太多关于自由选择基数的混乱。
https://stackoverflow.com/questions/9549195
复制相似问题