使用JavaScript Array.sort（）方法进行改组是否正确？

Question

我正在帮助别人使用他的JavaScript代码，但我的眼睛被一段看起来像这样的部分所吸引：

function randOrd(){
  return (Math.round(Math.random())-0.5);
}
coords.sort(randOrd);
alert(coords);

我的第一个想法是： 嘿，这可能行不通！ 但是后来我做了一些实验，发现它确实确实至少提供了很好的随机结果。

但是我的直觉告诉我，这一定是错误的。特别是由于ECMA标准未指定排序算法。我认为不同的排序算法将导致不同的不均匀混洗。一些排序算法甚至可能无限循环…

但是你觉得呢？

还有另一个问题……我现在将如何测量这种改组技术的结果的随机性？

更新： 我做了一些测量，并将结果发布在下面作为答案之一。

Answer 1

这从来不是我最喜欢的改组方式，部分原因是您所说的是特定于实现的。尤其是，我似乎还记得，从Java或.NET（不确定哪个）排序的标准库通常可以检测到是否最终在某些元素之间进行了不一致的比较（例如，首先声明A < B和B < C，然后声明C < A）。

最后，它还会以比您真正需要的更复杂的（就执行时间而言）洗牌结束。

我更喜欢shuffle算法，该算法可以有效地将集合划分为“ shuffled”（在集合的开头，最初为空）和“
unshuffled”（集合的其余部分）。在算法的每个步骤中，选择一个随机的未改组元素（可以是第一个元素），然后将其与第一个未改组的元素交换-
然后将其视为已改组（即，在精神上移动分区以将其包括在内）。

这是O（n），只需要对随机数生成器进行n-1次调用，这很好。它还会产生真正的随机播放-任何元素，不管其原始位置如何（假设RNG合理），都有1 /
n的机会出现在每个空间中。排序后的版本近似于均匀分布（假设随机数生成器没有两次选择相同的值，如果返回随机双精度数则不太可能），但我发现更容易推断出随机版本：）

这种方法称为Fisher-Yates随机播放。

我认为最好的做法是对这种改组进行一次编码，然后在需要改组项目的任何地方重用它。然后，您不必担心可靠性或复杂性方面的排序实现。仅有几行代码（我不会在JavaScript中尝试！）

将在维基百科的文章值得一读的一般洗牌的差实现的部分，所以你知道，以避免什么（尤其是洗牌的算法部分）有关排序随机投影会谈。