Java -Bit -Operationen (in Radix -Sortierung)

Question

Neulich habe ich beschlossen, eine Implementierung von zu schreiben Radix -Sortierung in Java. Die Radix -Sortierung soll o (k*n) sein, aber meine war o (k^2*n), weil der Prozess der Aufschlüsselung jeder Ziffer auf eine Zahl abgebaut wurde. Ich habe jede Ziffer durch Modding (%) die vorhergehenden Ziffern ausgebrochen und durch zehn geteilt, um die folgenden Ziffern zu beseitigen. Ich fragte meinen Professor, ob es eine effizientere Möglichkeit geben würde, und er sagte, er solle Bit -Betreiber verwenden. Nun zu meinen Fragen: Welche Methode wäre am schnellsten beim Aufbrechen jeder Zahl in Java, 1) Methode oben angegeben. 2) Konvertieren Sie die Nummer in SPRING und verwenden Sie Substrings. 3) Verwenden Sie Bitoperationen.

Wenn 3) wie würde das dann funktionieren?

Answer 1

Versuchen Sie als Hinweis, einen anderen Radix als 10 zu verwenden, da Computer die binäre Arithmetik besser als dezimal umgehen.

• x >>> n entspricht x / 2ⁿ
• x & (2ⁿ - 1) ist äquivalent zu x % 2ⁿ

Javas >> führt übrigens eine Zeichenerweiterung durch, was in diesem Fall wahrscheinlich nicht das ist, was Sie wollen. Verwenden Sie stattdessen >>>.

Answer 2

[http://en.literateprograms.org/Radix_sort_(Java)](http://en.liteerateprograms.org/radix_sort_(java)))

Die Codezeile, die dies tut;

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

ist der Teil der Bitmanipulation.

& ist der Bediener, der bitweise macht und und >> ist ein Rechtsverschiebung.