实现洗牌算法

[lxinr]

Fisher-Yates算法

大致流程：

• 写下从 1 到 N 的数字
• 取一个从 1 到剩下的数字（包括这个数字）的随机数 k
• 从低位开始，得到第 k 个数字（这个数字还没有被取出），把它写在独立的一个列表的最后一位
• 重复第 2 步，直到所有的数字都被取出
• 第 3 步写出的这个序列，现在就是原始数字的随机排列

function shuffle(arr){
    var result = [],
        random;
    while(arr.length > 0){
        random = Math.floor(Math.random() * arr.length);
        result.push(arr[random])
        arr.splice(random, 1)
    }
    return result;
}

在方法中使用了splice，因此其时间复杂度为O(n2)

Knuth-Durstenfeld算法

该方法是为计算机设计的，具体为每次从未处理的数组中随机取一个元素，然后把该元素放到数组的尾部，即数组的尾部放的就是已经处理过的元素，该方法复杂度为O(n)

function shuffle(arr){
    let n = arr.length, random
    while(0 !== n){
        random =  Math.floor(Math.random() * n--) // 向下取整
        [arr[n], arr[random]] = [arr[random], arr[n]] // 变量互换
    }
    return arr
}