无队列负整数的LSD基排序

Question

首先，我知道这里有一个类似的问题：负整数的基排序

然而，它并不是重复的这一个。

我正在研究基类，并对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]++;
}

每个count[i]都是a中在其d第四个字节中有值i-1的元素的数量(注意，它们使用count[c + 1]++，所以使用count[0] == 0)。

然后，该算法继续使用

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

在此之后，每个count[i]都是该桶的第一个元素应该在(中间)输出中结束的索引。(请注意，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])。

现在，该算法使用这些累积计数作为(中间)输出中的索引。每当它从那个桶中复制一个元素时，它就会增加桶索引，这样来自同一个桶的元素就会被复制到连续的点。

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

处理符号位

最重要的位有点特别，因为在二补中它是符号，负数是1，正数是0。因此，累积数组count对于最后一步是不正确的。最重要位为0的值(正数)的计数位于数组的前半部分，最重要位为1的值(负数)的计数位于数组的后半部分。因此，数组的前半部分和下半部分必须“翻转”。

这是通过将计数数组后半部分中的元素总数添加到计数数组前半部分中的每个元素来实现的。并从计数数组的下半部分的每个元素中减去计数数组前半部分中的元素总数。如前所述，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数组用于两个不同的目的。首先，它用于计数单独的事件，然后用于计数累积的事件。单独计数时，不使用数组的第一个元素。累积计数时，不使用数组的最后一个元素。

我认为如果使用两个单独的数组，算法会更简单。