我正在帮助别人调试他的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;
}
这个算法的时间复杂度为O(n)，而排序应该是O(n log n)。根据执行JS代码与本地sort()函数相比的开销，这可能会导致性能上的明显差异，并且随着数组大小的增加而增加。
sort()的实现方式）。c = n(n-1)/2。我们的随机比较函数使每个比较的结果同等可能，即有2^c个等可能的结果。现在，每个结果都必须对应于数组条目的n!个排列之一，这在一般情况下使得均匀分布不可能。（这是一个简化，因为实际需要比较的数量取决于输入数组，但这个断言仍然成立。）sort()，因为随机数生成器也将将有限数量的伪随机值映射到n!个排列中。但Fisher-Yates的结果仍然应该更好：
Math.random()在范围[0;1[内产生伪随机数。由于JS使用双精度浮点值，因此这对应于52 ≤ x ≤ 63的2^x个可能值（我懒得找实际数字）。使用Math.random()生成的概率分布如果原子事件的数量与其数量级相同，它将停止表现良好。sort()使用Mergesort，您应该是相对安全的，除非在极端情况下（至少我希望2^c ≤ n!是一个极端情况），否则一切都无法确定。这从来不是我最喜欢的洗牌方式，部分原因是正如你所说，它是特定于实现的。特别地，我记得标准库排序算法Java或.NET（不确定哪个）通常能够检测到一些元素之间存在不一致的比较（例如，你首先声明A < B和B < C，但是接下来又有 C < A）。
相对而言，这种方法也会变成一个更加复杂（在执行时间方面）的洗牌操作，其实并非真正需要的。
我更喜欢的是将集合有效地划分为“洗过的”（在集合开头，最初为空）和“未洗过的”（集合的其余部分）所采用的洗牌算法。在算法的每个步骤中，选择一个随机的未洗过元素（可以是第一个）并将其与第一个未洗过的元素交换 - 然后将其视为已洗过（即在心里移动分区以包含它）。
这是O(n)的，并且只需要n-1次调用随机数生成器，这很好。它还产生了一个真正的洗牌效果 - 任何元素都有1/n的机会进入每个空间，而不管其原始位置如何（假设随机数生成器是合理的）。排序版本近似于均匀分布（假设随机数生成器不会选择相同的值两次，这在返回随机双倍时极不可能），但我发现关于洗牌版本更容易推理:)
这种方法称为Fisher-Yates shuffle。
我认为最好的实践是编写一次此洗牌操作并在需要洗牌项目的所有地方重复使用。然后你就不必担心排序实现的可靠性或复杂性了。这只需要几行代码（我不会尝试在JavaScript中编写代码！）
《洗牌的维基百科文章》（特别是关于洗牌算法部分）讨论了对随机投影进行排序 - 值得阅读有关普遍洗牌实现的糟糕部分，以便知道避免什么。
2^x 个状态，即总共将有 2^(xn) 个状态，这应该比 2^c 大得多——请参见我编辑后的答案以获取详细信息。 - Christophvar permutations = function(A) {
if (A.length === 0)
return [[]];
else {
var perms = [];
for (var i=0; i<A.length; i++) {
var x = A[i];
var subperms = permutations(A.slice(0,i).concat(A.slice(i+1)));
for (var j=0; j<subperms.length; j++) {
perms.push(x.concat(subperms[j]));
}
}
return perms;
}
};
var test = function(A, iterations, func) {
// 初始化排列
var stats = {};
var perms = permutations(A);
for (var i in perms){
stats[""+perms[i]] = 0;
}
// 洗牌多次并收集统计数据
var start=new Date();
for (var i=0; i<iterations; i++) {
var shuffled = func(A);
stats[""+shuffled]++;
}
var end=new Date();
// 格式化结果
var arr=[];
for (var i in stats) {
arr.push(i+" "+stats[i]);
}
return arr.join("\n")+"\n\n花费时间: " + ((end - start)/1000) + " 秒.";
};
alert("随机排序: " + test([1,2,3,4], 100000, randSort));
alert("洗牌: " + test([1,2,3,4], 100000, shuffle));
有趣的是，微软在其pick-random-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"));
sort()зҡ„жҜ”иҫғеҮҪж•°еә”иҜҘиҝ”еӣһдёҖдёӘж•°еӯ—пјҢж №жҚ®aе’Ңbзҡ„жҜ”иҫғз»“жһңеӨ§дәҺгҖҒе°ҸдәҺжҲ–зӯүдәҺйӣ¶гҖӮ (https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/sort) - LarsH我在我的网站上放置了一个简单的测试页面，展示了使用不同方法进行洗牌时，您当前浏览器与其他流行浏览器之间的偏差。它显示了仅使用Math.random()-0.5的可怕偏见，另一种没有偏见的“随机”洗牌以及上面提到的Fisher-Yates方法。
您可以看到，在某些浏览器上，有高达50%的概率某些元素在“洗牌”期间根本不会改变位置！
注意：您可以通过更改代码来使@Christoph编写的Fisher-Yates shuffle在Safari中稍微快一点：
function shuffle(array) {
for (var tmp, cur, top=array.length; top--;){
cur = (Math.random() * (top + 1)) << 0;
tmp = array[cur]; array[cur] = array[top]; array[top] = tmp;
}
return array;
}
arr = arr.map(function(n){return [Math.random(),n]}).sort().map(function(n){return n[1]}); 这种方式，它的优点是长度不会过长，而且分配实际上是正确的。还有一些非常压缩的 Knuth/F-Y 洗牌变体。 - Daniel Martinarr = arr.map(function(n){return [Math.random(),n];}).sort().map(function(n){return n[1];});。 - Giacomo1968
这确实是一种hack。在实际应用中，无限循环算法不太可能出现。 如果你正在对对象进行排序，可以遍历coords数组并执行类似以下的操作：
for (var i = 0; i < coords.length; i++)
coords[i].sortValue = Math.random();
coords.sort(useSortValue)
function useSortValue(a, b)
{
return a.sortValue - b.sortValue;
}
然后再次循环遍历它们以删除sortValue。
但这仍然是一种折衷方法。如果您想要漂亮地完成它，您必须走弯路 :)
coords.map(v=>[v,Math.random()]).sort((a,b)=>a[1]-b[1]).map(v=>v[0]) - user20091357var days = ['Lundi','Mardi','Mercredi','Jeudi','Vendredi','Samedi','Dimanche'];
d3.shuffle(days);
以下是Mike详细说明：