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