使用 JavaScriptArray.sort()方法进行洗牌是否正确？

它从来都不是我最喜欢的洗牌方式，部分原因是它像您说的那样是特定于 是实现的。特别是，我似乎记得从 Java 或。NET (不确定是哪一个)可以经常检测到某些元素之间是否有不一致的比较(例如，你首先声称是 A < B和 B < C，然后是 C < A)。

它最终也会变成一个比您实际需要的更复杂的洗牌(在执行时间方面)。

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

这是 O (n) ，只需要对随机数生成器进行 n-1调用，这很好。它也产生一个真正的洗牌-任何元素有1/n 的机会结束在每个空间，无论它的原始位置(假设一个合理的 RNG)。排序后的版本 大概是均匀分布的(假设随机数生成器不会选择相同的值两次，如果它返回随机双精度数，这种情况发生的可能性很小) ，但我发现对于 shuffle 版本更容易推断:)

这种方法称为 Fisher-Yates 洗牌。

我认为这是一个最佳实践，编码这个洗牌一次，并重用它的任何地方，你需要洗牌项目。那么您就不必担心可靠性或复杂性方面的排序实现。这只是几行代码(我不会在 JavaScript 中尝试!)

关于洗牌的维基百科文章(特别是 shuffle 算法部分)讨论了对随机投影进行排序——值得一读关于一般性的不良 shuffle 实现的部分，这样您就知道应该避免什么了。

实际上，无限循环算法是不可能的。 如果你要对对象进行排序，你可以循环遍历坐标数组，然后执行以下操作:

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)

如果你想做得好，你必须用最难的方法:)

没什么问题。

传递给. sort () 通常的函数类似于

function sortingFunc( first, second )
{
// example:
return first - second ;
}

你在分类方面的工作是返回:

• 如果第一个数在第二个数之前，则为负数
• 一个正数，如果第一个应该在第二个后面
• 如果它们完全相等，则为0

上面的排序函数使事情井然有序。

如果返回 -s 和 + 的顺序是随机的，就会得到一个随机排序。

比如 MySQL:

SELECT * from table ORDER BY rand()

在 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)。与本机 sort()函数相比，执行 JS 代码的开销有所不同，这可能导致 表现上的显著差异随着数组大小的增加而增加。

在对 波波波的回答的评论中，我指出有问题的算法可能不会产生均匀分布的概率(取决于 sort()的实现)。

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

正如 Jon 指出的那样，这一点本身并不能说明 Fisher-Yates 优于使用 sort()的原因，因为随机数生成器也会将有限数目的伪随机值映射到 n!排列。但费舍尔-耶茨的结果应该更好:

Math.random()产生一个范围为 [0;1[的伪随机数。由于 JS 使用双精度浮点值，这对应于 2^x的可能值，其中 52 ≤ x ≤ 63(我太懒了，找不到实际数字)。如果原子事件的数量相同，那么使用 Math.random()生成的概率分布就会停止正常工作数量级。

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

当使用随机比较函数进行排序时，函数基本上只关心返回值是正值还是负值，因此这不会成为问题。但是有一个类似的例子: 因为比较函数表现良好，所以如上所述，2^c可能的结果是同样可能的。如果是 c ~ n log n，那么就是 2^c ~ n^(a·n)，其中的 a = const，这至少使得 2^c的大小与(甚至小于) n!相同，从而导致了不均匀的分布，即使排序算法在哪里映射到排列上是均匀的。如果这有任何实际影响，我都不知道。

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

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

我认为对于不挑剔发行版的情况，并且希望源代码很小的情况，这样做是可以的。

在 JavaScript 中(源代码不断传输) ，小的带宽成本会有所不同。

我测量了这种随机排序的结果有多随机。

我的技巧是获取一个小数组[1,2,3,4]并创建所有(4！它的排列组合。然后，我将对数组应用洗牌函数大量的次数，并计算每个排列生成的次数。一个好的洗牌算法会将结果均匀地分布在所有的排列中，而一个坏的算法不会产生统一的结果。

使用下面的代码，我在 Firefox，Opera，Chrome，IE6/7/8中测试过。

令我惊讶的是，随机排序和真正的洗牌都创造了同样统一的分布。因此，似乎(正如许多人所建议的那样)主要浏览器都在使用合并排序。当然，这并不意味着，没有一个不同的浏览器，但是我想说，这意味着，这种随机排序方法足够可靠，可以在实践中使用。

编辑: 这个测试并没有真正正确地测量随机性或缺乏随机性。参见我发布的另一个答案。

但是在性能方面，克里斯托弗赋予的洗牌功能是一个明显的赢家。即使对于小型的四元素数组，真正的 shuffle 的执行速度也是 Random-sort 的两倍！

// The shuffle function posted by Cristoph.
var shuffle = function(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;
};


// the random sort function
var rnd = function() {
return Math.round(Math.random())-0.5;
};
var randSort = function(A) {
return A.sort(rnd);
};


var permutations = function(A) {
if (A.length == 1) {
return [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]));
}
}
return perms;
}
};


var test = function(A, iterations, func) {
// init permutations
var stats = {};
var perms = permutations(A);
for (var i in perms){
stats[""+perms[i]] = 0;
}


// shuffle many times and gather stats
var start=new Date();
for (var i=0; i<iterations; i++) {
var shuffled = func(A);
stats[""+shuffled]++;
}
var end=new Date();


// format result
var arr=[];
for (var i in stats) {
arr.push(i+" "+stats[i]);
}
return arr.join("\n")+"\n\nTime taken: " + ((end - start)/1000) + " seconds.";
};


alert("random sort: " + test([1,2,3,4], 100000, randSort));
alert("shuffle: " + test([1,2,3,4], 100000, shuffle));