c# - 基数排序中的分组何时会带来优势？

Question

我一直在测试this基数排序的实现:

public void RadixSort(int[] a)
{  
// our helper array 
int[] t=new int[a.Length]; 

// number of bits our group will be long 
int r=4; // try to set this also to 2, 8 or 16 to see if it is quicker or not 

// number of bits of a C# int 
int b=32; 

// counting and prefix arrays
// (note dimensions 2^r which is the number of all possible values of a r-bit number) 
int[] count=new int[1<<r]; 
int[] pref=new int[1<<r]; 

// number of groups 
int groups=(int)Math.Ceiling((double)b/(double)r); 

// the mask to identify groups 
int mask = (1<<r)-1; 

// the algorithm: 
for (int c=0, shift=0; c<groups; c++, shift+=r)
{ 
    // reset count array 
    for (int j=0; j<count.Length; j++)
        count[j]=0;

    // counting elements of the c-th group 
    for (int i=0; i<a.Length; i++)
        count[(a[i]>>shift)&mask]++; 

    // calculating prefixes 
    pref[0]=0; 
    for (int i=1; i<count.Length; i++)
        pref[i]=pref[i-1]+count[i-1]; 

    // from a[] to t[] elements ordered by c-th group 
    for (int i=0; i<a.Length; i++)
        t[pref[(a[i]>>shift)&mask]++]=a[i]; 

    // a[]=t[] and start again until the last group 
    t.CopyTo(a,0); 
} 
// a is sorted 
}

而且我不太明白为什么要将 r 设置为与 b 不同的值。 我通过始终将其设置为 b 值来获得最佳结果。使用比 b 更小的值可以获得优势的示例是什么？

编辑:这仅在您不使用输入类型的全部范围时才有效: 示例:如果您使用 r = b < 32，则使用 int[] 作为输入只会按 r = b 排序。因此在 b = 32 的情况下，您需要将 r 设置为 16

Answer 1

我不明白使用 2 位将 4000 个元素分成 3 个一组，因为 4000/3 不是 2 的幂。

如果值的范围是 0 到 4000，并且数组的大小 >= 4000，计数排序会更快:

#define SORTMAX 4000
void CountSort(int a[], size_t n)
{
    size_t cnt[SORTMAX + 1];
    for (size_t i = 0; i <= SORTMAX; i++)
        cnt[i] = 0;
    for (size_t i = 0; i < n; i++)
        cnt[a[i]]++;    // no out of range check
    for (size_t j = 0, i = 0; i <= SORTMAX; i++)
        while (cnt[i]--)
            a[j++] = (int)i;
}