核心要点
从后往前遍历 i 从 n-1 到 1，取 j = randint(0, i)（含两端），交换 a[i] 与 a[j]。
每一步从「尚未定位」的前缀中等概率挑一个放到位置 i。
正确性：每种排列出现概率恰为 1/n!，时间 O(n)、原地无额外空间。
关键：j 的范围必须是 [0, i]（含 i），不能是 [0, n-1]。
标准回答
一、先把结论讲清楚
可以先说实现思路：从后往前洗，每一轮把当前位置和 [0,i] 里的随机位置交换。
一、算法怎么写？
从 i = n-1 开始往前走。每一步在闭区间 [0, i] 里随机选一个 j，然后交换 a[i] 和 a[j]。交换完之后，位置 i 就算定下来了，后面不会再动它。
二、拆开机制和判断点
二、为什么这样是均匀的？
最后一个位置有 n 个候选，每个元素被放到最后的概率都是 1/n；倒数第二个位置在剩下 n-1 个元素里选，每个概率是 1/(n-1)。一直乘下去，一个具体排列出现的概率就是 1/n!。
**三、复杂度和关键边界。
三、补上例子、边界和取舍
**
这个算法是原地的，时间 O(n)，额外空间 O(1)。最容易写错的地方是随机范围：j 必须从 [0,i] 里选，不能每次都从 [0,n-1] 里选，否则排列会有偏。
面试里如果出现公式，建议先说 用 Fisher-Yates 实现均匀随机洗牌 解决的直觉问题，再解释变量含义和适用条件。最后补一个反例或边界，比如样本量不足、分布假设不成立、数值不稳定时应该怎么处理。
import random
def fisher_yates(a):
"""原地均匀洗牌：每种排列概率严格 1/n!"""
n = len(a)
for i in range(n - 1, 0, -1): # 从后往前 i = n-1 .. 1
j = random.randint(0, i) # j 在闭区间 [0, i]
a[i], a[j] = a[j], a[i] # 交换
return a
if __name__ == '__main__':
# 频率验证：n=3 共 6 种排列，应各约 1/6
from collections import Counter
cnt = Counter()
for _ in range(600000):
cnt[tuple(fisher_yates([0, 1, 2]))] += 1
for perm, c in sorted(cnt.items()):
print(perm, round(c / 600000, 3)) # 应都 ≈ 0.167
常见误区
⚠️ 常见踩坑
误区一：每轮都在 [0,n-1] 里随机。 这会让某些排列路径更多，最终不是均匀洗牌。
误区二：把 [0,i] 写成 [0,i)。 这样当前位置不能和自己交换，也会破坏均匀性。
追问
追问 1：为什么 j 的上界必须是 i 而不是 n-1？
因为当前只应该从“还没定下来的元素”里选一个放到位置 i。用 [0,i] 时，每轮选择数正好是 n、n-1、...、1，乘起来是 n! 条等概率路径，刚好对应所有排列。
追问 2：如何在数据流/未知长度下做洗牌（inside-out 变体）？
可以用 inside-out：遍历第 i 个元素时，随机 j∈[0,i]，令 out[i]=out[j]，out[j]=当前元素。它的好处是 不用修改原数组，也可以边读边构造随机排列。
🔗 相似问题
同一考点的不同问法，换着练更稳
延伸学习
按主题分类的相关资源，便于系统复习