洗牌算法

缘起：如何真正的打乱数组?

let arr = [1, 2, 3, 4, 5];

arr.sort(function(){
    return Math.random() - 0.5;
});

上述代码看似可以打乱，但是不是真正的打乱。做下测试：

let times = 100000;
let res = {};

for (let i = 0; i < times; i++) {
    let arr = [1, 2, 3];
    arr.sort(() => Math.random() - 0.5);
    let key = JSON.stringify(arr);
    res[key] ? res[key]++ : res[key] = 1;
}

// 为了方便展示，转换成百分比
for (let key in res) {
    res[key] = res[key] / times * 100 + '%'
}
------------------------------------------------

{
    '[2,1,3]': '25.027%',
    '[1,2,3]': '25.05%',
    '[1,3,2]': '12.361%',
    '[3,2,1]': '12.447%',
    '[2,3,1]': '12.545%',
    '[3,1,2]': '12.57%'
}

可以看出末尾数字是3的概率为50%，而不是想象中的33%。

究其原因是因为sort函数底层是使用插入排序实现的

所以初始为[1,2,3]的时候，插入排序从2开始，和前面做比较，此时有50%的几率顺序50%的几率逆序，所以

[1,2,3] [2,1,3]出现几率都为50% 50%。接下来的操作如下图所示：

数组	i = 1	i = 2	总计
[1, 2, 3]	50% [1, 2, 3]	50% [1, 2, 3]	25% [1, 2, 3]
		25% [1, 3, 2]	12.5% [1, 3, 2]
		25% [3, 1, 2]	12.5% [3, 1, 2]
	50% [2, 1, 3]	25% [2, 1, 3]	50% [2, 1, 3]
		25% [2, 3, 1]	12.5% [2, 3, 1]
		25% [3, 2, 1]	12.5% [3, 2, 1]

洗牌算法：

function shuffle(arr) {
    for (let i = arr.length; i; i--) {
        let random = Math.floor(Math.random() * i);
        [arr[i - 1], arr[random]] = [arr[random], arr[i - 1]];
    }
    return arr;
}
----------------------------------------
{ '[3,1,2]': '16.825000000000003%',
  '[2,1,3]': '16.739%',
  '[1,2,3]': '16.688%',
  '[1,3,2]': '16.72%',
  '[3,2,1]': '16.697%',
  '[2,3,1]': '16.331%' }

洗牌算法，或者说随机乱置算法的正确性衡量标准是：对于每种可能的结果出现的概率必须相等，也就是说要足够随机。

蒙特卡罗方法验证正确性：采样越多，越近似最优解。