JavaScript 混排算法解释

Question

我发现改组算法似乎工作正常。

const questions = [
  { name: "Ananda or Nalanda" },
  { name: "Sunny or Rainy" },
  { name: "Facebook or Instagram" },
  { name: "IOS or Android" },
  { name: "Mc or KFC" }
];

questions.sort(() => Math.random() - 0.5)

questions.forEach(e=>{
    console.log(e.name)
})

但我想不出这在语法上是如何工作的。我知道 Math.random() 会生成一个介于 0 和 1 之间的数字。此外，sort 是用于排序的标准函数。但是这两个函数如何洗牌我的数组？为什么要从 Math.random() 中减去 0.5？

Answer 1

.sort 回调的返回值应为正数、0 或负数。因此，从范围为 [0, 1) 的变量中减去 0.5 会导致范围为 [-0.5, 0.5) - 一个在 b 之前随机排序 a 和在 a 之前随机排序 b 的均等分布(其中 a 和 b 是被比较的元素)。这种类型的通过随机确定 a 是在 b 之前还是之后对数组进行随机排序。

如果您不减去 0.5，或者减去 0.5 以外的值，结果将有很大偏差。

但是，这不是随机排序数组的好方法；这里的结果也会有些偏差:

// an array of 'a' to 'f'
const questions = Array.from(
  { length: 6 },
  (_, i) => String.fromCharCode(i + 97)
);

const positionFrequency = {};
for (let i = 0; i < 1e5; i++) {
  const sorted = questions.slice().sort(() => Math.random() - 0.5);
  sorted.forEach((char, i) => {
    if (!positionFrequency[char]) {
      positionFrequency[char] = {};
    }
    positionFrequency[char][i] = (positionFrequency[char][i] || 0) + 1;
  });
}
console.log(positionFrequency);

请运行该代码段 - 它非常有偏见!在 Chrome 中，a 出现在第一个位置的概率约为 28%，尽管它应该出现的概率只有 1/6 (16.667%)。在 Firefox 56 中，它甚至比这更有偏见。

这是因为排序算法不稳定 - 结果取决于首先将哪些元素与其他元素进行比较(这取决于实现)。您可以在此处阅读有关这种随机排序究竟有何偏倚的更多详细信息:

http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html