2014-09-01 44 views
1

以下基數排序會從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; 
} 

這是什麼段的代碼的目的是什麼?謝謝!

回答

4

代碼塊不正是評論說:

大多數顯著字節,0x80-0xFF來爲0x00-0x7F

這樣做的原因是:由於您使用int ,所以最重要的位是符號位。因此,0x80-0xFF範圍內最高有效字節的數字爲負數,因此應放在正數之前,其最高有效字節的範圍爲0x00-0x7F

如果你問代碼塊是如何實現它,這裏是一個簡單的想法:

既然你瞭解數據是如何移動的,所以我想你明白什麼count[]做的全部代碼。在代碼塊中,R是上限,它是0xFF + 1,而R/20x7F + 1。因此count[R] - count[R/2]是在0x800xFF範圍內的總數。因此,通過加入count[R] - count[R/2]轉變到count[0 .. R/2],並減去從count[R/2 .. R]將有助於號碼0x000x7F範圍具有較高的count值不是數字在0x80不等到0xFF,導致0x80-0xFF來爲0x00-0x7F最終前。

最後,您可能會好奇:如果第一位是符號位,爲什麼11111111大於10000001?是不是-(127) < -(1)?這是因爲在計算機系統中,我們使用的是2's compliment而不是有符號整數,因此11111111實際上是指-1,而10000001實際上是指-127

+0

謝謝,很好的解釋!在這種情況下,這段代碼實際上適用於包含非負整數的'int a []'(與代碼作者對第4-5行評論的假設相反)? – alwc 2014-09-01 03:10:56

+1

是的,只要所有的整數都是'int'類型。 – nevets 2014-09-01 03:16:42