C++17起推荐用std::sample实现无放回随机抽样，时间复杂度O(n)、空间O(k)，不修改原容器；需用合法随机引擎、预留输出空间，并校验k≤n。
std::sample 是 C++17 起最直接的解法
如果你用的是 C++17 或更新标准，std::sample 就是专为此设计的标准库函数，无需手写洗牌或维护额外容器。它在时间复杂度 O(n)、空间 O(k) 下完成无放回随机抽样，且不修改原容器。
常见错误是误用 std::random_shuffle（已弃用）或对整个数组调用 std::shuffle 后取前 k 个——当 n 很大而 k 很小时，这浪费大量随机数和交换操作。
实操建议：
- 确保传入合法的随机数引擎，比如
std::mt19937{std::random_device{}()}，别用std::default_random_engine（默认种子固定，多次运行结果相同） - 输入迭代器范围必须满足
ForwardIterator，std::vector和原生数组指针都满足；但std::list也行，只是性能略低 - 输出容器（如
std::vector<int>）必须预留足够空间（out.reserve(k)），否则反复 realloc 会拖慢速度 - 若抽样数量 k > n，
std::sample会复制全部 n 个元素，不会报错也不会截断——需提前校验
std::vector<int> data = {1,2,3,4,5,6,7,8,9,10};
std::vector<int> samples;
samples.reserve(3);
std::sample(data.begin(), data.end(),
samples.begin(), 3,
std::mt19937{std::random_device{}()});
// samples 现在包含 3 个随机不重复元素小数据量时用 Fisher-Yates + 截断更省事
当数组很小（比如 n std::sample 更直观、更容易调试。
立即学习“C++免费学习笔记（深入）”；
核心是只执行 k 次交换：第 i 步从 [i, n-1] 中随机选一个索引 j，交换 arr[i] 和 arr[j]。这样前 k 个就是样本，其余部分无需处理。
容易踩的坑：
- 循环上限写成
i < k，但忘了初始化随机引擎——每次运行结果一样 - 用
rand() % (n - i)代替均匀分布的std::uniform_int_distribution<int>(i, n-1)，导致低位偏差（尤其当 n 不是 2 的幂时） - 误把索引范围写成
[0, n-i)，实际应为[i, n-1]，否则会重复抽到前面元素
std::vector<int> arr = {1,2,3,4,5};
std::mt19937 g{std::random_device{}()};
for (int i = 0; i < 2 && i < arr.size(); ++i) {
std::uniform_int_distribution<int> d(i, arr.size()-1);
int j = d(g);
std::swap(arr[i], arr[j]);
}
// arr[0] 和 arr[1] 就是两个随机样本大数据流场景下用 Reservoir Sampling（蓄水池算法）
当你无法一次性加载全部数据（比如从文件逐行读、网络流、传感器实时数据），且只允许单次遍历，std::sample 无法使用——这时必须上蓄水池算法。
它保证每个元素被选中的概率严格为 k/n，即使 n 未知。内存只用 O(k)，时间 O(n)。
关键细节：
- 前 k 个元素无条件入池；从第 k+1 个开始，对第 i 个元素以概率 k/i 决定是否替换池中某个随机位置
- 替换时务必用
std::uniform_int_distribution<int>(0, k-1)，不能用rand() % k（模偏差） - 如果 k=1，可简化为“遇到第 i 个元素时，以 1/i 概率替换当前样本”，代码更短但逻辑不变
- 该算法天生支持无限流，但要注意浮点精度问题：当 i 极大时，
k/(double)i可能下溢为 0，应改用整数比较（生成 [1,i] 随机数 ≤ k）
std::vector<int> reservoir(3);
int i = 0;
for (int x : data_stream) {
if (i < 3) {
reservoir[i] = x;
} else {
std::uniform_int_distribution<int> d(1, i+1);
if (d(g) <= 3) { // 等价于概率 3/(i+1)
reservoir[d(g) % 3] = x;
}
}
++i;
}性能与兼容性取舍点
不是所有场景都适合同一套方案。C++17 的 std::sample 最稳妥，但 MSVC 2015/2017 对它的实现有 bug（抽样结果可能不均），GCC 7.1+ 和 Clang 6.0+ 支持良好。
若需跨平台兼容旧编译器，Fisher-Yates 截断版更可靠；若数据源是流式且内存受限，蓄水池没有替代方案。
真正容易被忽略的是随机数引擎的生命周期和线程安全：别在循环里反复构造 std::mt19937，也别多个线程共用同一个引擎实例——后者会导致抽样结果相关性升高，看似随机实则偏倚。
