【算法】随机洗牌算法-随机数组重组问题

随机洗牌可以看成随机数组重组问题, 什么意思呢

假如我要把一副牌随机打乱重组这一副牌可以怎么做? 随机洗牌是从原数组中随机抽取一张牌放在一边, 然后再从原数组中再选一张放到刚刚取出来的牌堆中, 重复这个行为, 直到原数组被取完为止

算法怎么实现?

function shuffle(array) {
    var arr = [];
    var len = array.length;
    var i;
    while (len) {
        i = Math.floor(Math.random() * len);
        if (i in array) {
            arr.push(array[i]);
            delete array[i];
            len--;
        }
    }
    return arr;
}

注意因为产生的随机数有可能经常是同一个值, 那么就有可能很大程度上造成效率问题, 甚至极端地说, 产生的随机数一直是同一个值, 那么程序就永远执行不完, 那就考虑用splice()把该元素删除掉

并且如果用splice()来删除元素也会造成效率问题, 他会把后面的数组补充到前面去, 也就是常说的移动, 那么删除一个移动一个就会很耗时间,

那么怎么高效率洗牌?

可以把每次选到的随机数字和数组末尾进行交换

i = Math.floor(Math.random() * len--); 
[array[len], array[i]] = [array[i], array[len]];