使用JavaScript Array.sort（）方法进行混洗是否正确？
我用他的JavaScript代码帮助某人，我的眼睛被一个看起来像这样的部分抓住：
function randOrd(){ return (Math.round(Math.random())-0.5); } coords.sort(randOrd); alert(coords); 我的第一个虽然是： 嘿，这不可能工作！ 但后来我做了一些实验，发现至less似乎提供了很好的随机结果。
然后，我做了一些networkingsearch，几乎在顶部find了一个文件，从这个代码是最ceartanly复制。 看起来像一个相当可敬的网站和作者…
但我的直觉告诉我，这一定是错的。 特别是由于ECMA标准没有规定sortingalgorithm。 我认为不同的sortingalgorithm会导致不同的非均匀混洗。 一些sortingalgorithm可能甚至无限循环…
但你觉得呢？
另外还有一个问题，我现在怎么去衡量这个混洗技术的结果是多么的随意？
更新：我做了一些测量，并发布了下面的结果作为答案之一。
这从来都不是我最喜欢的洗牌方式，部分原因在于它像你说的那样是特定于实现的。 特别是，我似乎记得，从Java或.NET（不知道是哪一种）的标准库sorting，如果最终得出一些元素之间不一致的比较（例如，您首先声明A < B和B < C ，但是C < A ）。
它也最终是一个比你真正需要的更复杂的（在执行时间上）洗牌。
我更喜欢shufflealgorithm，它有效地将收集分为“混洗”（在收集开始时，最初是空的）和“不混杂”（收集的其余部分）。 在algorithm的每一步，select一个随机的非混洗元素（可能是第一个），并与第一个非混洗元素进行交换 – 然后将其视为混洗（即精神上移动分区以包含它）。
这是O（n），只需要对随机数发生器进行n-1次调用，这很好。 它也产生真正的洗牌 – 任何元素有1 / n的机会结束在每个空间，无论其原始位置（假设一个合理的RNG）。 sorting后的版本接近于均匀分布（假设随机数生成器不会select相同的值两次，如果它返回随机双数，这是不太可能的），但我觉得更容易推理关于洗牌版本:)
这种方法被称为Fisher-Yates shuffle 。
我认为这是最好的做法，编码这个洗牌一次，并随时随地重复使用它来洗牌项目。 那么你不需要担心在可靠性或复杂性方面的sorting实现。 这只是几行代码（我不会尝试JavaScript！）
关于洗牌的维基百科文章 （特别是洗牌algorithm部分）讨论了对随机投影进行sorting的问题 – 值得一读关于糟糕的洗牌实现的部分，所以你知道该怎么回避。
在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; }
algorithm是O(n) ，而sorting应该是O(n log n) 。 根据与本地sort()函数相比执行JS代码的开销，这可能会导致性能的显着差异，这应该随着数组大小而增加。
在对bobobobo的回答的评论中，我指出所讨论的algorithm可能不会产生均匀分布的概率（取决于sort()的实现）。
我的观点如下：sortingalgorithm需要一定数量的比较，例如Bubblesort的c = n(n-1)/2 。 我们的随机比较函数使得每个比较的结果具有相同的可能性，即有2^c 相等的可能结果。 现在，每个结果都必须对应一个n! 数组条目的排列，这在一般情况下是不可能均匀分布的。 （这是一个简化，因为需要比较的实际数量取决于input数组，但断言仍应该保持。）
正如Jon指出的那样，单独使用sort()就没有理由selectFisher-Yates，因为随机数生成器也会将有限数量的伪随机值映射到n! 排列。 但是Fisher-Yates的结果应该还是比较好的：
Math.random()产生范围[0;1[的伪随机数。 由于JS使用双精度浮点值，这对应于2^x可能的值，其中52 ≤ x ≤ 63 （我懒得find实际的数字）。 如果primefaces事件的数量是相同的数量级，使用Math.random()生成的概率分布将停止行为。
当使用Fisher-Yates时，相关参数是数组的大小，由于实际的限制，决不应该接近2^52 。
当使用随机比较函数进行sorting时，函数基本上只关心返回值是正数还是负数，所以这不会成为问题。 但也有一个类似的结论：由于比较函数的性能良好，所以2^c可能的结果如上所述是相同的。 如果c ~ n log n那么2^c ~ n^(a·n)其中a = const ，这使得至less有可能2^c的大小与（或者甚至小于） n!相等n! 从而导致分布不均匀，即使将sortingalgorithm均匀地映射到置换上。 如果这有什么实际影响超出我的话。
真正的问题是sortingalgorithm不能保证均匀映射到排列上。 很容易看出Mergesort是对称的，但推理像Bubblesort，更重要的是，Quicksort或Heapsort不是。
底线：只要sort()使用Mergesort，除了在angular落的情况下（至less我希望2^c ≤ n!是一个angular落的情况），你应该是合理安全的，如果不是，所有的投注都closures。
我做了一些随机sorting结果的随机测量。
我的技术是采取一个小数组[1,2,3,4]，并创build它的所有（4！= 24）排列。 然后我将这个混洗函数应用到数组中，并计算每个排列产生的次数。 一个好的洗牌algorithm会将结果相当均匀地分布在所有的排列上，而坏的algorithm则不会产生统一的结果。
使用下面的代码我在Firefox，Opera，Chrome，IE6 / 7/8testing。
令我惊奇的是，随机sorting和真正的洗牌都创造了同样均匀的分布。 所以似乎（如许多人所build议的），主要的浏览器正在使用合并sorting。 这当然不意味着在那里不能有一个浏览器，这样做是不一样的，但我想这意味着，这种随机sorting方法在实践中足够可靠。
编辑：这个testing没有真正测量正确的随机性或缺乏。 看到我张贴的其他答案。
但在性能方面，克里斯托弗给出的洗牌function是明显的赢家。 即使对于小型四元素arrays，真正的洗牌也是随机sorting的两倍！
// Cristoph发布的shuffle函数
var shuffle = function（array）{
var tmp，current，top = array.length;
if（top）while（ - top）{
当前= Math.floor（Math.random（）*（top + 1））;
tmp = array [current];
array [current] = array [top];
array [top] = tmp;
}
返回数组;
};
//随机sortingfunction
var rnd = function（）{
返回Math.round（Math.random（）） - 0.5;
};
var randSort = function（A）{
返回A.sort（rnd）;
};
var permutations = function（A）{
如果（A.length == 1）{
返回[A];
}
else {
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 = function（A，iterations，func）{
//初始化排列
var stats = {};
var perms =排列（A）;
for（var i perms）{
stats [“”+ perms [i]] = 0;
}
//洗牌多次并收集统计信息
var start = new Date（）;
for（var i = 0; i <iterations; i ++）{
var shuffled = func（A）;
统计[ “” +改组] ++;
}
var end = new Date（）;
//格式结果
var arr = [];
for（var i in stats）{
arr.push（i +“”+ stats [i]）;
}
返回arr.join（“\ n”）+“\ n \ nlogging时间：”+（（结束 - 开始）/ 1000）+“秒”。
};
alert（“random sort：”+ test（[1,2,3,4]，100000，randSort））;
alert（“shuffle：”+ test（[1,2,3,4]，100000，shuffle））;
有趣的是， 微软在pick-random-browser-page中使用了相同的技术 。
他们使用了稍微不同的比较function：
function RandomSort(a,b) { return (0.5 - Math.random()); }
看起来几乎和我一样，但结果并不是那么随意的…
所以我再次用相同的方法做了一些testruns，事实上 – 这个随机sorting方法的结果是错误的。 新的testing代码在这里：
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"));
我在我的网站上放置了一个简单的testing页面 ，显示了当前浏览器与使用不同方法混洗的其他stream行浏览器之间的偏见。 它显示了使用Math.random()-0.5 ，另一个没有偏见的“随机”混洗以及上面提到的Fisher-Yates方法的糟糕的偏见。
你可以看到，在一些浏览器上，在“洗牌”过程中，某些元素根本不会改变的可能性高达50％。
注意：通过将代码更改为：可以使@Christoph的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; }
testing结果： http ： //jsperf.com/optimized-fisher-yates
我认为对于分发不够挑剔的情况并且希望源代码很小的情况就可以。
在JavaScript（源代码不断传输）中，小带宽成本是有差别的。
当然，这是一个黑客。 实际上，无限循环algorithm是不可能的。 如果你正在sorting对象，你可以循环访问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，则有一个内置的洗牌function（使用Fisher-Yates）：
var days = ['Lundi','Mardi','Mercredi','Jeudi','Vendredi','Samedi','Dimanche']; d3.shuffle(days);
这里是迈克详细介绍它：
已经四年了，但是我想指出的是，无论使用什么sortingalgorithm，这可能都不会起作用。
certificate：有n！ n个元素的排列。 每次你做一个比较，你都是在这组排列的两个子集之间进行select。 所以每个置换的概率都是分数，对于某个k，分母2 ^ k。
对于n = 3，有六个同样可能的排列。 那么每个排列的机会是1/6。 1/6不能表示为2的幂作为分母。 尝试用不同的方式绘制决策树。
唯一可能正确分布的大小是n = 0,1,2。
这是一个使用单个数组的方法：
基本的逻辑是：
码：
for(i=a.length;i--;) a.push(a.splice(Math.floor(Math.random() * (i + 1)),1)[0]);
你可以使用Array.sort（）函数来洗牌数组 – 是的。
结果足够随机 – 可能不是。 我用这个JavaScript进行testing：
var array = ["a", "b", "c", "d", "e"]; var stats = {}; for (var i = 0; i < array.length; i++) { stats[array[i]] = []; for (var j = 0; j < array.length; j++) { stats[array[i]][j] = 0; } } //stats = { // a: [0, 0, 0, ...] // b: [0, 0, 0, ...] // c: [0, 0, 0, ...] // ... // ... //} for (var i = 0; i < 100; i++) { var clone = array.slice(0); clone.sort(function() { return Math.random() - 0.5; }); for (var j = 0; j < clone.length; j++) { stats[clone[j]][j]++; } } for (var i in stats) { console.log(i, stats[i]); }
示例输出：
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左右）。 但他们不是。 显然，分布依赖于浏览器实现的sortingalgorithm，以及它如何迭代数组项以进行sorting。
本文提供了更多的见解：
Array.sort（）不应该用来洗牌数组
Addi Osmani实施了这个版本的Fisher-Yates shuffle ：
function shuffle(array) { var rand, index = -1, length = array.length, result = Array(length); while (++index < length) { rand = Math.floor(Math.random() * (index + 1)); result[index] = result[rand]; result[rand] = array[index]; } return result; }
对于那些回头看看这个，这里是certificatesort（）不工作随机： http : //phrogz.net/JS/JavaScript_Random_Array_Sort.html
没有什么问题。
传递给.sort（）的函数通常看起来像这样
函数sortingFunc（第一，第二）
{
//示例：
返回一秒钟;
}
您在sortingFunc中的工作是返回：
- 一个负数，如果第一个在第二个之前
- 如果第一个应该是第二个是正数
- 如果它们完全相等则为0
上面的sortingfunction是按顺序排列的。
如果你随机地返回“+”和“+”，你会得到一个随机的sorting。
像在MySQL中一样：
SELECT * from table ORDER BY rand（）
