最早提出这个洗牌方法的是 Ronald A. Fisher 和 Frank Yates，即 Fisher–Yates Shuffle，其基本思想就是从原始数组中随机取一个之前没取过的数字到新的数组中，具体如下：

        1. 初始化原始数组和新数组，原始数组长度为n(已知)；

        2. 从还没处理的数组（假如还剩k个）中，随机产生一个[0, k)之间的数字p（假设数组从0开始）；

        3. 从剩下的k个数中把第p个数取出；

        4. 重复步骤2和3直到数字全部取完；

        5. 从步骤3取出的数字序列便是一个打乱了的数列。

        下面证明其随机性，即每个元素被放置在新数组中的第i个位置是1/n（假设数组大小是n）。

        证明：一个元素m被放入第i个位置的概率P = 前i-1个位置选择元素时没有选中m的概率 * 第i个位置选中m的概率，即

#define N 10
#define M 5
void Fisher_Yates_Shuffle(vector<int>& arr,vector<int>& res)
{
     srand((unsigned)time(NULL));
     int k;
     for (int i=0;i<M;++i)
     {
     	k=rand()%arr.size();
     	res.push_back(arr[k]);
     	arr.erase(arr.begin()+k);
     }
}

       
时间复杂度为O(n*n),空间复杂度为O(n).

    2.2 Knuth-Durstenfeld Shuffle  

对于arr[i],洗牌后在第n-1个位置的概率是1/n（第一次交换的随机数为i）

在n-2个位置概率是[(n-1)/n] * [1/(n-1)] = 1/n，（第一次交换的随机数不为i，第二次为arr[i]所在的位置（注意，若i=n-1，第一交换arr[n-1]会被换到一个随机的位置））

在第n-k个位置的概率是[(n-1)/n] * [(n-2)/(n-1)] *…* [(n-k+1)/(n-k+2)] *[1/(n-k+1)] = 1/n

（第一个随机数不要为i，第二次不为arr[i]所在的位置(随着交换有可能会变)……第n-k次为arr[i]所在的位置）.

        Inside-Out Algorithm 算法的基本思思是从前向后扫描数据，把位置i的数据随机插入到前i个（包括第i个）位置中（假设为k），这个操作是在新数组中进行，然后把原始数据中位置k的数字替换新数组位置i的数字。其实效果相当于新数组中位置k和位置i的数字进行交互。

       如果知道arr的lengh的话，可以改为for循环，由于是从前往后遍历，所以可以应对arr[]数目未知的情况，或者arr[]是一个动态增加的情况。
证明如下：
原数组的第 i 个元素（随机到的数）在新数组的前 i 个位置的概率都是：(1/i) * [i/(i+1)] * [(i+1)/(i+2)] *…* [(n-1)/n] = 1/n，（即第i次刚好随机放到了该位置，在后面的n-i 次选择中该数字不被选中）。
原数组的第 i 个元素（随机到的数）在新数组的 i+1 （包括i + 1）以后的位置（假设是第k个位置）的概率是：(1/k) * [k/(k+1)] * [(k+1)/(k+2)] *…* [(n-1)/n] = 1/n（即第k次刚好随机放到了该位置，在后面的n-k次选择中该数字不被选中）。         

void Inside_Out_Shuffle(const vector<int>&arr,vector<int>& res)
{
	res.assign(arr.size(),0);
	copy(arr.begin(),arr.end(),res.begin());
	int k;
	for (int i=0;i<arr.size();++i)
	{
		srand((unsigned)time(NULL));
		k=rand()%(i+1);
		res[i]=res[k];
		res[k]=arr[i];
	}
} 

    时间复杂度为O(n),空间复杂度为O(n). 

     2.4 蓄水池抽样

Init : a reservoir with the size： k  
        for    i= k+1 to N  
            M=random(1, i);  
            if( M < k)  
                 SWAP the Mth value and ith value  
       end for 

proof：

每次都是以 k/i 的概率来选择 
例: k=1000的话， 从1001开始作选择，1001被选中的概率是1000/1001，1002被选中的概率是1000/1002，与我们直觉是相符的。 
接下来证明： 
假设当前是i+1, 按照我们的规定，i+1这个元素被选中的概率是k/i+1，也即第 i+1 这个元素在蓄水池中出现的概率是k/i+1 
此时考虑前i个元素，如果前i个元素出现在蓄水池中的概率都是k/i+1的话，说明我们的算法是没有问题的。 

对这个问题可以用归纳法来证明：k < i <=N 
1.当i=k+1的时候，蓄水池的容量为k，第k+1个元素被选择的概率明显为k/(k+1), 此时前k个元素出现在蓄水池的概率为 k/(k+1), 很明显结论成立。 
2.假设当 j=i 的时候结论成立，此时以 k/i 的概率来选择第i个元素，前i-1个元素出现在蓄水池的概率都为k/i。 
证明当j=i+1的情况： 
即需要证明当以 k/i+1 的概率来选择第i+1个元素的时候，此时任一前i个元素出现在蓄水池的概率都为k/(i+1). 
前i个元素出现在蓄水池的概率有2部分组成, ①在第i+1次选择前得出现在蓄水池中，②得保证第i+1次选择的时候不被替换掉 
①.由2知道在第i+1次选择前，任一前i个元素出现在蓄水池的概率都为k/i 
②.考虑被替换的概率： 
首先要被替换得第 i+1 个元素被选中(不然不用替换了)概率为 k/i+1，其次是因为随机替换的池子中k个元素中任意一个，所以不幸被替换的概率是 1/k，故 
前i个元素(池中元素)中任一被替换的概率 = k/(i+1) * 1/k = 1/i+1 
则(池中元素中)没有被替换的概率为: 1 - 1/(i+1) = i/i+1 
综合① ②,通过乘法规则 
得到前i个元素出现在蓄水池的概率为 k/i * i/(i+1) = k/i+1 
故证明成立

如果m被选中，则随机替换水库中的一个对象。最终每个对象被选中的概率均为k/n，证明如下：

   证明：第m个对象被选中的概率=选择m的概率*（其后元素不被选择的概率+其后元素被选择的概率*不替换第m个对象的概率），即

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]); 
	}
}

因此，蓄水池抽样因为不需知道n的长度，可用于机器学习的数据集的划分，等概率随机抽样分为测试集和训练集。