Java Bit Operations (En Radix Sort)

Question

L'autre jour, j'ai décidé d'écrire une implémentation de radix sort en Java. Le tri de la base est supposé être O (k * N) mais le mien a fini par être O (k^2 * N) à cause du processus consistant à décomposer chaque chiffre en un nombre. J'ai décomposé chaque chiffre en modifiant (%) les chiffres précédents et en divisant par dix pour éliminer les chiffres suivants. J'ai demandé à mon professeur s'il y aurait une façon plus efficace de le faire et il a dit d'utiliser des opérateurs de bits. Maintenant pour mes questions: Quelle méthode serait la plus rapide à décomposer chaque nombre en Java, 1) Méthode indiquée ci-dessus. 2) Convertir nombre en chaîne et utiliser des sous-chaînes. 3) Utilisez les opérations sur les bits.

Si 3) alors comment cela fonctionnerait-il?

Answer 1

Comme indice, essayez d'utiliser une autre base que 10, car les ordinateurs gèrent l'arithmétique binaire b plus que décimal.

• x >>> n est équivalent à x/2 ⁿ
&
• x (2 n -1) est équivalent à x% 2 ⁿ

Par façon, Java >> effectue l'extension de signe, ce qui n'est probablement pas ce que vous voulez dans ce cas. Utilisez >>> à la place.

Answer 2

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

La ligne de code qui fait cela,

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

est la partie de manipulation de bits

& est l'opérateur de faire une opération de bits AND et >>. est un décalage vers la droite