储层采样
水库采样是一种随机算法。在该算法中，从具有n个不同项的列表中选择k个项。
我们可以通过创建一个数组作为大小为k的容器来解决它。然后从主列表中随机选择一个元素，然后将该项目放置在容器列表中。一次选择一项时，下次将不再选择。但是他的方法无效，我们可以通过这种方法增加复杂性。
在存储库列表中，复制列表中的前k个项目，现在从列表中的第（k+1）个数字开始一个接一个地复制，让当前选定的项目位于索引i处。找到一个从0到i的随机索引，并将其存储到j中，如果j在0到k的范围内，则将库[j]与list[i]交换。
输入输出
Input:
The list of integers: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, The value of k = 6
Output:
K-Selected items in the given array: 8 2 7 9 12 6算法
chooseKItems(array, n, k)
输入：数组，数组中的元素数，要选择的元素数。
输出：随机选择k个元素。
Begin
define output array of size [k]
copy k first items from array to output
while i < n, do
j := randomly choose one value from 0 to i
if j < k, then
output[j] := array[i]
increase i by 1
done
display output array
End示例
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void display(int array[], int n) {
for (int i = 0; i < n; i++)
cout << array[i] << " ";
}
void chooseKItems(int array[], int n, int k) { //it will choose k items from the array
int i;
int output[k];
for (i = 0; i < k; i++)
output[i] = array[i];
srand(time(NULL)); //use time function to get different seed value
while(i < n) {
int j = rand() % (i+1); //random index from 0 to i
if (j < k) //copy ith element to jth element in the output array
output[j] = array[i];
i++;
}
cout << "K-Selected items in the given array: ";
display(output, k);
}
int main() {
int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int n = 12;
int k = 6;
chooseKItems(array, n, k);
}输出结果
K-Selected items in the given array: 8 2 7 9 12 6