Битовые операции Java (в поразрядной сортировке)

Question

На днях я решил написать реализацию поразрядная сортировка на Яве.Предполагается, что сортировка по основанию должна быть O(k*N), но в итоге у меня получилось O(k^2*N) из-за процесса разбиения каждой цифры на одно число.Я разбил каждую цифру, убрав (%) предыдущие цифры и разделив их на десять, чтобы исключить последующие цифры.Я спросил своего профессора, есть ли более эффективный способ сделать это, и он посоветовал использовать битовые операторы.Теперь мои вопросы:Какой метод будет самым быстрым при разбиении каждого числа в Java: 1) Метод, указанный выше.2) Преобразуйте число в строку и используйте подстроки.3) Используйте битовые операции.

Если 3), то как это будет работать?

Answer 1

В качестве подсказки попробуйте использовать систему счисления, отличную от 10, поскольку компьютеры справляются с двоичной арифметикой лучше, чем с десятичной.

• x >>> n эквивалентно x/2^н
• х & (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;

это часть битовой манипуляции.

& — это оператор, выполняющий побитовое И, а >> — сдвиг вправо.