javascript - 为什么这种混洗算法没有偏见

我和我的同事正在争论为什么list of JS tips & tricks中给出的混洗算法不会产生有偏见的结果，如天真混洗的Jeff Atwood describes排序。

技巧中的数组洗牌代码是:

list.sort(function() Math.random() - 0.5);

Jeff的天真洗牌代码是:

for (int i = 0; i < cards.Length; i++)
{
  int n = rand.Next(cards.Length);
  Swap(ref cards[i], ref cards[n]);
}

我写了这个JS来测试洗牌:

var list = [1,2,3];
var result = {123:0,132:0,321:0,213:0,231:0,312:0};
function shuffle() { return Math.random() - 0.5; }
for (var i=0; i<60000000; i++) {
    result[ list.sort(shuffle).join('') ]++;
}

为此，我从Firefox 5获得了如下结果:

订单计数％Diff真实平均
123 9997461 -0.0002539
132 10003451 0.0003451
213 10001507 0.0001507
231 9997563 -0.0002437
312 9995658 -0.0004342
321 10004360 0.000436

大概Array.sort遍历list数组并执行与Jeff的示例相似的(相邻)元素交换。那么，为什么结果看起来没有偏见呢？

最佳答案

我发现公正地出现的原因。

Array.sort()不仅返回数组，还更改了数组本身。如果我们为每个循环重新初始化数组，则会得到如下结果:

123 14941
132 7530
321 7377
213 15189
231 7455
312 7508

这显示出非常明显的偏见。

对于那些感兴趣的人，下面是修改后的代码:

var result = {123:0,132:0,321:0,213:0,231:0,312:0};
var iterations = 60000;
function shuffle() {
    comparisons++;
    return Math.random() - 0.5;
}
for (var i=0; i<iterations; i++) {
    var list = [1,2,3];
    result[ list.sort(shuffle).join('') ]++;
}
console.log(result);