问使用JavaScript Array.sort()方法进行混洗是否正确？

EN

这从来不是我最喜欢的混洗方式，部分原因是正如你所说的，它是特定于实现的。特别是，我似乎记得，标准库排序从Java或.NET (不确定哪一个)通常可以检测到，如果你最终在某些元素之间进行了不一致的比较(例如，你首先声称A < B和B < C，然后C < A)。

它最终也会变得比你真正需要的更加复杂(就执行时间而言)。

我更喜欢shuffle算法，它有效地将集合划分为"shuffled“(在集合开始时，最初是空的)和"unshuffled”(集合的其余部分)。在算法的每一步，选择一个随机的未洗牌元素(可能是第一个)，并将其与第一个未洗牌元素交换-然后将其视为已洗牌元素(即在心理上移动分区以包括它)。

这是O(n)，并且只需要n-1次调用随机数生成器，这很好。它还会产生真正的混洗--任何元素都有1/n的机会在每个空间结束，而不管它的原始位置(假设一个合理的RNG)。排序后的版本近似于均匀分布(假设随机数生成器不会两次选取相同的值，如果它返回随机双精度值，这是非常不可能的)，但我发现更容易推断shuffle版本:)

这种方法称为Fisher-Yates shuffle。

我会将其视为一种最佳实践，即只需编写一次混洗代码，然后在需要混洗项目的任何地方重用它。那么你就不需要担心排序实现的可靠性和复杂性了。它只有几行代码(我不会在JavaScript中尝试！)

Wikipedia article on shuffling (特别是shuffle算法部分)讨论了如何对随机投影进行排序--值得一读的是关于一般情况下shuffling的糟糕实现的部分，这样您就知道应该避免什么了。

在Jon已经covered the theory之后，下面是一个实现：

function shuffle(array) {
    var tmp, current, top = array.length;

    if(top) while(--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
    }

    return array;
}

算法是O(n)，而排序应该是O(n log n)。根据与原生sort()函数相比执行JS代码的开销，这可能会导致noticable difference in performance随着数组大小的增加而增加。

在对bobobobo's answer的评论中，我指出所讨论的算法可能不会产生均匀分布的概率(取决于sort()的实现)。

我的论点是这样的:排序算法需要一定数量的比较，例如c = n(n-1)/2 c Bubblesort。我们的随机比较函数使每次比较的结果可能性相等，即存在2^c等概率结果。现在，每个结果都必须对应于数组条目的一个n!排列，这使得均匀分布在一般情况下是不可能的。(这是一种简化，因为所需的实际比较次数取决于输入数组，但断言仍然有效。)

正如Jon指出的那样，这本身并不是首选Fisher-Yates而不是使用sort()的理由，因为随机数生成器还会将有限数量的伪随机值映射到n!排列。但Fisher-Yates的结果仍然应该更好：

Math.random()在[0;1[范围内产生一个伪随机数。由于JS使用双精度浮点值，这与52 ≤ x ≤ 63 (我懒得找不到实际数字)的2^x可能值相对应。如果原子事件的数量是相同的数量级，则使用Math.random()生成的概率分布将停止表现良好。

当使用Fisher-Yates时，相关参数是数组的大小，由于实际限制，它永远不应该接近2^52。

当使用随机比较函数进行排序时，该函数基本上只关心返回值是正还是负，所以这永远不会是问题。但有一个类似的:因为比较函数表现良好，所以2^c可能的结果，如上所述，是同样可能的。If c ~ n log n然后2^c ~ n^(a·n) where a = const，这使得2^c至少有可能与n!具有相同的大小(甚至更小)，从而导致不均匀的分布，即使排序算法均匀地映射到置换数上。如果这有任何实际影响，我是无法做到的。

真正的问题是排序算法不能保证均匀地映射到排列上。很容易看出Mergesort是对称的，但对Bubblesort或更重要的Quicksort或Heapsort之类的东西进行推理却不是。

底线:只要sort()使用Mergesort，你就应该是相当安全的，除非是在角落情况下(至少我希望2^c ≤ n!是一个角落情况)，如果不是，所有的赌注都是无效的。

有趣的是，微软在他们的pick--browser-page中使用了相同的技术。

他们使用了一个略有不同的比较函数：

function RandomSort(a,b) {
    return (0.5 - Math.random());
}

在我看来几乎是一样的，但是

因此，我再次使用链接文章中使用的相同方法进行了一些测试，事实证明，随机排序方法产生了有缺陷的结果。这里有新的测试代码：

function shuffle(arr) {
  arr.sort(function(a,b) {
    return (0.5 - Math.random());
  });
}

function shuffle2(arr) {
  arr.sort(function(a,b) {
    return (Math.round(Math.random())-0.5);
  });
}

function shuffle3(array) {
  var tmp, current, top = array.length;

  if(top) while(--top) {
    current = Math.floor(Math.random() * (top + 1));
    tmp = array[current];
    array[current] = array[top];
    array[top] = tmp;
  }

  return array;
}

var counts = [
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
];

var arr;
for (var i=0; i<100000; i++) {
  arr = [0,1,2,3,4];
  shuffle3(arr);
  arr.forEach(function(x, i){ counts[x][i]++;});
}

alert(counts.map(function(a){return a.join(", ");}).join("\n"));