java - 基数排序，r的值

Question

基数排序请引用以下代码:

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);
    }
}

这是从维基百科下载的。

我认为该算法仅适用于完全除以 32 的 bits 参数值。因此，bits 应该是 2 或 4 之类的东西，而不是 10。请告诉我我是否正确。

Answer 1

简短回答:否

长答案:

可能的混淆是:

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

mask <<= bits移位 mask 的位留下 bits ，用零填充右侧。如果bits不除 32，则不会使用完整的 32 位。所以虽然bits 应该除以 32，选择不除以 32 的值也不会破坏代码。