Реализуйте сортировку, аналогичную radix

Question

привет, мне нужно написать suj вид сортировки, может быть, это похоже на основную сортировку а также (это не домашняя работа, потому что я сам создал ее, и, пожалуйста, если кто-то может мне помочь) проблема такая предположим, у меня есть массив int x [] = new int [] {4,5,3,2,1}; давай напишем это в двоичном виде 5 -0101 4- 0100 3-0011 2-0010 1-0001 я хочу отсортировать эти элементы с помощью побитовых операций или проверить каждый бит, и если меньше обмена, это может кто-нибудь помочь мне например, возьмите 5 и 4, проверьте первый самый правый бит 0 == 0, поэтому продолжайте в индексе 1 также 1 == 1, затем те же самые 0 = 0 и последний 1> 0, это означает, что первый элемент больше второго, поэтому поменяйте его

Paraphasing:

Мне нужно создать вид, похожий на radix.

Предположим, у меня есть массив: int x[] = new int[] {4, 5, 3, 2, 1};

Или в двоичном виде: 5-0101 4-0100 3-0011 2-0010 1-0001

Я хочу отсортировать эти элементы с помощью побитовых операторов или проверить каждый бит и (если меньше) заменить его. Например, рассмотрим 5 и 4:

Самый старший или старший значащий бит (MSB) 5 в двоичном виде равен 0, как и MSB, равный 4. С 0 == 0 процесс продолжается. Следующие два бита (0, затем 1) также эквивалентны. Наконец, самый правый или младший значащий бит (LSB), равный 5, равен 1, тогда как младший бит, равный 4, равен 0, что указывает на необходимость обмена двумя значениями.

Answer 1

Чтобы получить k -й бит int x, вы можете сделать следующее:

int bit = (x >> k) & 1;

Вот тестовый жгут:

    int xs[] = {4,5,3,2,1};
    for (int k = 0; k < 4; k++) {
        for (int x : xs) {
            int bit = (x >> k) & 1;
            System.out.format("|%s|  ", bit);
        }
        System.out.println();
    }

Эта печать (с аннотацией)

x= 4    5    3    2    1  k=
  |0|  |1|  |1|  |0|  |1|  0
  |0|  |0|  |1|  |1|  |0|  1
  |1|  |1|  |0|  |0|  |0|  2
  |0|  |0|  |0|  |0|  |0|  3

Хитрый бит здесь - это бит знака, то есть бит 31 на int. Когда это 1, это означает отрицательное число. Вы можете сначала иметь реализацию, которая работает только для положительных значений int, а затем добавить поддержку отрицательного числа.

Смотри также

• Википедия / Дополнение к двум