洗牌算法

问题描述

从n个元素中选出m个

Fisher-Yates Shuffle

假设待选元素数组N， 此算法核心思想为每次选一个，然后把此元素从数组删除。

Knuth-Durstenfeld Shuffle

是方法一的改进，由于方法一删除通常会伴随内存从新分配或者元素重新排列或者辅助空间，因此方法二将删除改为每次选一个之后，跟最后面的元素交换，然后减少选的范围。

Inside-Out Algorithm

由于方法二需要额外的空间存储整个元素数组，此方法改进为遍历数组然后每次将i元素跟0~i元素交换。

如果知道arr的lengh的话，可以改为for循环，由于是从前往后遍历，所以可以应对arr[]数目未知的情况，或者arr[]是一个动态增加的情况。

蓄水池抽样

void Reservoir_Sampling(vector<int>& arr)
{
	int k;
	for (int i = m; i < arr.size(); ++ i)
	{
		srand((unsigned)time(NULL));
		k = rand() % (i + 1);
		if (k < M)
			swap(arr[k], arr[i]); 
	}
}

从伪代码很容易理解，就是从第m个元素开始，以（i + 1)为界生成随机数，如果随机数小于m,则交换两个元素。