Fisher-Yates 洗牌算法

可以原地实现打乱数组。

vector<int> nums; int n=nums.size();
for(int i=0; i<n; i++) {
    uniform_int_distribution<> dis(i, n-1);  // range is [i, n-1]
    int j=dis(gen);
    swap(nums[i], nums[j]);
} 
return nums;

该程序循环n次，每次从[i, n-1]选取一个数字，然后把它交换到第i位。

概率分析：
原数组中的任意一个数字，在第i次被选出从而放到第i个位置的概率是

P(0)=1/n
P(1)=(n-1/n)*(1/n-1)=1/n
...
P(i)= (n-1/n)*(n-2/n-1)*...*(1/n-i)=1/n

所以每个数字出现在每个位置的概率等同。

Donate