先说个亲身经历。前两年帮朋友改一个棋牌类小游戏的抽奖逻辑需求本身很简单玩家进房间后把一组牌随机打乱。我第一版偷懒写成了arr.sort(() Math.random() - 0.5)结果上线没一周就有老玩家反馈“某个位置的牌老是重复出现”。从那时起我才真正意识到洗牌不是“看起来乱了就行”它背后是一个有严格概率标准的算法问题——也就是今天要聊的 Fisher-Yates 洗牌算法。这个算法适合所有写随机逻辑的程序员无论是做抽奖活动、游戏卡池还是数据采样甚至只是写面试题掌握它都能少踩很多随机性的坑。这篇就把原理、实现、证明和实战里最容易翻车的点一次讲透。1. 先从一道“看似简单”的洗牌题说起1.1 网上那些洗牌代码为什么总有问题搜索“洗牌算法”最容易看到的一个答案是用排序加随机比较器function shuffle(arr) { return arr.sort(() Math.random() - 0.5); }这段代码在短视频和教程里流传很广因为它写起来短、思路直观排序时候每次比较都扔硬币最后顺序一定很乱。但问题是排序算法对比较器的要求是“稳定且满足传递性”而随机比较器既不稳定也不传递。V8 在排序时用的 TimSort 会利用数组已有的局部有序性做归并这会让比较结果不均等。换句话说随机比较器产生的不是“均匀随机排列”而是一个被排序策略扭曲过的分布。我当年那个棋牌项目出问题根源就在这短数组排序后某些位置出现特定元素的概率远高于理论值玩家当然能察觉。还有一个更隐蔽的坑这种写法会把洗牌变成 O(n log n) 排序复杂度对性能也有不必要的消耗。1.2 公平洗牌到底要满足什么标准“公平”在洗牌问题里有明确数学定义对长度为 n 的数组理论上存在 n! 种排列每种排列出现的概率都应该等于 1 / n!。比如数组[1, 2, 3]一共有 6 种排列每种都应该以约 16.67% 的概率出现。如果某个排列出现 30%、另一个只出现 5%这就是有偏。这听起来像是纸上谈兵但在抽奖、游戏抽卡、公平发牌这些场景里偏差是能直接被用户感知的。轻则偶尔有几个固定模式让人怀疑重则被玩家利用漏洞刷奖品。所以“看起来乱”不是标准“每种排列等概率”才是。这也是 Fisher-Yates 洗牌算法的核心价值它用最少的交换操作把均匀分布这件事从数学上保证下来。1.3 Fisher-Yates 诞生的背景这个算法最早出现在 1938 年 Ronald Fisher 和 Frank Yates 合著的《Statistical Tables for Biological, Agricultural and Medical Research》里当时的场景是统计学实验需要随机排列一组对象而且没有电脑只能用随机数表和纸笔操作。它的原始形式更像“抽签”把 n 个编号写在纸上每次随机选一个未划掉的编号记录下来划掉它然后继续在剩余编号里选。思路在今天依然成立只是用数组实现时我们不需要真的划掉元素而是通过“逐步缩小可选范围 交换”的方式模拟这个过程。真正把它变成现代程序员熟悉的循环交换写法是后来 John Durstenfeld 在 1964 年贡献的改进有时也叫 Fisher-Yates-Durstenfeld 洗牌。聊到实现时我基本默认指现代版本。2. 算法原理两种实现版本与核心代码2.1 原始版本从抽签到在线洗牌原始算法可以理解成从袋子里不重复地摸球摸出来一个就放到新队列末尾。伪代码是这样的准备一个待洗牌数组 A以及一个空结果数组 B。从 A 中剩余元素里随机选一个位置 i。把 A[i] 放到 B 末尾并把 A[i] 从 A 中删除。重复直到 A 为空。这个版本符合直观也保持每一种排列等概率每次从剩余集合里均匀抽取剩几个元素就有几分之一的概率选中某个特定元素。多重集的最终排列概率就是1/n × 1/(n-1) × ... × 1/1 1/n!。但用数组实现时“删除元素”这一步很麻烦。如果用链表删除要维护指针如果用数组删除则需要移动元素每次都是 O(n)整体就退化成了 O(n²)。2.2 现代版原地反向遍历Durstenfeld 的改进思想很简洁既然抽出来的元素放到了结果的末尾不如直接把“抽出来的元素”和“当前范围的最后一个元素”原地交换这样待抽取区域自然缩小也不额外占用空间。经典实现是从末尾向前遍历function shuffle(arr) { for (let i arr.length - 1; i 0; i--) { const j Math.floor(Math.random() * (i 1)); [arr[i], arr[j]] [arr[j], arr[i]]; } }Python 的写法也差不多import random def shuffle(arr): for i in range(len(arr) - 1, 0, -1): j random.randint(0, i) arr[i], arr[j] arr[j], arr[i]C 里更推荐用现代随机库避免直接用rand() % n的模数偏置问题#include random #include vector #include algorithm void shuffle(std::vectorint v) { std::mt19937 rng(std::random_device{}()); for (int i v.size() - 1; i 0; --i) { std::uniform_int_distributionint dist(0, i); std::swap(v[i], v[dist(rng)]); } }2.3 为什么边界是[0, i]循环是i 0我在教学和交流时发现最容易问的就是这两个细节。首先j必须落在[0, i]的闭区间里因为这一步是把第 i 个位置和“当前未处理区域中任意一个元素”交换。如果j i相当于这个元素留在原位这也是一种合法随机结果不能排除它。如果j只在[0, i - 1]里选算法性质就变了这个我后面会专门讲。其次循环为什么到i 1就停而不是i 0因为当 i 1 时只剩两个位置随机范围是[0, 1]交换后相当于决定了最后一个未确定位置。如果继续到 i 0此时Math.random() * 1只能得到 0交换自身没有任何意义。所以i 0作为循环条件既是正确的也是省一次无意义操作的优化。复杂度方面现代版本只遍历 n - 1 次每次只做一次随机数生成和一次交换整体复杂度 O(n)空间复杂度 O(1)这也是它真正成为工业标准的原因。3. 用严格的概率视角证明“公平性”3.1 每种排列都对应唯一的随机序列前面说了公平的标准是每种排列概率都等于 1/n!。现在我们来证明 Fisher-Yates 能达到这个标准。假设数组长度为 n。算法执行步骤如下第 1 步从[0, n-1]中选一个 j让 A[j] 进入位置 n-1。第 2 步从剩余的前 n-1 个位置中选一个 j让 A[j] 进入位置 n-2。... 依次类推。最终得到的完整排列是由每一次的随机选择决定的。不同选择组合会得到不同的排列而且每一种排列 P 都能唯一对应一组随机值。比如[3, 1, 2]这个结果只可能来自第一步选中 3、第二步在剩余元素中选中 1、最后一步只剩 2 这样的随机序列。所以计算 P 出现的概率就是每一步对应随机值出现的概率相乘。第 1 步选中某个特定元素的概率是 1/n第 2 步在剩余 n-1 个元素里选中另一个特定元素的概率是 1/(n-1)依此类推最后一步概率是 1/1。相乘得到1/n × 1/(n-1) × ... × 1/2 × 1 1/n!n! 种排列每种概率都是 1/n!这就完成了公平性证明。整个过程不依赖任何“排序稳定性”或“比较器一致性”只依赖每个随机数生成器本身的均匀性。3.2 用归纳法看“任意元素停在任意位置”还有更直观的验证方式。以元素 x 为例它最终落在位置 1、位置 2、位置 3 ... 的概率分别是多少第 1 轮x 被选到最后一个位置的概率是 1/n。如果没被选中它留在前 n-1 个位置里第 2 轮在剩余 n-1 个元素中它被选中到倒数第二个位置的条件概率是 1/(n-1)。综合来看x 最终落在倒数第二个位置的概率是(1-1/n) × 1/(n-1)。因为1-1/n (n-1)/n乘上 1/(n-1) 等于 1/n。用数学归纳法一路推下去x 落在任意一个位置的概率都是 1/n。这从侧面说明了“每个元素在每个位置出现的概率相等”。不过要强调这个条件只是“均匀排列”的必要条件不是充分条件有些有偏算法也能让每个元素在每个位置等概率但排列整体分布却不均匀。完整的证明还是要回到“每种排列等概率”这一点上也就是 3.1 节的推理过程。3.3 顺带说一句把(i 1)写成i会得到 Sattolo有人喜欢把随机范围写成[0, i - 1]也就是代码里写成const j Math.floor(Math.random() * i);这样得到的不再是 Fisher-Yates而是另一个叫 Sattolo 算法的东西。它只会生成那些“没有任何元素留在原位置”的排列也就是循环排列。n 个元素的循环排列只有(n-1)!种不是 n! 种。如果你本意是普通洗牌写成这样就错了因为部分排列永远不会出现。但在某些特殊需求里比如“打乱后要求每个位置都不能保持原元素”Sattolo 恰好能满足。只是使用时必须清楚自己在做什么否则别人维护你的代码时大概率会把* i当成 bug 改回* (i 1)让你这个“特殊功能”原地失效。我的建议是普通洗牌老老实实用[0, i]真要做“无固定点排列”就用 Fisher-Yates 洗一次再检查有没有元素留在原位置如果有就重新洗通常最多洗几次就能得到合法结果代码意图也更清楚。4. 项目实战文档不会告诉你的坑4.1 随机数模数偏置到底怎么回事很多 C 语言项目会用rand() % n生成[0, n-1]的随机数这在量化、抽奖场景是不能直接用的。假设rand()返回 0 到 RAND_MAX 之间的整数而 RAND_MAX 是 32767那rand() % 6的结果里0、1、2 会比其他数字多出现一次因为 32768 6×5461 2余数 0 和 1 各自多了一个来源。这就是模数偏置。正确做法是拒绝采样只接受落在“最大公约数倍数区间”内的随机数超出部分直接丢弃重取int unbiased_rand(int n) { int limit RAND_MAX - RAND_MAX % n; int r; do { r rand(); } while (r limit); return r % n; }拒绝采样的代价是可能循环多次但r limit的概率很低平均循环次数接近 1 次性能几乎不受影响。相比之下JavaScript 的Math.floor(Math.random() * (i 1))是基于双精度浮点的缩放不存在整数模数的经典问题但在理论上极小极小的精度偏差仍然存在日常业务可以忽略加密场景则不应该用Math.random。4.2 语言自带 shuffle 的可靠性其实很多现代语言的标准库已经内置了正确实现。Java 的Collections.shuffle()、Python 的random.shuffle()、Go 的rand.Shuffle()内部都使用了 Fisher-Yates 思想。能用标准库就优先用标准库它们通常做了随机数边界优化也处理了不同底层随机源的问题。但标准库也有使用门槛Python 的random.shuffle就地修改原列表不返回新列表很多人误以为它返回了一个新对象结果拿到NoneJavaScript 原生没有数组 shuffle 方法第三方库如 lodash 的shuffle则复制数组后洗牌不会修改原数组。这些行为差异不是说谁对谁错而是调用之前必须看清楚契约。4.3 原地修改与复制导致的隐藏 bugFisher-Yates 现代版默认是原地修改这既是它的优点也是隐患。比如你有一个“最近播放列表”想给用户展示随机顺序播放但又不能真的改乱用户的原始播放列表必须先深拷贝。深拷贝也有讲究。数组如果只存基础类型[...arr]就够了如果数组里是对象这个浅拷贝会让新数组里的对象和原数组仍共享引用洗牌后虽然顺序变了但某块业务通过新数组修改了某个对象的字段原数组也一起变了。遇到嵌套结构要自行structuredClone或写递归深拷贝。这个错误在数据结构稍微复杂一点的项目里非常常见。4.4 随机种子与可复现测试测试洗牌函数最头疼的就是“随机”。想做个单元测试断言结果是[3,1,4,2]完全没用因为下次运行就变了。我的做法是给随机源设计一个可注入的种子接口生产代码用真实的加盐随机源测试代码注入固定种子让洗牌结果在测试环境中稳定复现。这样我就能断言“特定种子下输出等于预期数组”既验证了交换逻辑没写错又不会依赖运气。游戏行业还会用种子随机做“回放”。比如卡牌对战里开局洗牌结果由唯一种子决定服务器记录种子和玩家操作即可复现整局过程出现纠纷时回溯非常容易。这背后都是一个朴素的规律洗牌算法本身是确定的不确定的只是随机源。把随机源抽出来你的算法就变得完全可控。5. 怎么验证你的洗牌结果真的“均匀”5.1 用蒙特卡洛做位置频率统计验证一个洗牌实现是否正确最直接的办法是做大数次洗牌后统计分布。用[0, 1, 2, 3]四个元素洗上十万次然后把每个元素出现在每个位置的次数记录下来用 Python 示意from collections import Counter def shuffle(arr): for i in range(len(arr) - 1, 0, -1): j random.randint(0, i) arr[i], arr[j] arr[j], arr[i] n 4 trials 100000 pos Counter() for _ in range(trials): a list(range(n)) shuffle(a) for idx, val in enumerate(a): pos[(val, idx)] 1 for val in range(n): row [pos[(val, idx)] / trials for idx in range(n)] print(val, row)如果算法公平每一行四个值都应该接近 0.25波动幅度在sqrt(0.25 * 0.75 / 100000)也就是约 0.0014 的范围内。如果某一列是 0.3、另一列是 0.12那就说明分布有明显偏置需要回头检查随机范围是否写错了。5.2 “看着随机”不等于正确一个常见误区是凭肉眼判断洗牌结果输出[9, 2, 5, 1, 8]就觉得挺随机。但随机性的判断无法靠单次结果进行只有大量重复后在统计意义上才能暴露问题。比如我前面提到的arr.sort(() Math.random() - 0.5)你单次看也会觉得很乱但卡方检验和频率统计立刻就会露馅。如果想做得严谨一点可以引入卡方检验计算每个位置出现每个元素的期望频次是trials / n再算出实际观测频次和期望值之间的偏差平方和χ² Σ((观察值-期望值)²/期望值)。对 n4 的数组自由度一般是(n-1)²9在 99% 置信区间下卡方值应当小到一定程度。实测时我用过这些指标发现用错误随机比较器洗牌的结果卡方值常常比正常值高出几十倍一百次实验里几乎必然暴露。5.3 抽样验证的快捷方式在正式引入统计框架之前可以先做一个更简单的验证用同一套种子跑固定次数把每次洗牌结果导出到文件再用脚本统计排列出现频率。比如 n3 时总共只有 6 种排列跑 6000 次后每种排列应该接近 1000 次。这个验证成本低、直观适合快速排查“是不是基本逻辑出了问题”。如果一切正常再扩展到 n5、n8观察排列数量爆炸后是否仍能维持均匀。逐步放大规模比一上来就跑大数组要容易定位错误如果 n3 就有问题那基本是随机范围写错了如果 n3 没问题、n4 有问题那可能是边界条件只在特定长度下触发。6. 常见问题速查表与扩展玩法6.1 问题排查速查现象可能原因解决方向洗牌后总有几个排列不出现随机范围写成[0, i-1]误用了 Sattolo改成Math.floor(Math.random() * (i 1))结果不报错但分布严重偏置使用了随机比较器排序洗牌改为 Fisher-Yates 或标准库C 语言实现出现周期性模式rand() % n存在模数偏置用拒绝采样或换std::uniform_int_distribution原数组被意外修改原地洗牌函数修改了传入数组调用前显式拷贝或自己封装复制逻辑同样的代码每次测试结果都不同单测难写随机源不可注入支持种子随机或注入 mock 随机函数使用random.shuffle拿到NonePython 标准库是原地修改用random.sample(arr, len(arr))或自行拷贝洗牌结果在低版本 Android WebView 上表现异常Math.random或 sort 实现差异避免随机比较器改用确定的 Fisher-Yates 实现6.2 洗牌算法还能做无放回采样Fisher-Yates 还有一个容易忽略的用途从 n 个元素里随机抽取 k 个不重复元素。做法是只执行循环前 k 步取出数组末尾的 k 个元素。比如从一个 1000 人的奖池里抽 10 个中奖者function sample(arr, k) { const result [...arr]; for (let i result.length - 1; i result.length - k; i--) { const j Math.floor(Math.random() * (i 1)); [result[i], result[j]] [result[j], result[i]]; } return result.slice(-k); }这个操作在数学上等同于无放回抽样每个人被抽中的概率保持一致。我在做活动抽奖时经常用这个变体与其把 1000 个人的数组完整洗一遍再取前 10 个不如只洗 10 步性能更好代码也更符合“抽奖”这个语义。6.3 一点个人体会最后再说个技巧当你把洗牌算法封装成公共工具时尽量设计成“不修改输入 支持种子随机源”的形式。输入不被修改能避免业务层意外污染数据种子随机源能让你在出问题时稳定复现。这两个接口看起来只是小设计实际维护时能省非常多事。Fisher-Yates 本身只有几行代码但它周围的随机源选择、边界处理、拷贝策略才是真实项目中真正体现功力的地方。把这些细节都照顾到才算真正把经典算法用到位。