怎样手写数组乱序（洗牌）？为什么 sort(() => Math.random()

简答

抽奖页要把候选人顺序打乱，很多人会写 arr.sort(() => Math.random() - 0.5)，看起来每次都不一样，但这样打乱并不均匀，有的顺序出现得多，有的出现得少。

原因是 sort 要求比较函数是一致的：同样两个元素，每次比较结果要相同，a 小于 b 时 b 就要大于 a。随机的比较函数每次都给出不同答案，违反了这个要求，MDN 说这种比较函数没法可靠地排序。排序算法拿到前后矛盾的比较结果，最后的排列会偏向某些顺序，而且具体怎么偏，取决于引擎用的是哪种排序算法。

正确的做法是 Fisher-Yates 洗牌。从数组最后一位开始往前走，每到一个位置 i，就在 0 到 i 之间随机选一个下标 j，交换 i 和 j 两个位置。这样每个元素落到每个位置的机会都一样，所有排列出现的概率相同，而且只遍历一遍，是 O(n)。

要注意，Math.random() 生成的随机数不能用于安全相关的场景。真正涉及奖金、安全的抽奖，应该在服务端做，或者在浏览器里用 crypto.getRandomValues()。

Fisher-Yates 洗牌

JavaScript

function shuffle(items) {
  const result = [...items];
  for (let i = result.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [result[i], result[j]] = [result[j], result[i]];
  }
  return result;
}

function countOrders(shuffleFn, times) {
  const counts = {};
  for (let k = 0; k < times; k++) {
    const key = shuffleFn(['a', 'b', 'c']).join('');
    counts[key] = (counts[key] ?? 0) + 1;
  }
  return counts;
}

const fair = countOrders(shuffle, 60000);
const biased = countOrders((arr) => [...arr].sort(() => Math.random() - 0.5), 60000);
console.log(Object.keys(fair).length); // 6
console.log(Object.values(fair).every((n) => n > 9000 && n < 11000)); // true
console.log(Object.values(biased).every((n) => n > 9000 && n < 11000)); // false

a、b、c 三个元素一共有 6 种排列，打乱 60000 次，理想情况下每种大约出现 10000 次。shuffle 的结果每种都落在 9000 到 11000 之间。随机比较的 sort 却不是：在 Node 22 里实测，abc 约 22500 次、cba 约 18800 次、bac 约 7500 次，acb、bca、cab 各只有约 3700 次，最多和最少差了 6 倍，原本的顺序 abc 出现得最多。

为什么 j 的范围是 0 到 i，包含 i 自己？因为当前元素也可能留在原地，不包含的话，每个元素都被迫离开原位，有些排列就永远不会出现。为什么从后往前？每一轮确定位置 i 上的元素，i 后面的位置都已经定好了，只在前面没处理过的元素里选，每个元素被选中的机会才相等。

这里先复制了一份 result，不修改传入的数组。需要原地打乱时，直接在原数组上交换即可。

为什么随机比较函数会偏

sort 的结果依赖比较函数，规范对比较函数的要求包括：相同的输入总是返回相同的结果；compare(a, b) 和 compare(b, a) 的符号相反。MDN 举例说，只返回 1 和 0、或只返回 0 和 -1 的比较函数破坏了反对称性，没法可靠地排序。随机比较函数连“同样输入同样结果”都做不到。

排序算法会假设比较结果可信，比如“已经确认 a 在 b 前面，就不用再比了”。有了矛盾的结果，有的元素被比较的次数多，有的少，留在原位或被交换的概率就不一样。不同引擎、不同数组长度用的排序策略不同，偏差的方向也不同，没法通过调参修正。

常见追问

怎样随机抽取 k 个不重复的元素？

只做 Fisher-Yates 的前 k 轮，然后取最后 k 个位置的元素，不需要把整个数组都打乱，时间是 O(k)。

需要安全的随机数时怎样生成 0 到 n-1 的整数？

用 crypto.getRandomValues(new Uint32Array(1))[0] 拿到一个随机整数。直接对 n 取余会有轻微偏差，因为 2^32 不一定能被 n 整除；严格的做法是丢弃落在最后不完整区间里的值重新取。

怎样手写数组乱序（洗牌）？为什么 sort(() => Math.random() - 0.5) 不对？

简答

Fisher-Yates 洗牌

为什么随机比较函数会偏

常见追问