01

60 秒回答模板

洗牌算法最标准的回答是 Fisher-Yates。假设数组长度为 n，从 i = n - 1 遍历到 1，每次在 [0, i] 中均匀随机选 j，然后交换 a[i] 和 a[j]。这样第 i 个位置会从尚未固定的 i+1 个元素中均匀选出一个，递归到前面位置，最终每个排列概率都是 1/n!。复杂度 O(n)，原地 O(1)。要强调随机数必须均匀，不能用 sort(() => random - 0.5)，也要避免取模偏差。

考点 Fisher-Yates
难度 真实面经题
回答目标 讲清方法、边界和追问
02

深入解析

01

定义公平性

公平洗牌不是看起来乱，而是 n 个元素的 n! 种排列出现概率相等。面试中要先说清这个目标，否则容易写出有偏算法。

02

从未固定区间抽样

Fisher-Yates 每轮把位置 i 固定下来，从下标 0 到 i 的未固定元素中均匀随机选择一个与它交换，之后不再修改 i 位置。

03

证明概率均匀

最后一个位置选中任一元素概率是 1/n，倒数第二个位置在剩余元素中概率是 1/(n-1)，依此类推，任意排列概率都是这些概率乘积。

04

复杂度和实现

算法只需要一次线性遍历和常数额外空间，适合数组原地打乱。实现时要注意随机区间是闭区间 [0, i]，包含当前位置。

05

随机源质量

如果用于安全场景，普通伪随机数不够，需要密码学安全随机源；如果用随机整数取模，也要注意随机源范围不是倍数时的取模偏差。

javascript

Fisher-Yates 原地洗牌

function shuffle(items, random = Math.random) {
  const arr = [...items];
  for (let i = arr.length - 1; i > 0; i -= 1) {
    const j = Math.floor(random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}
  • `j` 必须从未固定区间 `[0, i]` 中等概率选择，包含 `i`。
  • 如果面试要求原地修改，可直接在输入数组上交换，不需要复制。
03

易错点

  • 不要把数组随机 sort 当作公平洗牌。
  • 不要每轮都从整个数组随机交换，否则排列概率会不均匀。
  • 不要忽略随机数闭区间边界，漏掉 i 会让元素不能留在原位。
04

面试官追问

为什么不能用随机排序比较器？

排序算法期望比较器满足传递性，随机比较会破坏排序假设，结果分布也不均匀。

为什么 j 的范围要包含 i？

当前位置也可能保持原元素不变，包含 i 才能保证所有排列都有正确概率。

安全抽奖场景要注意什么？

要使用密码学安全随机源、记录可审计种子或过程，并避免可预测的伪随机实现。