讲师中心 微信公众号
AI工具推荐 视频效率加速

C++实现洗牌算法算法 _ Fisher-Yates随机乱序原理【实战】

雨枫大大_5257

雨枫大大_5257

发布时间:2026-04-13 19:00:05

|

819人浏览过

|

来源于php中文网

原创

应使用 std::shuffle,它是 Fisher-Yates 的标准实现,要求传入 UniformRandomBitGenerator(如 std::mt19937),避免 rand() % n 的分布不均、线程不安全和不可复现问题。

c++实现洗牌算法算法 _ fisher-yates随机乱序原理【实战】

直接用 std::shuffle,别写手搓循环——它就是 Fisher-Yates 的标准实现,且已规避所有经典陷阱。

std::shuffle 是 Fisher-Yates 的现代封装,不是“可选方案”

你写的所谓“手撸 for 循环 + rand() % size”大概率是错的:分布不均、线程不安全、不可复现。而 std::shuffle 内部正是从后往前迭代、每次在 [0, i] 范围内均匀采样并交换,完全对应 Knuth-Durstenfeld 版 Fisher-Yates。

关键点在于它强制你传入一个 UniformRandomBitGenerator(如 std::mt19937),而不是依赖全局 std::rand()。

  • std::random_shuffle 在 C++17 已被移除,任何还在用它的代码都该立即替换
  • 只传两个迭代器(如 v.begin(), v.end())会编译失败——std::shuffle 没有无参重载
  • 引擎必须显式构造,例如 std::mt19937 g{std::random_device{}()},不能只写 std::mt19937 g(否则种子恒为 0)

常见错误:rand() % n 导致的分布倾斜

现象:打乱 100 张牌,某些排列出现频率明显偏高,尤其当容器大小和 RAND_MAX 不成整除关系时(比如 RAND_MAX == 32767,而 n == 1000)。

立即学习“C++免费学习笔记(深入)”;

C++ Code Review Master
C++ Code Review Master

组合式C++代码评审方案,融合静态分析、AI推理、多轮迭代评审和C++专项检查,适用于PR审查、增量代码审查、全项目评审和代码质量评分,触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

原因:rand() % n 实际把 [0, RAND_MAX] 划分为若干长度为 n 的块,余数部分(RAND_MAX % n)会被“重复映射”,造成前 RAND_MAX % n 个索引概率更高。

  • 用 std::uniform_int_distribution<int>{0, i}(g)</int> 替代 rand() % (i+1),它内部使用拒绝采样,保证严格均匀
  • 不要对 std::list 或 std::forward_list 调用 std::shuffle——它要求随机访问迭代器,否则编译不过
  • 若需复现结果(如测试、回放),固定种子: std::mt19937 g{12345},而非用 std::random_device

原地洗牌的边界条件:i > 0 还是 i >= 0?

标准 Fisher-Yates 从最后一个元素(i = n-1)开始,到第二个元素(i = 1)结束,即循环条件为 i > 0。此时共进行 n-1 次交换,已足够生成全部 n! 种排列。

若写成 i >= 0,最后一次交换是 swap(v[0], v[0]),冗余但无害;但若逻辑误写为 i >= 1,则漏掉第 0 位与自身的“有效”交换机会,破坏等概率性。

  • 正确写法:for (int i = v.size() - 1; i > 0; --i)
  • 错误写法:for (int i = 0; i (这是正向版本,需配合 <code>rand() % (i+1),但容易下标混淆)
  • 更安全的做法:直接用 std::shuffle(v.begin(), v.end(), g),不用自己推导循环范围

真正容易被忽略的是:洗牌算法的“正确”不只看能不能动起来,而在于每种排列出现的概率是否严格相等。这取决于随机源质量、取模/分布方式、以及是否引入隐藏状态——这些细节 std::shuffle 都已封装好,你只需管好种子和引擎类型。

热门AI工具

更多
Loomy
Loomy Hot

一款AI工具,主要用于科大讯飞发布的桌面级 AI 助理,比 OpenClaw 更易用、更安全!,适合需要提升相关任务效率的用户。

二狗PPT
二狗PPT Hot

一款AI演示文稿工具,主要用于专为中式职场打造的AI PPT生成工具,适合需要提升相关任务效率的用户。

讯飞智作

讯飞智作是一款AI视频创作工具,AI文本配音工具,数字人课程、营销视频制作。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

咔片AIPPT

一款在线AI演示文稿制作工具,可根据主题和内容需求辅助生成PPT结构与页面,提高演示材料制作效率。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

切问学术

切问学术是一款AI论文写作工具,复旦大学NLP团队推出的AI学术智能体。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

火山引擎

火山引擎是一款面向企业的云计算与AI服务平台。

相关专题

更多
string转int
string转int

在编程中,我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算,或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

5939

2023.08.02

int占多少字节
int占多少字节

int占4个字节,意味着一个int变量可以存储范围在-2,147,483,648到2,147,483,647之间的整数值,在某些情况下也可能是2个字节或8个字节,int是一种常用的数据类型,用于表示整数,需要根据具体情况选择合适的数据类型,以确保程序的正确性和性能。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2925

2024.08.29

c++怎么把double转成int
c++怎么把double转成int

本专题整合了 c++ double相关教程,阅读专题下面的文章了解更多详细内容。

3708

2025.08.29

C++中int的含义
C++中int的含义

本专题整合了C++中int相关内容,阅读专题下面的文章了解更多详细内容。

2605

2025.08.29

线程和进程的区别
线程和进程的区别

线程和进程的区别:线程是进程的一部分,用于实现并发和并行操作,而线程共享进程的资源,通信更方便快捷,切换开销较小。本专题为大家提供线程和进程区别相关的各种文章、以及下载和课程。

3958

2023.08.10

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

5496

2023.08.14

PixTV官网入口地址合集
PixTV官网入口地址合集

本专题汇总了 PixTV AI 一站式视频创作平台的官方入口与使用教程。无需下载软件,浏览器直接访问即可使用。平台将剧本、图像、视频、声音与剪辑整合在“无限画布”中,接入 GPT Image 2.5、Seedance 2.5 等头部模型。本专题整理了从新建画布、角色锚定、分镜拆分到视频生成与导出的完整操作指南,助你快速上手 AI 短剧与漫剧创作。

20

2026.10.10

Kratos框架HTTP与gRPC服务开发教程
Kratos框架HTTP与gRPC服务开发教程

本专题围绕Kratos框架双协议服务开发,涵盖HTTP路由与处理器编写、参数获取、gRPC服务实现与客户端调用、metadata上下文传递、encoding编解码注册、统一响应封装、超时控制与流式响应实现方法。

20

2026.10.10

Kratos框架Protobuf接口定义与代码生成合集
Kratos框架Protobuf接口定义与代码生成合集

本专题讲解Kratos框架接口定义体系,涵盖proto编写规范、proto add/client/server生成命令、http注解路由、validate校验、OpenAPI文档生成、跨服务proto复用与兼容性设计。

0

2026.10.10

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
C++ Core Guidelines
C++ Core Guidelines

共0课时 | 0人学习

C++ Reference
C++ Reference

共0课时 | 0人学习

C++ 官方标准说明
C++ 官方标准说明

共0课时 | 0人学习

关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn