JavaScript 中的基数排序

Question

我想出了以下方法，但可以预见的是它不起作用。

var t = new Array(a.length);
var r = 4;
var b = 64;

var count = new Array(1<<r);
var pref = new Array(1<<r);

var groups = Math.ceil(b / r);

var mask = (1 << r) - 1;

var shift = 0;
for(var c = 0; c < groups; c++)
{
    shift += r;

    for(var j = 0; j < count.length; j++)
    {
        count[j] = 0;
    }

    for(var i = 0; i < a.length; i++)
    {
        count[ (a[i] >> shift) & mask ]++;
    }

    pref[0] = 0;

    for(var i = 0; i < count.length; i++)
    {
        pref[i] = pref[i-1] + count[i-1];
    }

    for(var i = 0; i < a.length; i++)
    {
        t[ pref[ (a[i] >> shift) & mask ]++ ] = a[i];
    }

    for(var i = 0; i < a.length; i++)
    {
        a[i] = t[i];
    }
    // a is sorted?
}

Answer 1

这个循环基本上以一种更 JavaScript 的方式做同样的事情：

for (var div = 1, radix = 16; div < 65536 * 65536; div *= radix) {
  var piles = [];

  for (var i = 0; i < a.length; ++i) {
    var p = Math.floor(a[i] / div) % radix;
    (piles[p] || (piles[p] = [])).push(a[i]);
  }

  for (var i = 0, ai = 0; i < piles.length; ++i) {
    if (!piles[i]) continue;
    for (var pi = 0; pi < piles[i].length; ++pi)
      a[ai++] = piles[i][pi];
  }
}

这个循环不是像 C 程序员那样做，而是构建一个列表列表，每个可能的 4 位值都有一个列表。我避免使用位移运算符，因为这是 Javascript，虽然它们确实有效，但当数字变大时，事情就会变得有趣。

从“a”中每个值的低 4 位开始，代码将“a”的该元素复制到其中一个“堆”的末尾，即对应于 4 位值的堆。然后，它收集这些堆并从低 4 位为 0、然后为 1 等的所有值开始重建“a”。（显然会有一些间隙，因此会跳过这些间隙。）在每次迭代结束时在整个循环中，除数乘以基数，以便检查下一组 4 位。

一旦除数用完可用的整数范围，就完成了。

请注意，这仅适用于正数。用负数来做这件事有点奇怪；将负数剥离到单独的数组中，翻转符号，排序，然后反转可能会更容易。对正数进行排序，然后最后将反转的负数（再次翻转符号）粘贴到已排序的正数的前面。

Answer 2

这

for(var i = 0; i < count.length; i++) 
{ 
    pref[i] = pref[i-1] + count[i-1]; 
} 

是一个问题，因为在第一次迭代中，i 为零，因此 pref[ 0 - 1 ] 不会很好地工作。

我没有方便的基数排序参考来确定您实际上应该在这里做什么。