Битовые операции Java (в поразрядной сортировке)
-
22-07-2019 - |
Вопрос
На днях я решил написать реализацию поразрядная сортировка на Яве.Предполагается, что сортировка по основанию должна быть O(k*N), но в итоге у меня получилось O(k^2*N) из-за процесса разбиения каждой цифры на одно число.Я разбил каждую цифру, убрав (%) предыдущие цифры и разделив их на десять, чтобы исключить последующие цифры.Я спросил своего профессора, есть ли более эффективный способ сделать это, и он посоветовал использовать битовые операторы.Теперь мои вопросы:Какой метод будет самым быстрым при разбиении каждого числа в Java: 1) Метод, указанный выше.2) Преобразуйте число в строку и используйте подстроки.3) Используйте битовые операции.
Если 3), то как это будет работать?
Решение
В качестве подсказки попробуйте использовать систему счисления, отличную от 10, поскольку компьютеры справляются с двоичной арифметикой лучше, чем с десятичной.
- x >>> n эквивалентно x/2н
- х & (2н - 1) эквивалентно x % 2н
Кстати, Java >> выполняет расширение знака, что в данном случае, вероятно, не то, что вам нужно.Вместо этого используйте >>>.
Другие советы
[http://en.literateprograms.org/Radix_sort_(Java)
](http://en.literateprograms.org/Radix_sort_(Java))
Строка кода, которая это делает;
int key = (a[p] & mask) >> rshift;
это часть битовой манипуляции.
& — это оператор, выполняющий побитовое И, а >> — сдвиг вправо.