Fisher-Yates 洗牌算法：为什么随机排序不能只用随机数？

你按下"随机排序"，结果真的够随机吗？大多数人以为，只要调用随机数函数就能得到公平的随机排列。但事实上，错误的实现方式会让某些排列出现的概率远高于其他排列，造成隐性偏差。本文从原理出发，解析正确的随机洗牌算法——Fisher-Yates Shuffle。

1. 什么是"公平的随机排列"？

假设有 3 个元素 [A, B, C]，全部可能的排列有 3! = 6 种：

ABC  ACB  BAC  BCA  CAB  CBA

"公平的随机排列"意味着每一种排列被选中的概率都是 1/6 ≈ 16.67%，不偏向任何特定顺序。如果某种实现让 ABC 出现概率变成 20%，其他排列只有 16%，这就是有偏差的随机——即使表面上"看起来很乱"。

2. 直觉做法的陷阱：Sort + Math.random()

许多开发者写过这样的代码（以 JavaScript 为例）：

// 常见但有偏差的做法
array.sort(() => Math.random() - 0.5);

这个做法看起来合理，但实际上有严重的偏差问题。原因在于：

排序算法假设比较结果是一致的：快速排序、归并排序等算法在排序过程中会多次比较同两个元素，预期"A > B"的结果在每次比较时应一致。但随机比较函数每次调用都可能翻转，导致算法走入非预期路径。
数学上无法保证均匀分布：比较排序的时间复杂度是 O(n log n)，代表它只做了 n log n 次比较。对于 n 个元素，可能的排列有 n! 种。当 n! 远大于比较次数能区分的状态时，某些排列必然被"合并"，出现概率不均。

统计验证

对 [1,2,3] 用 sort+random 跑 100 万次，你会发现某些排列出现约 20%，而非均等的 16.67%。偏差虽然不大，但在需要公平性的抽签场合不可接受。

3. Fisher-Yates 算法的原理

Fisher-Yates Shuffle（现代版本又称 Knuth Shuffle）由 Ronald Fisher 和 Frank Yates 于 1938 年提出，Donald Knuth 在《计算机程序设计艺术》中推广了其现代变体。

算法步骤（以 n 个元素的数组为例）：

从最后一个元素（索引 n-1）开始，向前遍历到索引 1。
对于当前索引 i，在 [0, i]（含两端）范围内随机选一个索引 j。
交换 array[i] 与 array[j]。
继续处理索引 i-1，直到 i = 1 为止。

// Fisher-Yates Shuffle（JavaScript 正确实现）
function shuffle(array) {
    const a = [...array]; // 不修改原数组
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], a[i]]; // 交换
    }
    return a;
}

4. 为什么 Fisher-Yates 能保证均匀分布？

以 3 个元素 [A, B, C] 为例，逐步分析概率：

步骤	操作	概率
i=2	从 [0,1,2] 选 j，决定第 3 个位置的元素	各 1/3
i=1	从 [0,1] 选 j，决定第 2 个位置的元素	各 1/2
i=0	第 1 个位置固定为剩余元素	1

每种完整排列的概率：

P(任意特定排列) = 1/3 × 1/2 × 1 = 1/6

数学上完全均匀！对于 n 个元素，每种排列出现概率精确为 1/n!，前提是随机数函数本身是均匀分布的。

5. 正确随机数的重要性

Fisher-Yates 算法的公平性建立在"随机数函数均匀分布"的假设上。不同环境的随机数品质差异很大：

环境	函数	适用场合
JavaScript（浏览器）	`Math.random()`	一般抽签、游戏（非密码学用途）
JavaScript（需高品质）	`crypto.getRandomValues()`	安全抽签、彩票系统
Python	`random.shuffle()`	一般用途（已内置 Fisher-Yates）
Python（安全）	`secrets.SystemRandom().shuffle()`	需要密码学强度的场合
PHP	`shuffle()`	一般用途

6. 分组的实现：从洗牌到分配

"随机分组"其实是"随机排序 + 均匀分配"两个步骤的组合：

function randomGroup(names, groupCount) {
    const shuffled = shuffle(names);      // 第一步：Fisher-Yates 洗牌
    const groups = Array.from({ length: groupCount }, () => []);
    shuffled.forEach((name, i) => {
        groups[i % groupCount].push(name); // 第二步：轮流分配到各组
    });
    return groups;
}

轮流分配（i % groupCount）确保各组人数差距最多 1 人。若 10 人分 3 组，结果会是 4、3、3 人，而非 4、4、2 这种更不均匀的情况。

7. 常见误区总结

误区	问题	正确做法
array.sort(() => Math.random() - 0.5)	统计上有偏差	使用 Fisher-Yates
每次给元素一个随机数再排序	理论上正确但效率低	直接用 Fisher-Yates（O(n) vs O(n log n)）
只选前 n 个随机元素	不是完整洗牌	Fisher-Yates 的前 n 步即为"无放回抽样"
在同一位置"原地随机交换"多次	某些位置被交换概率更高	每个位置只交换一次

延伸应用

Fisher-Yates 的前 k 步就是"从 n 个元素中无放回随机抽取 k 个"的最佳算法，时间复杂度 O(k)，不需要对整个数组完整洗牌。在抽奖、随机抽题等场合非常有用。

8. 小结

随机排序看似简单，但"看起来很乱"和"统计上均匀"是两回事。Fisher-Yates 算法以 O(n) 的时间复杂度、精确的数学保证，成为业界标准的洗牌做法。无论是班级分组、活动抽签还是游戏发牌，使用正确的算法才能确保每个人机会均等。

想直接体验随机分组效果，可以使用本站的名单分组工具，输入名单后即可随机排序或分组，结果可直接复制使用。