我正在帮助某人编写他的JavaScript代码，我的眼睛被一个看起来像这样的部分所吸引：
function randOrd(){
return (Math.round(Math.random())-0.5);
}
coords.sort(randOrd);
alert(coords);
我的第一个问题是：嘿，这不可能奏效！但后来我做了一些实验，发现它确实至少似乎提供了很好的随机化结果。
然后我做了一些网络搜索，几乎在顶部找到了一篇文章，从中复制了这段代码。看起来像一个非常受人尊敬的网站和作者...
但我的直觉告诉我，这一定是错的。特别是因为排序算法不是由 ECMA 标准指定的。我认为不同的排序算法会导致不同的非均匀洗牌。一些排序算法甚至可能无限循环...
但你怎么看？
作为另一个问题...我现在如何去测量这种洗牌技术的结果有多随机？
更新：我做了一些测量，并在下面发布了结果作为答案之一。
在Jon已经涵盖了这个理论之后，这里有一个实现：
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;
}
算法是 ，而排序应该是 。根据执行 JS 代码与本机函数相比的开销，这可能会导致明显的性能差异，这应该随着数组大小而增加。O(n)O(n log n)sort()
在对bobobobo的答案的评论中，我指出所讨论的算法可能不会产生均匀分布的概率（取决于的实现）。sort()
我的论点是这样的：排序算法需要一定数量的比较，例如对于Bubblesort。我们的随机比较函数使每个比较的结果具有同等的可能性，即存在同样可能的结果。现在，每个结果都必须对应于数组条目的排列之一，这使得在一般情况下不可能进行偶数分布。（这是一种简化，因为实际比较次数取决于输入数组，但断言仍然应该成立。cc = n(n-1)/22^cn!
正如 Jon 所指出的，仅凭这一点并不是选择 Fisher-Yates 而不是使用的理由，因为随机数生成器也会将有限数量的伪随机值映射到排列中。但Fisher-Yates的结果应该仍然更好：sort()n!
Math.random()在 范围内生成一个伪随机数。由于JS使用双精度浮点值，这对应于可能的值（我懒得找到实际数字）。如果原子事件的数量具有相同的数量级，则 使用 生成的概率分布将停止运行良好。[0;1[2^x52 ≤ x ≤ 63Math.random()
使用Fisher-Yates时，相关参数是数组的大小，由于实际限制，永远不应该接近。2^52
当使用随机比较函数进行排序时，该函数基本上只关心返回值是正数还是负数，因此这永远不会成为问题。但也有类似的一个：因为比较函数表现良好，所以可能的结果，如前所述，同样可能。如果那么 where ，这使得它至少有可能具有相同的量级（甚至小于），从而导致分布不均匀，即使排序算法在哪里均匀地映射到排列上。如果这有什么实际影响，那将超出我。2^cc ~ n log n2^c ~ n^(a·n)a = const2^cn!
真正的问题是排序算法不能保证均匀地映射到排列上。很容易看出Mergesort是对称的，但是像Bubblesort或更重要的是Quicksort或Heapsort这样的东西的推理却不是。
底线：只要使用Mergesort，除了在角落的情况下（至少我希望这是一个角落的情况），你应该是相当安全的，如果没有，所有的赌注都被取消了。sort()2^c ≤ n!
它从来都不是我最喜欢的洗牌方式，部分原因是正如你所说，它是特定于实现的。特别是，我似乎记得从Java或.NET排序的标准库（不确定哪个）通常可以检测到您是否最终在某些元素之间进行了不一致的比较（例如，您首先声明和，但随后）。A < BB < CC < A
它也最终成为比您真正需要的更复杂的（在执行时间方面）的洗牌。
我更喜欢洗牌算法，它有效地将集合划分为“洗牌”（在集合开始时，最初是空的）和“未洗牌”（集合的其余部分）。在算法的每个步骤中，选择一个随机的未洗牌元素（可能是第一个），并将其与第一个未洗牌的元素交换 - 然后将其视为洗牌（即在精神上移动分区以包含它）。
这是O（n），只需要对随机数生成器进行n-1调用，这很好。它还会产生真正的洗牌 - 任何元素都有1/n的几率在每个空间中结束，无论其原始位置如何（假设合理的RNG）。排序版本近似于偶数分布（假设随机数生成器不会两次选择相同的值，如果它返回随机双精度值，则极不可能），但我发现更容易推理随机播放版本:)
这种方法被称为Fisher-Yates洗牌。
我认为这是一种最佳实践，只需对这个随机播放进行一次编码，然后在需要随机播放项目的任何位置重用它。然后，您无需担心排序实现的可靠性或复杂性。它只是几行代码（我不会在JavaScript中尝试！
维基百科上关于洗牌的文章（特别是洗牌算法部分）谈到了随机投影的排序 - 值得一读的是关于洗牌实现不佳的部分，所以你知道要避免什么。
