Java位操作（基數排序）

Question

有一天，我決定用Java編寫radix sort的實現。基數排序應該是O（k * N），但是由於將每個數字分解爲一個數字的過程，我的結果是O（k^2 * N）。我通過修改（％）前面的數字併除以10來消除後面的數字來分解每個數字。我問我的教授是否有更有效的方法來做這件事，他說要使用位操作符。現在對於我的問題：在Java中分解每個數字的方法是最快的，1）上述方法。 2）將數字轉換爲字符串並使用子字符串。 3）使用位操作。

如果3）那麼如何工作？

Answer 1

作爲提示，嘗試使用除10以外的基數，因爲計算機處理二進制算術b etter比十進制。

• X >>> n是等價於x/2 ^Ñ
• X &（2 ^Ñ - 1）等價於x％2 ^Ñ

通過方式，Java的>>執行符號擴展，這可能不是你想要在這種情況下。改用>>>。

Answer 2

[http://en.literateprograms.org/Radix_sort_(Java)]（http://en.literateprograms.org/Radix_sort_(Java))

的代碼執行此線;

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

是位操作部

&是操作員做逐位AND和>>。是一個右移