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是要排序的标准函数。但是，这两个函数如何使我的数组混乱？为什么要从中减去0.5 Math.random()？

Answer 1

.sort回调的返回值应为正数，0或负数。因此，0.5从具有一定范围[0, 1)结果的变量中减去将导致[-0.5, 0.5)-相等分布的随机排序a之前b和b之前排序a（其中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尽管它应该只在该位置的1/6（16.667％）位置出现，但它大约在28％的时间出现在第一位置。在Firefox 56中，它的偏见甚至更大。

这是因为排序算法不稳定 -结果取决于首先将哪些元素与哪些其他元素进行比较（这取决于实现）。您可以在此处阅读有关这种随机排序的准确度的更多详细信息：

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