以下基數排序會從Sedgewick's Algorithms textbook中進行四次計數排序(256個存儲桶,32位整數,從最低有效位數開始)。有關在Java中使用基數排序的問題
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;
}
這是什麼段的代碼的目的是什麼?謝謝!
謝謝,很好的解釋!在這種情況下,這段代碼實際上適用於包含非負整數的'int a []'(與代碼作者對第4-5行評論的假設相反)? – alwc 2014-09-01 03:10:56
是的,只要所有的整數都是'int'類型。 – nevets 2014-09-01 03:16:42