您如何处理每个整数基数排序的位置？

Question

背景：
我正在研究基数排序，我相信我对该算法的总体工作原理有一个很好的了解。但是，我无法理解您在浏览列表时实际上是如何 "interpret" 每个元素的。

我再解释一下：

假设我有 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 这样的元素呢？我假设我需要 "pad" 它们前导零。但是，如果我这样做，是否意味着我需要在进行比较时将每个元素视为一个字符串才能获得该填充（即“0002”）？根据我的理解，Java（我正在使用的语言）没有实现带有前导零的整数。但是在字符串和整数之间切换似乎效率低下。

问题：
你应该如何处理一些整数与数组中其他整数的位数不同的问题？

我看过算法的伪代码和实现，但我仍然对他们如何处理获取整数中每个位置的值感到困惑。我不明白如何在没有前导零的情况下实现算法（并将整数转换为字符串），而我看到的示例并没有这样做。以下是我试过的几个网站：

旁注：
如果有人想知道，这不是家庭作业。我只是想更加熟悉不同的算法以及如何实现它们。

Answer 1

如果您使用的桶号是 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 ).

虽然这不适用于负数...您还需要使用该公式以不同方式处理负数。

Answer 2

不用担心。数学提供了您正在考虑的 "padding"。

第一次通过，1 的位置给出了桶。在您提供的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,0,4,1,0。

第三次迭代只是为了好玩，

hashIndex = (data[i] / 100) % 10;

所以你有：0,1,9,0,0。

在下一次迭代中，您当然会得到全零。

Answer 3

您已经清楚地理解了算法的要点。您只对一个小的实现细节感兴趣。

在十进制系统中，我们有以下数字表示法：

n = 10⁰*a₀ + 10¹*a₁ + 10²*a₂ + ... + 10ⁱ*a_i + ... = ∑10ⁱ*a_i

其中 0 ≤ a_i ≤ 9是一个数字。

示例：

4 = 10⁰*4 + 10¹*0 + 10²*0 + ...

104 = 10⁰*4 + 10¹*0 + 10²*1 + ...

事实上，你总是在任何地方都有一个数字。那些前导零只是没有写成十进制数字表示形式。

所以考虑使用这个函数来找到一个数字：

int dig(int num, int place) {
    // divide by powerOf10 to put away lower place digits
    // take the reminder of division by 10 - the lowest digit
    return num / powersOf10[place] % 10;
}

预先计算 powersOf10 数组。

您如何处理每个整数基数排序的位置？

How do you handle the places for each integer Radix Sort?

java

sorting

algorithm

radix-sort