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?
}

- Josh K

---

a保存整数输入数组？为什么不将count、pref和groups清零？在JS中，即使通过new Array(length)创建数组，它们的内容也是未定义的，而undefined + 0等于NaN。 - Mike Samuel

@Mike：首先，我甚至不确定这个排序算法应该如何工作，因此我也不知道哪里出了问题。count已经被清零，pref在使用之前已经初始化，而groups不是一个数组。 - Josh K

基数排序通过查看排序关键字的一部分进行排序，这些部分足够小，以至于一个部分的所有可能值可以描述一定数量的离散列表。想象一下对你的 CD 收藏进行排序：首先按艺术家姓名的第二个字母分类，然后按 A-Z 的顺序浏览这些分类并按首字母创建新的分类。当你再次拿起 A-Z 分类并从左到右将它们排在架子上时，它们就已经排好序了！ - Pointy

你能提供样例输入和输出吗？ - lincolnk

一个问题是，"b"似乎代表每个整数的位数大小，这对于Javascript来说将是错误的值。Javascript整数只有32位（或31位）。 - Pointy

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位开始，该代码将该元素复制到“堆”之一的末尾，即对应于4位值的堆。然后收集所有的堆，并从所有低4位为0，1等的值重新构建“a”。（显然会有一些间隙，所以跳过它们。）在整个循环的每次迭代结束时，除数乘以基数，以便下一组4位将被检查。

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

请注意，这仅适用于正数。对负数进行此操作会有点奇怪；最好将负数剥离成一个单独的数组，翻转符号，排序，然后反转。对正数进行排序，最后将反转的负数（再次翻转符号）粘贴到排序后的正数前面。

- Pointy

---

这个可以运行，我会拆开来看看能否理解。我想在我的一些代码中实现这种排序算法，我有你的许可吗？ - Josh K

当然，这是相当常见的事情。我很喜欢你的问题，因为我一直在努力让我的孩子们对用基数排序整理我的旧LP唱片集感到兴奋 :-) - Pointy

Answer 2

这个

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

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

我没有关于基数排序的参考资料，无法确定你应该在这里做什么。

- lincolnk

---

“pref”数组旨在保存每个基数桶中值的计数。如果我用JavaScript编写，我根本不会这样做；它就像是一个转录的C程序。 - Pointy

@Pointy：我几乎完全从一个C#实现中获得了这个代码。这可能是为什么它看起来像被记录下来一样的原因。;) - Josh K