基数排序在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，而他们这样做的工作的，事情就变得有趣，当数字变得大。

在的“一”，代码拷贝该元素的每个值的低4位开始的“a”到“桩”中的一个的端部，即是对应于该4位值的一个。然后它收集了桩和重建的“a”从所有其低4位为0，则如图1所示，等的值的起始（显然还会有一些间隙，所以那些被跳过。）在每次迭代的结尾整个环路的，除数由基数相乘，使得4位下一组进行研究。

在除数已用尽整数的可用范围，它的完成。

请注意，这仅适用于正数字工作。负数这样做会有点怪异;它可能是更容易的负数去掉到一个单独的阵列中，翻转标志，排序，然后反转。排序的正数，然后最终胶反转负数（再次翻转标志）至前面排序的正数。

Answer 2

此

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

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

我没有为基数排序方便的引用，以确定你应该真正在这里做什么。