javascript中的基数排序

这个循环基本上做同样的事情,以一种更为javascript-y的方式:

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位值的元素。然后,它收集堆并重新构建“A”,从低4位为0,然后是1等的所有值开始(显然会有一些间隙,因此跳过这些间隙)。在整个循环的每次迭代结束时,除数乘以基数,以便检查下一组4位。

一旦除数耗尽了整数的可用范围,就完成了。

注意这只适用于 积极的 数字。用负数做这个会有点奇怪;将负数分为一个单独的数组,翻转符号,排序,然后反转可能更容易。对正数进行排序,然后最后将反转的负数(再次翻转符号)粘到已排序的正数的前面。

这

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

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

我手头没有基数排序的参考资料来确定您应该在这里做什么。