我正在用他的 JavaScript 代码帮助某人，我的眼睛被一个看起来像这样的部分所吸引：
function randOrd(){
return (Math.round(Math.random())-0.5);
}
coords.sort(randOrd);
alert(coords);
我的第一个想法是：嘿，这不可能！但后来我做了一些实验，发现它确实至少似乎提供了很好的随机结果。
然后我做了一些网络搜索，几乎在顶部找到了一篇文章，其中最明显地复制了这段代码。看起来像一个相当受人尊敬的网站和作者......
但我的直觉告诉我，这一定是错的。特别是因为 ECMA 标准没有指定排序算法。我认为不同的排序算法会导致不同的非均匀洗牌。一些排序算法甚至可能无限循环......
但是你怎么看？
作为另一个问题......我现在如何去测量这种洗牌技术的结果有多随机？
更新：我做了一些测量并将结果发布在下面作为答案之一。
在乔恩已经涵盖了理论之后，这里有一个实现：
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 代码的开销，这可能会导致性能上的显着差异，这种差异会随着数组大小的增加而增加。
在对bobobobo 的回答的评论中，我说有问题的算法可能不会产生均匀分布的概率（取决于 的实现sort()）。
我的论点是这样的： 排序算法需要一定数量c的比较，例如c = n(n-1)/2冒泡排序。我们的随机比较功能使每次比较的结果具有同等可能，即有2^c 同等可能的结果。现在，每个结果都必须对应于n!数组条目的排列之一，这使得在一般情况下不可能均匀分布。（这是一种简化，因为需要的实际比较次数取决于输入数组，但断言仍应成立。）
正如 Jon 指出的那样，仅凭这一点就没有理由更喜欢 Fisher-Yates 而不是 using sort()，因为随机数生成器还将有限数量的伪随机值映射到n!排列。但是Fisher-Yates的结果应该还是会更好：
Math.random()在 范围内产生一个伪随机数[0;1[。由于 JS 使用双精度浮点值，这对应于2^x可能的值 where 52 ≤ x ≤ 63（我懒得找到实际数字）。Math.random()如果原子事件的数量处于同一数量级，则使用生成的概率分布将停止表现良好。
2^52使用 Fisher-Yates 时，相关参数是数组的大小，由于实际限制，不应接近。
使用随机比较函数进行排序时，该函数基本上只关心返回值是正数还是负数，所以这永远不会有问题。但也有类似的情况：因为比较函数表现良好，所以如前所述，2^c可能的结果同样可能。如果c ~ n log nthen 2^c ~ n^(a·n)where a = const，这使得它至少有可能2^c与（或什至小于）大小相同n!，从而导致分布不均匀，即使排序算法 where 均匀地映射到排列上也是如此。如果这有任何实际影响是超出我的。
真正的问题是排序算法不能保证均匀地映射到排列上。很容易看出 Mergesort 是对称的，但推理诸如 Bubblesort 或更重要的是 Quicksort 或 Heapsort 之类的东西却不是。
底线：只要sort()使用 Mergesort，你应该是相当安全的，除非在极端情况下（至少我希望这2^c ≤ n!是一个极端情况），如果不是，所有的赌注都没有了。
它从来都不是我最喜欢的洗牌方式，部分原因是它是特定于实现的，正如你所说。特别是，我似乎记得从 Java 或 .NET（不确定是哪个）排序的标准库通常可以检测到您是否最终在某些元素之间进行了不一致的比较（例如，您首先声明A < Band B < C，然后是C < A）。
它最终也比你真正需要的更复杂（就执行时间而言）洗牌。
我更喜欢 shuffle 算法，它有效地将集合划分为“shuffled”（在集合开始时，最初为空）和“unshuffled”（集合的其余部分）。在算法的每一步，选择一个随机的未混洗元素（可能是第一个）并将其与第一个未混洗元素交换 - 然后将其视为已混洗（即在心理上移动分区以包含它）。
这是 O(n) 并且只需要对随机数生成器进行 n-1 次调用，这很好。它还产生了真正的洗牌——任何元素都有 1/n 的机会出现在每个空间中，无论其原始位置如何（假设一个合理的 RNG）。排序后的版本近似于均匀分布（假设随机数生成器不会两次选择相同的值，如果它返回随机双精度值，这是极不可能的）但我发现更容易推理随机版本:)
这种方法称为Fisher-Yates shuffle。
我认为将这种 shuffle 编码一次并在需要对项目进行 shuffle 的任何地方重复使用它是一种最佳实践。然后，您无需担心排序实现的可靠性或复杂性。这只是几行代码（我不会在 JavaScript 中尝试！）
维基百科关于洗牌的文章（特别是洗牌算法部分）讨论了对随机投影进行排序 - 值得一读关于洗牌的不良实现的部分，所以你知道要避免什么。
我对这种随机排序的结果的随机性做了一些测量......
我的技术是采用一个小数组 [1,2,3,4] 并创建它的所有 (4! = 24) 个排列。然后我会多次将改组函数应用于数组并计算每个排列生成的次数。一个好的洗牌算法会将结果相当均匀地分布在所有排列中，而一个糟糕的洗牌算法不会产生这种均匀的结果。
使用下面的代码，我在 Firefox、Opera、Chrome、IE6/7/8 中进行了测试。
令我惊讶的是，随机排序和真正的随机排序都创建了同样均匀的分布。因此，似乎（正如许多人所建议的）主要浏览器正在使用合并排序。这当然并不意味着不能有一个浏览器，它的作用不同，但我想说的是，这种随机排序方法足够可靠，可以在实践中使用。
编辑：这个测试并没有真正正确地测量随机性或缺乏随机性。请参阅我发布的另一个答案。
但在性能方面，Cristoph 提供的 shuffle 功能显然是赢家。即使对于小型四元素数组，真正的随机排序的执行速度也大约是随机排序的两倍！
// Cristoph 发布的 shuffle 函数。
var shuffle = 函数（数组）{
var tmp，当前，顶部 = array.length；
如果（顶部）而（--顶部）{
当前 = Math.floor(Math.random() * (top + 1));
tmp = 数组[当前];
数组[当前] = 数组[顶部];
数组[顶部] = tmp;
}
返回数组；
};
// 随机排序函数
var rnd = 函数（） {
返回 Math.round(Math.random())-0.5;
};
var randSort = 函数（A）{
返回 A.sort(rnd);
};
var 排列 = 函数（A）{
如果（A.length == 1）{
返回[A]；
}
别的 {
var perms = [];
for (var i=0; i<A.length; i++) {
var x = A.slice(i, i+1);
var xs = A.slice(0, i).concat(A.slice(i+1));
var subperms = permutations(xs);
for (var j=0; j<subperms.length; j++) {
perms.push(x.concat(subperms[j]));
}
}
退货烫发；
}
};
var test = 函数（A，迭代，函数）{
//初始化排列
变量统计 = {};
var perms = permutations(A);
for (var i in perms){
统计[“”+烫发[i]] = 0;
}
// 多次洗牌并收集统计数据
变量开始=新日期（）；
for (var i=0; i<iterations; i++) {
var shuffle = func(A);
统计[“”+洗牌]++；
}
变量结束=新日期（）；
// 格式化结果
变量 arr=[];
for (var i in stats) {
arr.push(i+" "+stats[i]);
}
return arr.join("\n")+"\n\n耗时：" + ((end - start)/1000) + " seconds.";
};
alert("随机排序：" + test([1,2,3,4], 100000, randSort));
alert("shuffle:" + 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"));
我在我的网站上放置了一个简单的测试页面，显示了您当前的浏览器与使用不同方法洗牌的其他流行浏览器的偏差。它显示了仅使用的可怕偏见Math.random()-0.5，另一个没有偏见的“随机”洗牌，以及上面提到的 Fisher-Yates 方法。
您可以看到，在某些浏览器上，某些元素在“洗牌”期间根本不会改变位置的可能性高达 50%！
注意：您可以通过将代码更改为：通过@Christoph 为 Safari 实现 Fisher-Yates shuffle 的速度稍快一些：
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;
}
我认为这适用于您对分发不挑剔并且希望源代码很小的情况。
在 JavaScript（源不断传输）中，小的会影响带宽成本。
已经四年了，但我想指出的是，无论您使用哪种排序算法，随机比较器方法都不会正确分布。
证明：
n元素数组，有确切的n!排列（即可能的洗牌）。唯一可能正确分布的尺寸是 n=0,1,2。
作为练习，试着画出 n=3 的不同排序算法的决策树。
证明中有一个漏洞：如果一个排序算法依赖于比较器的一致性，并且与一个不一致的比较器有无限的运行时间，它可以有无限的概率和，即使它加起来也可以达到 1/6和中的每个分母都是 2 的幂。试着找到一个。
此外，如果比较器有固定的机会给出任一答案（例如(Math.random() < P)*2 - 1，对于常数P），则上述证明成立。如果比较器根据之前的答案更改其赔率，则可能会产生公平的结果。为给定的排序算法找到这样的比较器可能是一篇研究论文。
当然，这是一个 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）
虽然仍然是一个黑客。如果你想做得很好，你必须努力去做:)
如果您使用的是 D3，则有一个内置的随机播放功能（使用 Fisher-Yates）：
var days = ['Lundi','Mardi','Mercredi','Jeudi','Vendredi','Samedi','Dimanche'];
d3.shuffle(days);
迈克正在详细介绍它：
你能用这个Array.sort()函数来打乱一个数组吗？是的。
结果是否足够随机 -否。
考虑以下代码片段：
/*
* The following code sample shuffles an array using Math.random() trick
* After shuffling, the new position of each item is recorded
* The process is repeated 100 times
* The result is printed out, listing each item and the number of times
* it appeared on a given position after shuffling
*/
var array = ["a", "b", "c", "d", "e"];
var stats = {};
array.forEach(function(v) {
stats[v] = Array(array.length).fill(0);
});
var i, clone;
for (i = 0; i < 100; i++) {
clone = array.slice();
clone.sort(function() {
return Math.random() - 0.5;
});
clone.forEach(function(v, i) {
stats[v][i]++;
});
}
Object.keys(stats).forEach(function(v, i) {
console.log(v + ": [" + stats[v].join(", ") + "]");
});样本输出：
a: [29, 38, 20, 6, 7]
b: [29, 33, 22, 11, 5]
c: [17, 14, 32, 17, 20]
d: [16, 9, 17, 35, 23]
e: [ 9, 6, 9, 31, 45]
理想情况下，计数应该均匀分布（对于上面的示例，所有计数应该在 20 左右）。但他们不是。显然，分布取决于浏览器实现的排序算法以及它如何迭代数组项进行排序。
这是一种使用单个数组的方法：
基本逻辑是：
代码：
for(i=a.length;i--;) a.push(a.splice(Math.floor(Math.random() * (i + 1)),1)[0]);
没有什么问题。
您传递给 .sort() 的函数通常看起来像
函数排序函数（第一，第二）
{
// 例子：
返回第一 - 第二;
}
您在 sortFunc 中的工作是返回：
上面的排序功能把事情整理好。
如果你随机返回 - 和 +，你会得到一个随机排序。
就像在 MySQL 中一样：
SELECT * 从表 ORDER BY rand()