java - Java 位运算（在基数排序中）

Question

前几天我决定用 Java编写一个基数排序的实现。基数排序应该是 O(k*N) 但我的最终是 O(k^2*N) 因为将每个数字分解为一个数字的过程。我通过修改（％）前面的数字并除以十来消除后面的数字来分解每个数字。我问我的教授是否有更有效的方法来做到这一点，他说使用位运算符。现在我的问题是：哪种方法在分解 Java 中的每个数字时最快，1) 上述方法。2）将数字转换为字符串并使用子字符串。3) 使用位操作。

如果 3) 那么这将如何工作？

Answer 1

作为提示，请尝试使用 10 以外的基数，因为计算机处理二进制算术比十进制更好。

• x >>> n 等价于 x / 2 ⁿ
• x & (2 ⁿ - 1) 等价于 x % 2 ⁿ

顺便说一句，Java 的 >> 执行符号扩展，在这种情况下这可能不是您想要的。使用 >>> 代替。

Answer 2

Radix_sort_(Java)

执行此操作的代码行；

int key = (a[p] & mask) >> rshift;

是位操作部分。

&是执行按位与的运算符并且>>是右移。