java - LSD基数排序为负整数，无队列

Question

首先，我知道这里有一个类似的问题：
Radix Sort for Negative Integers
然而，它与此不重复。
我正在研究基数排序，有一个关于Sedgewick教授和Wayne教授实现LSD基数排序的问题。

public static void sort(int[] a) {
    final int BITS = 32;                 // each int is 32 bits 
    final int R = 1 << BITS_PER_BYTE;    // each bytes is between 0 and 255
    final int MASK = R - 1;              // 0xFF
    final int w = BITS / BITS_PER_BYTE;  // each int is 4 bytes

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

最有意义的字节是怎么回事？它比我想到的任何东西都优雅得多。
我对自己解释这段代码的能力没有信心，很明显它处理的是负数，但我不太确定如何解释。
有人能更详细地解释这段代码吗？
更新
我想我还混淆了变量shift1和shift2的命名。如果我们稍微重命名一些，并添加一两条注释：

 if (d == w-1) {
            int totalNegatives= count[R] - count[R/2];
            int totalPositives= count[R/2];
            for (int r = 0; r < R/2; r++)
                // all positive number must come after any negative number
                count[r] += totalNegatives;
            for (int r = R/2; r < R; r++)
                // all negative numbers must come before any positive number
                count[r] -= totalPositives;
        }

这就更容易理解了。
其思想是，第一个正数只能位于最后一个负数之后，所有正数必须按顺序排在负数之后。因此，我们只需要在所有的正数中加上负数的总数，以确保正数确实会在负数之后出现。
对负数也有同样的类比。

Answer 1

基本算法
让我们从忽略最重要的块开始，并尝试理解代码的其余部分。
这些算法逐字节处理整数。每个字节可以有256个不同的值，这些值是单独计算的。这就是第一个街区发生的事。之后

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]++;
}

every count[i]是 a中在其第 i-1字节中具有值 d的元素的数目（注意，它们使用 count[c + 1]++，所以 count[0] == 0）
然后，该算法继续计算累积计数

for (int r = 0; r < R; r++)
    count[r+1] += count[r];

在这之后，every count[i]是该bucket的第一个元素应该在（中间）输出中结束的索引（注意 count的长度为257（ R + 1），因此可以忽略累积数组的最后一个元素我将把它放在下面的示例中的方括号中。）让我们看一个有4个值的示例（而不是256，以保持简洁）：
考虑一个字节值 [0, 3, 3, 2, 1, 2]的数组。这将给出计数 [0, 1, 1, 2, 2]和累计计数 [0, 1, 2, 4, (6)]。这些正是排序数组中第一个 0、 1、 2和 3的索引（这将是 [0, 1, 2, 2, 3, 3]）。
现在，算法使用这些累积计数作为（中间）输出的索引。每当从bucket复制一个元素时，它都会增加bucket索引，因此同一bucket中的元素会被复制到连续的点。

for (int i = 0; i < n; i++) {
    int c = (a[i] >> BITS_PER_BYTE*d) & MASK;
    aux[count[c]++] = a[i];
}

for (int i = 0; i < n; i++)
    a[i] = aux[i];

处理符号位
最有意义的位有点特殊，因为在 two's complement中它是符号，负数为1，正数为0因此，累积数组 count对于最后一步是不正确的。最有效位为0（正数）的值的计数位于数组的前半部分，最有效位为1（负数）的值的计数位于数组的后半部分因此，数组的上半部分和下半部分必须“翻转”。
这是通过将counts数组后半部分中的元素总数添加到counts数组前半部分中的每个元素来实现的。然后从counts数组后半部分的每个元素中减去counts数组前半部分的元素总数。如前所述， counts数组的长度为257，因此前128个元素（257/2）是前半部分，其余129个元素是后半部分。
让我们看一个新的例子，现在有两个带符号的位值，即 -2、 -1、 0和 1。它们的二进制表示是 10， 11， 00， 01，因此分别映射到 2， 3， 0， 1的无符号数。
将 a视为 [0, -1, -1, -2, 1, -2]转换为无符号： [0, 3, 3, 2, 1, 2]。应用该算法获得累积计数： [0, 1, 2, 4, (6)]。如果我们不进行翻转，我们最终将得到排序的无符号数组 [0, 1, 2, 2, 3, 3]，这相当于有符号数组 [0, 1, -2, -2, -1, -1]。分类不正确。
现在，让我们对签名字节应用额外的步骤。我们将累积 counts数组分成两部分： [0, 1]和 [2, 4, (6)]前半部分有2个（2-0）元素，后半部分有4个（6-2）元素。因此，我们在前半部分的每个元素上加4： [4, 5]，在后半部分的每个元素上减去2： [0, 2, (4)]将两部分组合在一起会得到 [4, 5, 0, 2, (4)]。
如果我们现在将这些计数用作最终无符号数组中的索引，则会得到 [2, 2, 3, 3, 0, 1]（第一个0位于索引4，第一个1位于索引5，依此类推）。将此值转换回有符号值将得到 [-2, -2, -1, -1, 0, 1]，这确实是正确的。
可能的混淆：该算法中混淆的部分之一是 counts数组用于两个不同的目的首先它用于计算单独的事件，然后它用于计算累积的事件单独计数时，不使用数组的第一个元素累积计数时，不使用数组的最后一个元素。
我认为如果使用两个独立的数组，算法会更简单。