蓄水池抽样算法 & 随机洗牌算法

蓄水池抽样算法

蓄水池抽样算法随机算法的一种，用来从 N 个样本中随机选择 K 个样本，其中 N 非常大（以至于 N 个样本不能同时放入内存）或者 N 是一个未知数。其时间复杂度为 O(N),包含下列步骤 (假设有一维数组 S, 长度未知，需要从中随机选择 k 个元素, 数组下标从 1 开始), 伪代码如下:蓄水池抽样算法随机算法的一种，用来从 N 个样本中随机选择 K 个样本，其中 N 非常