如何随机化（洗牌）一个 JavaScript 数组？

How to randomize (shuffle) a JavaScript array?

提问by Click Upvote

I have an array like this:

我有一个这样的数组：

var arr1 = ["a", "b", "c", "d"];

How can I randomize / shuffle it?

我怎样才能随机化/洗牌呢？

回答by ChristopheD

The de-facto unbiased shuffle algorithm is the Fisher-Yates (aka Knuth) Shuffle.

事实上的无偏洗牌算法是 Fisher-Yates（又名 Knuth）洗牌。

See https://github.com/coolaj86/knuth-shuffle

见https://github.com/coolaj86/knuth-shuffle

You can see a great visualization here(and the original post linked to this)

你可以在这里看到一个很棒的可视化（以及链接到这个的原始帖子）

function shuffle(array) {
  var currentIndex = array.length, temporaryValue, randomIndex;

  // While there remain elements to shuffle...
  while (0 !== currentIndex) {

    // Pick a remaining element...
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex -= 1;

    // And swap it with the current element.
    temporaryValue = array[currentIndex];
    array[currentIndex] = array[randomIndex];
    array[randomIndex] = temporaryValue;
  }

  return array;
}

// Used like so
var arr = [2, 11, 37, 42];
shuffle(arr);
console.log(arr);

Some more info about the algorithmused.

关于所用算法的更多信息。

回答by Laurens Holst

Here's a JavaScript implementation of the Durstenfeld shuffle, an optimized version of Fisher-Yates:

这是Durstenfeld shuffle的 JavaScript 实现，这是 Fisher-Yates 的优化版本：

/* Randomize array in-place using Durstenfeld shuffle algorithm */
function shuffleArray(array) {
    for (var i = array.length - 1; i > 0; i--) {
        var j = Math.floor(Math.random() * (i + 1));
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

It picks a random element for each original array element, and excludes it from the next draw, like picking randomly from a deck of cards.

它为每个原始数组元素选择一个随机元素，并将其从下一次抽奖中排除，就像从一副纸牌中随机选择一样。

This clever exclusion swaps the picked element with the current one, then picks the next random element from the remainder, looping backwards for optimal efficiency, ensuring the random pick is simplified (it can always start at 0), and thereby skipping the final element.

这种巧妙的排除将选取的元素与当前元素交换，然后从余数中选取下一个随机元素，向后循环以获得最佳效率，确保随机选取得到简化（它始终可以从 0 开始），从而跳过最后一个元素。

Algorithm runtime is O(n). Notethat the shuffle is done in-place so if you don't want to modify the original array, first make a copy of it with .slice(0).

算法运行时是O(n). 请注意，shuffle 是就地完成的，因此如果您不想修改原始数组，请先使用.slice(0).

---

---

EDIT:Updating to ES6 / ECMAScript 2015

编辑：更新到 ES6 / ECMAScript 2015

The new ES6 allows us to assign two variables at once. This is especially handy when we want to swap the values of two variables, as we can do it in one line of code. Here is a shorter form of the same function, using this feature.

新的 ES6 允许我们一次分配两个变量。当我们想要交换两个变量的值时，这特别方便，因为我们可以在一行代码中完成。这是使用此功能的相同功能的较短形式。

function shuffleArray(array) {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
}

回答by deadrunk

Warning!
The use of this algorithm is not recommended, because it is inefficientand strongly biased; see comments. It is being left here for future reference, because the idea is not that rare.

警告！不推荐
使用这种算法，因为它效率低下且有很强的偏见；看评论。它被留在这里以备将来参考，因为这种想法并不罕见。

[1,2,3,4,5,6].sort(function() {
  return .5 - Math.random();
});

回答by con

One could (or should) use it as a protoype from Array:

人们可以（或应该）将其用作 Array 的原型：

From ChristopheD:

来自克里斯托夫：

Array.prototype.shuffle = function() {
  var i = this.length, j, temp;
  if ( i == 0 ) return this;
  while ( --i ) {
     j = Math.floor( Math.random() * ( i + 1 ) );
     temp = this[i];
     this[i] = this[j];
     this[j] = temp;
  }
  return this;
}

回答by superluminary

You can do it easily with map and sort:

您可以使用 map 和 sort 轻松完成：

let unshuffled = ['hello', 'a', 't', 'q', 1, 2, 3, {cats: true}]

let shuffled = unshuffled
  .map((a) => ({sort: Math.random(), value: a}))
  .sort((a, b) => a.sort - b.sort)
  .map((a) => a.value)

1. We put each element in the array in an object, and give it a random sort key
2. We sort using the random key
3. We unmap to get the original objects

1. 我们将数组中的每个元素放在一个对象中，并赋予它一个随机排序键
2. 我们使用随机键排序
3. 我们取消映射以获取原始对象

You can shuffle polymorphic arrays, and the sort is as random as Math.random, which is good enough for most purposes.

您可以对多态数组进行 shuffle，排序与 Math.random 一样随机，这对于大多数用途来说已经足够了。

Since the elements are sorted against consistent keys that are not regenerated each iteration, and each comparison pulls from the same distribution, any non-randomness in the distribution of Math.random is canceled out.

由于元素根据每次迭代都不会重新生成的一致键进行排序，并且每次比较都从相同的分布中提取，因此 Math.random 分布中的任何非随机性都被抵消了。

Speed

速度

Time complexity is O(N log N), same as quick sort. Space complexity is O(N). This is not as efficient as a Fischer Yates shuffle but, in my opinion, the code is significantly shorter and more functional. If you have a large array you should certainly use Fischer Yates. If you have a small array with a few hundred items, you might do this.

时间复杂度为 O(N log N)，与快速排序相同。空间复杂度为 O(N)。这不如 Fischer Yates shuffle 有效，但在我看来，代码明显更短且功能更强大。如果你有一个大数组，你当然应该使用 Fischer Yates。如果你有一个包含几百个项目的小数组，你可以这样做。

回答by vn_grv

Use the underscore.js library. The method _.shuffle()is nice for this case. Here is an example with the method:

使用 underscore.js 库。该方法_.shuffle()非常适合这种情况。以下是该方法的示例：

var _ = require("underscore");

var arr = [1,2,3,4,5,6];
// Testing _.shuffle
var testShuffle = function () {
  var indexOne = 0;
    var stObj = {
      '0': 0,
      '1': 1,
      '2': 2,
      '3': 3,
      '4': 4,
      '5': 5
    };
    for (var i = 0; i < 1000; i++) {
      arr = _.shuffle(arr);
      indexOne = _.indexOf(arr, 1);
      stObj[indexOne] ++;
    }
    console.log(stObj);
};
testShuffle();

回答by cocco

NEW!

新的！

Shorter & probably *faster Fisher-Yates shuffle algorithm

更短且可能*更快的 Fisher-Yates shuffle 算法

1. it uses while---
2. bitwise to floor (numbers up to 10 decimal digits (32bit))
3. removed unecessary closures & other stuff

1. 它使用 while ---
2. 按位到地板（数字最多 10 位十进制数字（32 位））
3. 删除了不必要的关闭和其他东西

---

---

function fy(a,b,c,d){//array,placeholder,placeholder,placeholder
 c=a.length;while(c)b=Math.random()*(--c+1)|0,d=a[c],a[c]=a[b],a[b]=d
}

script size (with fy as function name): 90bytes

脚本大小（以 fy 作为函数名）：90 字节

DEMOhttp://jsfiddle.net/vvpoma8w/

演示http://jsfiddle.net/vvpoma8w/

*faster probably on all browsers except chrome.

*可能在除 chrome 之外的所有浏览器上都更快。

If you have any questions just ask.

如果你有问题，就问吧。

EDIT

编辑

yes it is faster

是的，它更快

PERFORMANCE:http://jsperf.com/fyshuffle

性能：http : //jsperf.com/fyshuffle

using the top voted functions.

使用最高投票的功能。

EDITThere was a calculation in excess (don't need --c+1) and noone noticed

编辑有一个多余的计算（不需要--c + 1），没有人注意到

shorter(4bytes)&faster(test it!).

更短（4 字节）&更快（测试一下！）。

function fy(a,b,c,d){//array,placeholder,placeholder,placeholder
 c=a.length;while(c)b=Math.random()*c--|0,d=a[c],a[c]=a[b],a[b]=d
}

Caching somewhere else var rnd=Math.randomand then use rnd()would also increase slightly the performance on big arrays.

在其他地方缓存var rnd=Math.random然后使用rnd()也会稍微提高大阵列的性能。

http://jsfiddle.net/vvpoma8w/2/

http://jsfiddle.net/vvpoma8w/2/

Readable version(use the original version. this is slower, vars are useless, like the closures & ";", the code itself is also shorter ... maybe read this How to 'minify' Javascript code, btw you are not able to compress the following code in a javascript minifiers like the above one.)

可读版本（使用原始版本。这个比较慢，vars 没用，就像闭包和“;”一样，代码本身也更短......也许读这个How to 'minify' Javascript code，顺便说一句你不能将以下代码压缩在像上面那样的 javascript 压缩器中。）

function fisherYates( array ){
 var count = array.length,
     randomnumber,
     temp;
 while( count ){
  randomnumber = Math.random() * count-- | 0;
  temp = array[count];
  array[count] = array[randomnumber];
  array[randomnumber] = temp
 }
}

回答by Kris Selbekk

Edit: This answer is incorrect

编辑：这个答案是不正确的

See comments and https://stackoverflow.com/a/18650169/28234. It is being left here for reference because the idea isn't rare.

请参阅评论和https://stackoverflow.com/a/18650169/28234。它留在这里以供参考，因为这个想法并不罕见。

---

---

A very simple way for small arrays is simply this:

小数组的一个非常简单的方法就是这样：

const someArray = [1, 2, 3, 4, 5];

someArray.sort(() => Math.random() - 0.5);

It's probably not very efficient, but for small arrays this works just fine. Here's an example so you can see how random (or not) it is, and whether it fits your usecase or not.

这可能不是很有效，但对于小数组，这很好用。这是一个示例，您可以查看它的随机性（或不随机性），以及它是否适合您的用例。

const resultsEl = document.querySelector('#results');
const buttonEl = document.querySelector('#trigger');

const generateArrayAndRandomize = () => {
  const someArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
  someArray.sort(() => Math.random() - 0.5);
  return someArray;
};

const renderResultsToDom = (results, el) => {
  el.innerHTML = results.join(' ');
};

buttonEl.addEventListener('click', () => renderResultsToDom(generateArrayAndRandomize(), resultsEl));

<h1>Randomize!</h1>
<button id="trigger">Generate</button>
<p id="results">0 1 2 3 4 5 6 7 8 9</p>

回答by Ben Carp

Reliable, Efficient, Short

可靠、高效、简短

Some solutions on this page aren't reliable (they only partially randomise the array). Other solutions are significantly less efficient. With testShuffleArrayFun(see below) we can test array shuffling functions for reliability and performance. The following solutions are: reliable, efficient and short (using ES6 syntax)

此页面上的某些解决方案不可靠（它们仅部分随机化数组）。其他解决方案的效率要低得多。使用testShuffleArrayFun（见下文）我们可以测试阵列改组函数的可靠性和性能。以下解决方案是：可靠、高效和简短（使用 ES6 语法）

[Comparison tests were done using testShuffleArrayFunagainst other solutions, in Google Chrome]

[testShuffleArrayFun在谷歌浏览器中与其他解决方案进行了比较测试]

Shuffle Array In place

Shuffle Array 就位

    function getShuffledArr (array){
        for (var i = array.length - 1; i > 0; i--) {
            var rand = Math.floor(Math.random() * (i + 1));
            [array[i], array[rand]] = [array[rand], array[i]]
        }
    }

ES6 Pure, Iterative

ES6 纯的，迭代的

    const getShuffledArr = arr => {
        const newArr = arr.slice()
        for (let i = newArr.length - 1; i > 0; i--) {
            const rand = Math.floor(Math.random() * (i + 1));
            [newArr[i], newArr[rand]] = [newArr[rand], newArr[i]];
        }
        return newArr
    };

---

---

Reliability and Performance Test

可靠性和性能测试

As you can see in this page, there have been incorrect solutions offered here in the past. I wrote and have used the following function to test any pure (no side effects) array randomizing functions.

正如您在本页中看到的那样，过去在这里提供了不正确的解决方案。我编写并使用了以下函数来测试任何纯（无副作用）数组随机化函数。

    function testShuffleArrayFun(getShuffledArrayFun){
        const arr = [0,1,2,3,4,5,6,7,8,9]

        var countArr = arr.map(el=>{
            return arr.map(
                el=> 0
            )
        }) //   For each possible position in the shuffledArr and for 
           //   each possible value, we'll create a counter. 
        const t0 = performance.now()
        const n = 1000000
        for (var i=0 ; i<n ; i++){
            //   We'll call getShuffledArrayFun n times. 
            //   And for each iteration, we'll increment the counter. 
            var shuffledArr = getShuffledArrayFun(arr)
            shuffledArr.forEach(
                (value,key)=>{countArr[key][value]++}
            )
        }
        const t1 = performance.now()
        console.log(`Count Values in position`)
        console.table(countArr)

        const frequencyArr = countArr.map( positionArr => (
            positionArr.map(  
                count => count/n
            )
        )) 

        console.log("Frequency of value in position")
        console.table(frequencyArr)
        console.log(`total time: ${t1-t0}`)
    }

---

---

Other Solutions

其他解决方案

Other solutions just for fun.

其他解决方案只是为了好玩。

ES6 Pure, Recursive

ES6 纯递归

    const getShuffledArr = arr => {
        if (arr.length === 1) {return arr};
        const rand = Math.floor(Math.random() * arr.length);
        return [arr[rand], ...getShuffledArr(arr.filter((_, i) => i != rand))];
    };

ES6 Pure using array.map

ES6 Pure 使用 array.map

    function getShuffledArr (arr){
        return [...arr].map( (_, i, arrCopy) => {
            var rand = i + ( Math.floor( Math.random() * (arrCopy.length - i) ) );
            [arrCopy[rand], arrCopy[i]] = [arrCopy[i], arrCopy[rand]]
            return arrCopy[i]
        })
    }

ES6 Pure using array.reduce

ES6 Pure 使用 array.reduce

    function getShuffledArr (arr){
        return arr.reduce( 
            (newArr, _, i) => {
                var rand = i + ( Math.floor( Math.random() * (newArr.length - i) ) );
                [newArr[rand], newArr[i]] = [newArr[i], newArr[rand]]
                return newArr
            }, [...arr]
        )
    }

回答by KingKongFrog

Adding to @Laurens Holsts answer. This is 50% compressed.

添加到@Laurens Holsts 的答案。这是 50% 的压缩。

function shuffleArray(d) {
  for (var c = d.length - 1; c > 0; c--) {
    var b = Math.floor(Math.random() * (c + 1));
    var a = d[c];
    d[c] = d[b];
    d[b] = a;
  }
  return d
};