std::shuffle不适合采样场景，因其时间复杂度o(n)且需原地修改或拷贝，当k≪n时冗余工作多；而std::sample专为高效无放回采样设计，支持o(k)级优化、不改原数组、等概率且无需额外空间。
为什么 std::shuffle 不适合「采样」场景
直接打乱整个数组再取前 k 个，时间复杂度是 O(n)，空间上还要原地修改或拷贝——但你往往只需要 k ≪ n 个样本。这时候 std::shuffle 做了大量冗余工作，尤其是当 n 是百万级、而 k 只有几十时，效率明显偏低。
真正高效的采样应满足：只访问 O(k) 个元素、不修改原数组、支持无放回（默认）或有放回（显式控制）。
- 用
std::shuffle+std::vector::begin()截取，适合k接近n的情况；否则浪费 - 若数组不可随机访问（比如链表），则需 Reservoir Sampling；但题干明确是「数组」，可利用索引优势
- 注意
std::random_device和std::mt19937的初始化开销，别在循环里反复构造
用 std::sample（C++17 起）最简实现
std::sample 是标准库专为该问题设计的算法，底层采用「带拒绝的 Fisher-Yates 变种」或「蓄水池优化路径」，对小 k 自动启用更高效策略。
它要求输入迭代器支持随机访问（数组天然满足），输出到指定容器，且默认无放回、等概率。
#include <algorithm>
#include <random>
#include <vector><p>std::vector<int> arr = {1,2,3,4,5,6,7,8,9,10};
std::vector<int> samples(3);
std::random_device rd;
std::mt19937 g(rd());
std::sample(arr.begin(), arr.end(), samples.begin(), samples.size(), g);
// samples 现在包含 3 个等概率、无放回的随机元素
</int></int></p></vector></random></algorithm>
- 输出容器必须提前分配好空间（
samples.size()），否则行为未定义 - 第三个参数是输出迭代器起点，不是容器本身；写成
samples.begin()，别传samples - 若需有放回采样，不能用
std::sample，得换std::uniform_int_distribution配合索引生成
手动实现：有放回采样比无放回更轻量
有放回只需独立生成 k 次 [0, n) 区间内的随机索引，连交换都不用，O(k) 时间 + 零额外空间（除结果外）。
关键点在于分布对象复用和索引边界——别用 % n，它会引入偏差（尤其当 max() % n != 0）。
std::vector<int> arr = {/* ... */};
std::vector<int> samples(k);
std::random_device rd;
std::mt19937 g(rd());
std::uniform_int_distribution<size_t> dist(0, arr.size() - 1);
for (auto& s : samples) {
s = arr[dist(g)];
}
</size_t></int></int>
-
std::uniform_int_distribution构造时传入闭区间[a,b]，不是半开区间 - 若
arr.size() == 0，dist构造会抛std::invalid_argument，务必前置检查 - 不要在循环内重复构造
dist或g，这是常见性能陷阱
当 k 接近 n 时，退化策略要明确
如果 k > n/2，无放回采样用「标记已选索引」或「生成补集再取反」可能更快。但 std::sample 内部通常已做此判断，无需手动干预。
真正要注意的是边界条件：当 k >= n 时，std::sample 会复制全部元素（符合语义），但若业务逻辑本意是「最多取 k 个」，就得自己截断：
const size_t actual_k = std::min(k, arr.size()); samples.resize(actual_k); std::sample(arr.begin(), arr.end(), samples.begin(), actual_k, g);
-
std::sample不保证输出顺序与原数组一致，也不保证有序；如需升序，采样后单独std::sort - 多线程环境下，每个线程应持有独立的
std::mt19937实例，别共享引擎 - 调试时若发现采样结果总相同，大概率是
std::random_device被误用为伪随机（某些平台回退到常量），可改用rd() ^ (rd() 提高熵
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
