如何处理每个整数基数排序的位置？
背景：
我在看基数排序，我相信我对算法的一般工作原理有很好的了解。然而，当您浏览列表时，我很难理解您实际上是如何“解释”每个元素的。
我再解释一下：
让我说我有arrayToSort = [50, 4, 2, 10, 22, 284]
根据我的理解，我会从0到9按十位进行排序。所以，我会：
桶0: 50，10
桶1:空
桶2: 2，22
桶3:空
桶4: 4,284 (和5-9是空的)
然后，通过将每个桶中的元素(从桶0开始)放到新数组中来重构数组。
问题：
这就是我陷入困境的地方:对于百分之一的地方，我会在第一次迭代中做同样的事情。但是，对于像2和4这样的元素，我应该做什么呢？我假设我需要用前导零来“填充”它们。但是，如果我这样做，这是否意味着在进行比较时，我需要将每个元素视为字符串，以获得填充(即"0002")？据我所知，Java (我使用的语言)没有实现带前导零的整数。但字符串和ints之间的切换似乎效率低下。
问题：
如何处理某些整数与数组中其他整数的位置不相同的问题？
我看过伪代码和算法的实现，我仍然对它们如何处理获取整数中每个位置的值感到困惑。我不明白如何在不带前导零(并将整数转换为字符串)的情况下实现该算法，而我看到的示例没有这样做。以下是我尝试过的几个网站：
- 俄勒冈州根类
- 极客观点基数排序
旁注：
这不是家庭作业以防有人想知道。我只是想更加熟悉不同的算法，以及如何实现它们。
回答 2
Stack Overflow用户
发布于 2016-03-06 20:55:27
别担心。数学提供了你正在考虑的“填充”。
第一次通过时，一个人的位置给了水桶。在你给出的Budd代码中，这就是计算
hashIndex = (data[i] / 1) % 10;这将产生0到9之间的值，这些值依赖于最不重要的数字。也就是说，10,101,942，13，4l，你可以得到0,1,2,3,4。
在第二次迭代中，这变成
hashIndex = (data[i] / 10) % 10;桶指数将是10位数:1，04，1，0。
只是为了好玩第三次迭代，
hashIndex = (data[i] / 100) % 10;所以你有:0，1，9，0。
在下一次迭代中，您当然会得到所有的零。
Stack Overflow用户
发布于 2016-03-06 19:47:42
如果使用的桶号是2的幂，则可以使用位操作。
示例
16 = 2^4桶：
这使您可以使用
int input = ...
int digitNumber = ... // digit number from last digit to first one
int bucket = (index >> (4*digitNumber)) & ((1 << 4) - 1); // (index >> (4*digitNumber)) & 0xF在使用最重要的位时，您只需要小心，因为交换这个位交换了所表示的数字的符号。这意味着您还需要按符号进行排序。
这只是对2的幂的优化。通常，您可以使用
bucket = (input / d) % b;其中d = 1=b^0，b = b^1，b*b = b^2，.，b^n (^ =指数而不是XOR )。
但这不适用于负数.你也需要用这个公式来处理负数。
https://stackoverflow.com/questions/35831277
复制相似问题
腾讯云开发者
