如何对数组进行洗牌？

Question

我想在JavaScript中对元素数组进行洗牌，就像这样:

[0, 3, 3] -> [3, 0, 3]
[9, 3, 6, 0, 6] -> [0, 3, 6, 9, 6]
[3, 3, 6, 0, 6] -> [0, 3, 6, 3, 6]

- Anshul

---

这个问题在stackoverflow上已经被回答了很多次。请查看这里：https://dev59.com/IXE95IYBdhLWcg3wHqMV 这里还有一个：http://stackoverflow.com/questions/5086262/javascript-array-shuffle-with-padding - joekarl

一个很好的资源，包括JavaScript洗牌、发牌、抽牌和其他日期和数学相关内容。 - RobG

这是一个简短的代码片段，意思是将传入的数组随机打乱后返回。具体实现是通过reduce方法和splice函数以及Math.random()函数完成的随机排序过程。 - brunettdan

@VitaliPom 不要在random()中使用sort()。Sort不期望随机结果，结果可能不均匀。微软的浏览器投票因此出现了故障。 - Sheepy

@brunettdan 我写了这个一行代码，它不使用splice函数，速度更快：arr1.reduceRight((p,v,i,a)=>(v=i?~~(Math.random()*(i+1)):i, v-i?[a[v],a[i]]=[a[i],a[v]]:0, a),a)；另外请查看这个函数。 - Sheepy

Answer 1

使用Fisher-Yates shuffle算法的现代版本：

/**
 * Shuffles array in place.
 * @param {Array} a items An array containing the items.
 */
function shuffle(a) {
    var j, x, i;
    for (i = a.length - 1; i > 0; i--) {
        j = Math.floor(Math.random() * (i + 1));
        x = a[i];
        a[i] = a[j];
        a[j] = x;
    }
    return a;
}

ES2015（ES6）版本

/**
 * Shuffles array in place. ES6 version
 * @param {Array} a items An array containing the items.
 */
function shuffle(a) {
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], a[i]];
    }
    return a;
}

请注意，使用 解构赋值 交换变量会导致严重的性能损失，截至2017年10月。

用途

var myArray = ['1','2','3','4','5','6','7','8','9'];
shuffle(myArray);

实现原型

使用Object.defineProperty（此SO答案提供的方法），我们还可以将此函数实现为数组的原型方法，而不会在for（i in arr）等循环中显示。 以下代码将允许您调用arr.shuffle()来打乱数组arr：

Object.defineProperty(Array.prototype, 'shuffle', {
    value: function() {
        for (let i = this.length - 1; i > 0; i--) {
            const j = Math.floor(Math.random() * (i + 1));
            [this[i], this[j]] = [this[j], this[i]];
        }
        return this;
    }
});

- Jeff

---

这个方法（以及下面的方法）都会修改原始数组。这不是什么大问题，但调用它的示例有点奇怪。 - Michael

@Michael +1，感谢指出重新赋值是不必要的。实际上，这是具有误导性的，可能应该是在此评论线程中首先指出的事情。 - ryan-cook

我发现ES6的交换操作速度较慢（一旦我使其正常工作。你必须在 [ 前加上分号，这更加理由是直接总是使用它们）。 - trlkly

@trlkly：由于使用了解构赋值，ES2015变体会更慢。希望引擎能尽快优化它。 - Przemek

@RobG，const 是一个完美的选择，因为它是块级作用域，不像 var，并且在每次迭代后都会重新声明。let 也可以使用，但由于 j 在 for 块内部没有改变其值，所以 const 是更好的选择。 - pauk960

Answer 2

你可以使用Fisher-Yates Shuffle（代码改编自此网站）：

function shuffle(array) {
    let counter = array.length;

    // While there are elements in the array
    while (counter > 0) {
        // Pick a random index
        let index = Math.floor(Math.random() * counter);

        // Decrease counter by 1
        counter--;

        // And swap the last element with it
        let temp = array[counter];
        array[counter] = array[index];
        array[index] = temp;
    }

    return array;
}

- Blender

---

第一个答案似乎有bug。大约每15次运行中就会出现额外的 undefined 列。http://jsfiddle.net/tomasswood/z8zm7/ - Thomas Wood

为什么你不使用random + Array.prototype.sort呢？这比两个答案都更简单，代码也更少。 - volter9

@Volter9：因为分布不会是均匀的。 - Blender

Jeff Atwood在他的博客上发表了一篇非常有趣的关于这个算法的帖子。我想知道为什么它被实现成这个样子。 - JonnyRaa

请注意，这会更改初始数组，这不是一种函数式方法。我只是把它留在这里，供那些盲目复制它的人参考（就像我一样）。 - dcts