你如何处理每个整数Radix Sort的位置？-Java 学习之路

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

我会解释一下：

可以说我有 arrayToSort = [50, 4, 2, 10, 22, 284]

从我的理解，我将从0到9排序到十位 . 所以，我有：

铲斗0：50,10
铲斗1：空的
铲斗2：2,22
斗3：空了
铲斗4：4,284（和5 - 9是空的）

然后，我通过将每个桶中的元素（从桶0开始）放入新数组来重建数组 .

Problem:
这就是我陷入困境的地方：对于百分之一的地方，我为了获得填充而进行比较（即"0002"）？根据我的理解，Java（我的语言实现了带有前导零的整数 . 但是在字符串和整数之间切换似乎效率低下 .

Question:
你应该如何处理一些整数的问题，这些整数与数组中的其他整数没有相同的位数？

我已经看过伪代码和算法的实现，我仍然对如何处理在整数中获取每个位置的值感到困惑 . 我无法理解你如何在没有前导零（以及将整数转换为字符串）的情况下实现算法，而我看到的例子并没有这样做 . 以下是我尝试的几个网站：

Side note:
这不仅仅是为了更熟悉不同的算法以及如何实现它们 .

3 回答

2
别担心 . 数学提供了你正在思考的“填充” .

第一次，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 .

在下一次迭代中，你当然会得到全零 .
回复于 2024-04-18T13:21:35+08:00
0
如果使用2的幂的桶号，则可以使用位操作来执行此操作 .

Example

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） .

这虽然不适用于负数...您还需要使用该公式以不同方式处理负数 .
回复于 2024-04-18T13:21:35+08:00
0
你已经清楚地理解了算法的要点 . 您只对一个小的实现细节感兴趣 .

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

n = 100 * a0 101 * a1 102 * a2 ... 10i * ai ... =Σ10i* ai

其中0≤ai≤9是一个数字 .

例子：

4 = 100 *4 101 * 0 102 * 0 ......

104 = 100 *4 101 *0 102 *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 数组 .
回复于 2024-04-18T13:21:35+08:00

你如何处理每个整数Radix Sort的位置？

3 回答

相关问题