为什么搭配Math.random的sort简易数组洗牌算法存在偏差？

为什么sort随机排序的洗牌算法存在偏差 #

• 核心问题出在JS内置sort()方法的实现逻辑上：主流JS引擎采用的TimSort等排序算法，要求比较函数满足一致性规则——即若a应排在b前、b应排在c前，则a必须排在c前。你传入的() => Math.random() - 0.5完全破坏了这个规则，会导致排序过程出现逻辑异常，最终所有可能的排列出现概率不可能均等。
• 你测试的单个元素位置分布只是无偏洗牌的必要条件，而非充分条件。这种偏差在单个元素的位置统计里很难被发现，但如果统计全排列的出现频率就会非常明显：比如长度为3的数组本应6种排列等概率出现，用该算法测试的话，部分排列的出现概率会是其他排列的2~3倍。本质是排序算法的分治逻辑会让元素更大概率留在原位置附近的区间，只是单维度的位置统计刚好掩盖了这种偏差。
• 你可以做个更精准的测试：取长度为10的数组，统计原前两位元素同时出现在数组后半段的概率，无偏算法下这个值应为(5/10)*(4/9)≈22.2%，用该sort洗牌算法跑10万次的结果会明显偏离这个数值。
• 无偏的洗牌方案推荐使用Fisher-Yates算法，参考实现如下：

function shuffle<T>(array: T[]): T[] {
  for (let i = array.length - 1; i > 0; i--) {
    const randomIndex = Math.floor(Math.random() * (i + 1));
    [array[i], array[randomIndex]] = [array[randomIndex], array[i]];
  }
  return array;
}

内容的提问来源于stack exchange，提问作者bahejam379