C++如何使用Fisher-Yates算法打乱数组-C++-PHP中文网

应优先使用 std::shuffle，因其底层即现代 fisher-yates；手动实现仅适用于需精确控制、无 stl 环境或教学场景，且须注意随机引擎配对、循环方向、动态范围及参数传递等关键细节。

c++如何使用fisher-yates算法打乱数组

为什么不能用 `std::shuffle` 就直接写 Fisher-Yates？

多数情况下你真该用 std::shuffle——它底层就是现代 Fisher-Yates（即 Knuth shuffle），且已适配 C++11 及以上标准库的随机数设施。手写容易出错，尤其在边界和随机源上。只有当你需要：明确控制随机过程、嵌入无 STL 环境（如裸机/游戏引擎精简版）、或教学演示时，才值得手动实现。

`std::random_device` 和 `std::mt19937` 必须配对用

常见错误是直接用 rand() 或只用 std::random_device 构造分布——前者不满足均匀性，后者在某些平台（如 MinGW）可能退化为常量。正确做法是：

std::random_device 仅用于生成种子，不直接生成随机数
用该种子初始化 std::mt19937（Mersenne Twister），它才是主力随机引擎
再用 std::uniform_int_distribution 限定范围，避免模偏差（% N 会导致小数字概率略高）

示例关键片段：

std::random_device rd;
std::mt19937 g(rd());
std::uniform_int_distribution<size_t> dist(0, vec.size() - 1);
// 然后在循环中用 dist(g) 获取 [0, size-1] 的均匀索引
</size_t>

手写 Fisher-Yates 循环必须从后往前，且交换范围要动态缩小

核心逻辑是：对位置 i（从 size-1 递减到 1），在 [0, i] 范围内选一个随机索引 j，与 i 交换。若从前往后或固定范围（如总在 [0, size-1] 里选），会破坏均匀性。

C++

"空空如也"

下载

起始索引必须是 vec.size() - 1，终止条件是 i > 0（即至少留一个元素不参与“被选”）
每次随机上限必须是当前 i，不是原数组长度
交换前要检查 j ，虽然分布保证了这点，但调试时加断言更安心

简易实现（适用于 std::vector<int></int>）：

for (size_t i = vec.size() - 1; i > 0; --i) {
    size_t j = dist(g); // 此时 dist 应定义为 uniform_int_distribution<size_t>(0, i)
    std::swap(vec[i], vec[j]);
}
</size_t>

用 `std::shuffle` 时别漏掉第三个参数——URNG 对象

最常被忽略的是传错第三个参数：它要的是一个**可调用的随机数引擎对象**，不是分布，也不是 std::random_device 实例。错误写法：std::shuffle(v.begin(), v.end(), rd) 或 std::shuffle(v.begin(), v.end(), dist)，都会编译失败或行为未定义。

正确传参是 std::shuffle(v.begin(), v.end(), g)，其中 g 是 std::mt19937 实例
如果用 C++17，可直接用 std::shuffle(v.begin(), v.end(), std::random_device{}()) ——但注意这会每次新建引擎，种子可能重复，不推荐用于连续多次打乱
容器为原生数组时，需用指针：std::shuffle(arr, arr + N, g)

真正麻烦的从来不是算法本身，而是随机数引擎的生命周期管理——引擎对象必须比 std::shuffle 调用活得久，且不能在多线程中无保护共享。