c++ - C++中的基数排序

Question

我尝试编写 C++ 代码来对整数进行基数排序。看了网上的教程，我发现我们必须把每个整数放到正确的桶里，从最不重要的数字开始。我的问题是，在基数排序的普通算法中，我是否需要从 0 到 9 的 10 个桶？如果我将这些存储桶分配为链表（例如 *list1 ~~~ *list9），会不会有点奇怪？

感谢您的时间。这不是功课，只是出于好奇。

Answer 1

我不认为这是一个 C++ 问题（尽管 Radix Sort 可以清楚地在 C++ 中实现）并且它可能与链表无关，至少不是您似乎认为的那样：排序发生在每个数字的基数，您可以有效地访问每个数字的存储桶。为此，列表不会很好地工作，但向量会。在每个存储桶内，您可以使用一个列表。

至于您需要的桶数，答案是：视情况而定！您可以使用任何大于 1 的整数基数，并且您需要相应数量的存储桶。由于计算机特别擅长 2 的计算能力，使用 2 的幂可能比使用 10 等其他基数更有效，尽管 10 也可以。奇怪的是，维基百科关于基数排序的文章使用基数 10 - 可能是为了避免对基数的自由选择造成太多混淆。