核心要点

  • 从后往前遍历 i 从 n-1 到 1，取 j = randint(0, i)（含两端），交换 a[i] 与 a[j]。

  • 每一步从「尚未定位」的前缀中等概率挑一个放到位置 i。

  • 正确性：每种排列出现概率恰为 1/n!，时间 O(n)、原地无额外空间。

  • 关键：j 的范围必须是 [0, i]（含 i），不能是 [0, n-1]。

标准回答

Fisher-Yates（又称 Knuth Shuffle）原地生成均匀随机排列。从数组末尾开始：对 i = n-1, n-2, ..., 1，从区间 [0, i]（闭区间，包含 i 本身）中等概率选一个下标 j，交换 a[i] 与 a[j]。这样位置 i 就被「定下来」，之后不再改动；下一轮在更短的前缀 [0, i-1] 上重复。

正确性证明：某元素最终落在最后一格（位置 n-1）的概率是 1/n；在它没被选到的前提下落到位置 n-2 的概率是 (1-1/n)·(1/(n-1)) = 1/n；以此类推，任一元素落到任一位置的概率都是 1/n，且各位置独立地构成一个排列，于是每个具体排列出现的概率为 1/n × 1/(n-1) × ... × 1 = 1/n!，即严格均匀。

时间复杂度 O(n)，空间 O(1) 原地完成。下方代码给出标准实现并附频率验证。

python
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

常见误区

⚠️ 常见踩坑

错误写法是每轮都用 j = randint(0, n-1)（固定全范围），这会产生 n^n 种等概率路径，无法被 n! 整除，导致某些排列偏多——是经典的洗牌偏置 bug。j 上界必须随 i 收缩到当前位置。

追问

追问 1：为什么 j 的上界必须是 i 而不是 n-1？

因为只有 [0,i] 范围内各 i+1 个选择等概率，才能让总路径数恰为 n!，每种排列对应唯一一条路径。若用 [0,n-1]，路径总数 n^n 不被 n! 整除，必然有排列出现概率偏高（如 n=3 时某些排列概率 4/27、某些 5/27）。

追问 2：如何在数据流/未知长度下做洗牌（inside-out 变体）？

用 inside-out 算法：遍历输入第 i 个元素时，j=randint(0,i)，令 out[i]=out[j]，out[j]=输入[i]。它不需要预先知道 n，可边读边构造，同样保证 1/n! 均匀，且不修改原数组。

延伸学习

与本题相关的知识库文章、术语、工具与行业资讯。

📖 术语表

🎯 相关面试题