洗牌算法（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

import "math/rand/v2"

func FisherYatesShuffle[T any](slice []T) {
    for i := len(slice) - 1; i > 0; i-- {
        j := rand.IntN(i + 1)
        slice[i], slice[j] = slice[j], slice[i]
    }
}

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

rand.Shuffle(len(slice), func(i, j int) {
    slice[i], slice[j] = slice[j], slice[i]
})

标准库的 rand.Shuffle 就是 Fisher-Yates 的官方实现，内部直接处理随机源，优先用它。Go 1.22+ 的 math/rand/v2 顶层函数自动播种，无需再手动创建随机源。

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/v2（Go 1.22+）：顶层函数自动播种，直接用 rand.Shuffle / rand.IntN；
• 需要密码学安全（抽奖、安全场景）用 crypto/rand 或基于它的洗牌实现；
• 对”概率均等”有疑问时用蒙特卡洛验证：洗 1 万次统计每个元素在每个位置出现的次数，应近似均匀；
• 老代码里的 rand.New(rand.NewSource(time.Now().UnixNano())) 写法在 v1 中仍可用，但没必要再手写随机源。