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 回答
别担心 . 数学提供了你正在思考的“填充” .
第一次,1的位置给了桶 . 在您给出的Budd代码中,这就是计算
这将产生从0到9的值,这取决于最低有效数字 . 即,对于10,101,942,13,4l,你得到0,1,2,3,4 .
在第二次迭代中,这变成了
桶指数将是10位数:1,0,4,1,0 .
只是为了好玩第三次迭代,
所以你有:0,1,9,0,0 .
在下一次迭代中,你当然会得到全零 .
如果使用2的幂的桶号,则可以使用位操作来执行此操作 .
Example
16 = 2 ^ 4桶:
这允许您使用计算数字
您只需要在使用最高位时注意,因为交换此位也会交换表示数字的符号 . 这意味着您还需要按标记进行排序 .
这只是对2的幂的优化 . 通常,您可以使用找到数字
其中
d
=1=b^0
,b = b^1
,b*b = b^2
,...,b^n
(^
=指数不是此处的XOR) .这虽然不适用于负数...您还需要使用该公式以不同方式处理负数 .
你已经清楚地理解了算法的要点 . 您只对一个小的实现细节感兴趣 .
在十进制系统中,我们有以下数字表示:
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 ...
事实上,你总是在任何地方都有一个数字 . 那些前导零只是不用十进制数表示 .
因此,请考虑使用此函数来查找数字:
之前预先计算
powersOf10
数组 .