Fisher-Yates 洗牌算法（又称 Knuth 洗牌算法）是一种能生成有限序列无偏全排列的高效随机化算法，现代版为原地操作，时间复杂度 O (n)、空间复杂度 O (1)，由 Fisher 和 Yates 于 1938 年提出，经 Durstenfeld 与 Knuth 改进普及。
核心原理与步骤
核心是 “从后向前遍历，当前元素与前序随机位置交换”，确保每个元素到任意位置的概率均为 1/n，所有 n! 种排列等可能。
- 设数组长度为 n，索引从 0 到 n-1。
- 初始化 i = n - 1，向前遍历至 i = 1。
- 对每个 i，生成 [0, i] 内的均匀随机整数 j。
- 交换 arr [i] 与 arr [j]。
- i 减 1，重复至遍历结束。
伪代码
function fisherYatesShuffle(arr): n = arr.length for i from n-1 downto 1: j = random integer in [0, i] swap arr[i] and arr[j] return arr代码实现（Python）
import random def fisher_yates_shuffle(arr): n = len(arr) for i in range(n-1, 0, -1): j = random.randint(0, i) arr[i], arr[j] = arr[j], arr[i] return arr # 示例 if __name__ == "__main__": test_arr = [1, 2, 3, 4, 5] shuffled_arr = fisher_yates_shuffle(test_arr) print("Shuffled array:", shuffled_arr)数学正确性（归纳法简述）
- 基础步：n=1 时，唯一排列，概率 1，成立。
- 归纳步：假设 n=k 时成立，当 n=k+1，第 k+1 个元素被换到位置 i 的概率为 1/(k+1)；前 k 个元素仍保持均匀分布，故整体均匀。最终每个排列概率为 1/(n!)。
关键特性与对比
| 特性 | Fisher-Yates（现代） | 朴素洗牌（如每次全数组随机交换） |
|---|---|---|
| 时间复杂度 | O(n) | O (n)（但概率不均） |
| 空间复杂度 | O (1) | O(1) |
| 无偏性 | 是（所有排列等可能） | 否（概率偏倚） |
| 适用场景 | 数组、列表等可随机访问结构 | 非严谨场景 |
常见误区与注意事项
- 随机数范围错误：若 j 取 [0, n-1] 而非 [0, i]，会导致概率偏倚。
- 伪随机数质量：需使用高质量随机数生成器（如 Python 的 secrets 模块），避免周期过短或分布不均。
- 遍历方向：从后向前是为了原地操作，从前向后也可实现，但需额外空间或调整逻辑。
应用场景
游戏开发：打乱牌组、随机生成敌人位置、随机道具掉落顺序。
数据采样：无放回随机抽样、交叉验证中划分训练 / 测试集。
