Fisher-Yates 洗牌算法

定义

Fisher-Yates 洗牌算法用于把序列随机打乱,使每一种排列出现的概率相等。它源自统计学家 Ronald Fisher 与 Frank Yates 1938 年的手工方法,现代 O(n) 版本由 Richard Durstenfeld 于 1964 年给出,并因 Knuth 的著作而广为人知。

原理

从最后一个元素开始向前遍历,处理位置 i 时,在 [0, i] 范围内等概率取随机下标 j,交换第 i 与第 j 个元素。归纳可证每个元素落在每个位置的概率均为 1/n。整个过程原地完成,时间 O(n)。

常见错误

随机范围写成全长 [0, n-1] 会导致 nⁿ 种等概率路径映射到 n! 种排列上,产生系统性偏差;用"随机数作比较器排序"打乱同样有偏,历史上曾引发浏览器抽签不公平的知名案例。

应用

抽奖、卡牌游戏发牌、随机抽样、机器学习训练数据打乱等。