Radix Sort, der Wert von r

Question

den folgenden Code vertretend für Radixsort:

class RadixSort 
{ 
    public static void radix_sort_uint(int[] a, int bits) 
    { 

     int[] b = new int[a.length]; 
     int[] b_orig = b; 


     int rshift = 0; 
     for (int mask = ~(-1 << bits); mask != 0; mask <<= bits, rshift += bits) { 

      int[] cntarray = new int[1 << bits]; 

      for (int p = 0; p < a.length; ++p) { 
       int key = (a[p] & mask) >> rshift; 
       ++cntarray[key]; 
      } 


     for (int i = 1; i < cntarray.length; ++i) 
         cntarray[i] += cntarray[i-1]; 


      for (int p = a.length-1; p >= 0; --p) { 
       int key = (a[p] & mask) >> rshift; 
       --cntarray[key]; 
       b[cntarray[key]] = a[p]; 
      } 


      int[] temp = b; b = a; a = temp; 
     } 


     if (a == b_orig) 
      System.arraycopy(a, 0, b, 0, a.length); 
    } 
} 

Dies wird von wikipedia heruntergeladen.

Ich glaube, dass der Algorithmus nur für den Wert von bits Parameter funktioniert, die 32 perfekt zu teilen. Also, bits sollte so etwas wie 2 oder 4, aber nicht 10 sein. Bitte lassen Sie mich wissen, wenn ich Recht habe.

Answer 1

Kurze Antwort: Nein

Lange Antwort:

Die wahrscheinliche Linie der Verwirrung ist:

for (int mask = ~(-1 << bits); mask != 0; mask <<= bits, rshift += bits) { 

mask <<= bits verschiebt die Bits mask durch bits links, das Recht, mit Nullen Polsterung. Wenn bits 32 nicht teilt, werden die vollen 32 Bits nicht verwendet. Also während bitssollte 32 dividieren, wählen Sie einen Wert, der den Code nicht bricht.