Вопросы по реализации сортировки Radix в Java
Следующая сортировка Radix выполняет четыре прохода сортировки подсчета (256 сегментов, 32-разрядные целые числа, начиная с младших значащих цифр), взятых из учебника Алгоритмов Седжвика.
public class LSD {
private final static int BITS_PER_BYTE = 8;
// LSD sort an array of integers, treating each int as 4 bytes
// assumes integers are nonnegative
// [ 2-3x faster than Arrays.sort() ]
public static void sort(int[] a) {
int BITS = 32; // each int is 32 bits
int W = BITS / BITS_PER_BYTE; // each int is 4 bytes
int R = 1 << BITS_PER_BYTE; // each bytes is between 0 and 255
int MASK = R - 1; // 0xFF
int N = a.length;
int[] aux = new int[N];
for (int d = 0; d < W; d++) {
// compute frequency counts
int[] count = new int[R+1];
for (int i = 0; i < N; i++) {
int c = (a[i] >> BITS_PER_BYTE*d) & MASK;
count[c + 1]++;
}
// compute cumulates
for (int r = 0; r < R; r++)
count[r+1] += count[r];
// for most significant byte, 0x80-0xFF comes before 0x00-0x7F
if (d == W-1) {
int shift1 = count[R] - count[R/2];
int shift2 = count[R/2];
for (int r = 0; r < R/2; r++)
count[r] += shift1;
for (int r = R/2; r < R; r++)
count[r] -= shift2;
}
// move data
for (int i = 0; i < N; i++) {
int c = (a[i] >> BITS_PER_BYTE*d) & MASK;
aux[count[c]++] = a[i];
}
// copy back
for (int i = 0; i < N; i++)
a[i] = aux[i];
}
}
Я понимаю большую часть кода, за исключением этой части:
if (d == W-1) {
int shift1 = count[R] - count[R/2];
int shift2 = count[R/2];
for (int r = 0; r < R/2; r++)
count[r] += shift1;
for (int r = R/2; r < R; r++)
count[r] -= shift2;
}
Какова цель этого сегмента кода? Спасибо!
1 ответ
Блок кода делает именно то, что говорит комментарий:
для наиболее значимого байта 0x80-0xFF предшествует 0x00-0x7F
Причина этого такова: так как вы используете int
Таким образом, наиболее значимым битом является бит знака. Поэтому числа с самым старшим байтом в диапазоне 0x80-0xFF
являются отрицательными числами, поэтому должны быть помещены перед положительными числами, у которых самый старший байт в диапазоне 0x00-0x7F
,
Если вы спрашиваете, как блок кода достигает этого, вот краткая идея:
Поскольку вы поняли, как перемещаются данные, я полагаю, вы поняли, что count[]
сделать во всем коде. В блоке кода R
верхняя граница, которая 0xFF + 1
, а также R / 2
является 0x7F + 1
, Следовательно count[R] - count[R / 2]
общее число в диапазоне 0x80
в 0xFF
, Поэтому, добавив сдвиг count[R] - count[R / 2]
в count[0 .. R / 2]
и вычитая его из count[R / 2 .. R]
помогут номера в 0x00
в 0x7F
иметь выше count
значение, чем числа в 0x80
в 0xFF
В результате 0x80-0xFF в конечном итоге предшествует 0x00-0x7F.
Наконец, вам может быть любопытно: если первый бит является знаковым битом, почему 11111111
больше чем 10000001
? Разве это не -(127) < -(1)
? Это потому, что в компьютерной системе мы используем комплимент 2 вместо целых чисел со знаком, поэтому 11111111
на самом деле означает -1
, а также 10000001
на самом деле означает -127
,