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