Fisher-Yates 洗牌算法

Fisher-Yates 洗牌算法常用来生成数组元素的随机排列（要求每种排列等概率出现），假定数组包含n个元素，索引从0开始，则伪代码为：

// 反向版本
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]
​
// 正向版本
for i from 0 to n−2 do
     j ← random integer such that i ≤ j < n
     exchange a[i] and a[j]

其对应的示例代码为：

// 反向版本
vector<int> shuffle(vector<int> nums) {
    int n = nums.size();
    for (int i = n - 1; i >= 0; i--) {
        int pos = rand() % (i + 1);
        swap(nums[i], nums[pos]);
    }
}
​
// 正向版本
vector<int> shuffle(vector<int> nums) {
    int n = nums.size();
    for (int j = 0; j < n; j++) {
        int pos = j + rand() % (n - j);
        swap(nums[j], nums[pos]);
    }
​