洗牌算法（Shuffling Algorithm）

作者： /

什么是洗牌算法

洗牌算法把序列随机重排，要求每个排列等概率出现（均匀性）、算法本身无偏、且尽量高效。应用：卡牌游戏洗牌、训练数据随机化、抽奖、随机负载分发等。

Fisher-Yates 算法

最经典的洗牌算法，1938 年由 Fisher 和 Yates 提出，后经 Knuth 改进为现代版本：

  1. 从最后一个元素开始向前遍历；
  2. 对当前位置 i，在 [0, i] 中随机选一个下标 j；
  3. 交换位置 i 和 j 的元素；
  4. 重复直到遍历完。

时间复杂度 O(n)，空间 O(1)（原地）。关键：随机范围必须是 [0, i] 而不是 [0, n-1]——如果每次都从整个数组随机，结果不均匀（会引入偏差）。

Go 实现

1. 手写 Fisher-Yates

func FisherYatesShuffle(slice []int) {
    r := rand.New(rand.NewSource(time.Now().UnixNano()))
    for i := len(slice) - 1; i > 0; i-- {
        j := r.Intn(i + 1)
        slice[i], slice[j] = slice[j], slice[i]
    }
}

2. rand.Shuffle（推荐，Go 1.10+）

r := rand.New(rand.NewSource(time.Now().UnixNano()))
r.Shuffle(len(slice), func(i, j int) {
    slice[i], slice[j] = slice[j], slice[i]
})

标准库的 rand.Shuffle 就是 Fisher-Yates 的官方实现，内部直接处理了随机源，优先用它。

3. rand.Perm（生成排列）

如果不打乱已有切片，而是要生成一个 0..n-1 的随机排列，rand.Perm 用的是 “inside-out” 变体，不需要预填充数组：

perm := rand.Perm(10) // 0..9 的一个随机排列

正确性：为什么均匀

用归纳法证明”每个排列等概率”：

  • 基础情形：长度 1，唯一排列概率 1，成立；
  • 归纳假设：长度 k 时所有排列等概率 1/k!；
  • 递推：长度 k+1 时，最后一步从 k+1 个位置等概率选 j 放入最后一个位置（概率 1/(k+1)），剩余 k 个元素按假设均匀排列成 k! 种——于是每种排列概率 = 1/(k+1) × 1/k! = 1/(k+1)!，成立。

如果随机范围写错（取 [0, n-1]），最后一步的等概率论证就被破坏了，排列分布会偏向某些结果——这是面试常问的坑。

工程建议

  • 用 math/rand 记得先 rand.New(rand.NewSource(seed)) 指定随机源；需要密码学安全（抽奖、安全场景）用 crypto/rand；
  • Go 1.20+ 的 math/rand 顶层函数已自动加随机种子，直接 rand.Shuffle 也可以，但明确指定随机源的写法更可控；
  • 对”概率均等”有疑问时，可以用蒙特卡洛验证：洗 1 万次统计每个元素在每个位置出现的次数，应近似均匀。
滚动至顶部