洗牌算法之Knuth-Shuffle算法

看到好多公众号里写的洗牌算法有问题。

比如，最常见的一种是：

Array.prototype.shuffle = function() {
    return this.sort(() => Math.random() - 0.5);
}

这种算法的问题在于 Math.random() - 0.5 会导致左边的元素会堆积在左边，右边的元素会堆积在右边，尽管数组在被洗牌后看起来像是被打乱了。

洗牌算法的核心应该是找到一个映射方法，将数组中原来的元素value随机放置到数组中一个新的index上。

Knuth-Shuffle算法

关于Knuth-Shuffle，CSDN等博客基本写的都有问题。

我的理解如下：

1. 一个长度为n的数组，设置一个指针rightPos放在最右边。
2. 随机选取包含该rightPos在内的前n个元素的其中一个元素，将rightPos元素与其交换，这样可以保证rightPos元素有几率留在原位置。
3. rightPos左移一位，重复第2步直到rightPos为0。

/*
 *  改变原数组并返回
 */
Array.prototype.shuffle = function() {
    for (let len = this.length, i = len - 1; i >= 0; i--) {
        // 指针index
        let rightPos = i;
        // 随机选取前i+1个元素的index
        let randomPos = Math.floor(Math.random() * (i + 1));
        // 交换两个元素
        [this[randomPos], this[rightPos]] = [this[rightPos], this[randomPos]];
    }
    return this;
}

[1, 2, 3, 4, 5].shuffle();