11.md

随机打乱数组/洗牌算法

洗牌算法最核心:

保证每个元素在每个位置出现的概率相同。

常用的洗牌算法有

• Math.random()
• Fisher-Yates
• Knuth-Durstenfeld

Fisher–Yates Shuffle 算法可视化网站

Math.random()

利用数组原型的上方法 sort ，在数据量小的情况下可以，但随着数据规模的增大，随机性变差。不能保证每个元素在每个位置出现的概率一样。

[1, 2, 3, 5, 6, 6, 7].sort((a, b) => Math.random() - .5)

Fisher-Yates

算法的核心思想是在原数组随机一枚元素，放入到新的元素中。

function shuffle(arr) {
    let result = []
    while (arr.length) {
        const random = Math.floor(Math.random() * arr.length)
        result.push(arr[random])
        arr.splice(random, 1)
    }
    return result
}

复杂度分析

• 时间复杂度O(N^2), 主要由于遍历每一层元素及原数组的splice。
• 空间复杂度O(N), 存放新的数组的内存空间的消耗。

Fisher–Yates Shuffle

Fisher-Yates 洗牌算法的一个变种是 Knuth Shuffle,

每次从未处理的数组中随机取一个元素，然后把该元素放到数组的尾部，即数组的尾部放的就是已经处理过的元素，这是一种原地打乱的算法，每个元素随机概率也相等，时间复杂度从 Fisher 算法的 O(n2)提升到了 O(n)。

function shuffle2(arr) {
    let length = arr.length;
    while(length){
        const random = Math.floor(Math.random() * length)
        length--
        // 交换两个元素
        let temp = arr[length]
        arr[length] = arr[random]
        arr[random] = temp

    }
    return arr
}

// es6 实现

function shuffle3(arr) {
    let length = arr.length;
    while (length) {
        const random = Math.floor(Math.random() * length)
        length--
        [arr[random], arr[length]] = [arr[length], arr[random]];

    }
    return arr
}