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

Question

我有一个像这样的数组：

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

如何随机/洗牌它？

Answer 1

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

您可以在此处看到精彩的可视化。

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

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

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

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

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

Answer 2

下面是 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;
    }
}

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

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

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

---

编辑：更新到 ES6 / ECMAScript 2015

新的 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]];
    }
}

Answer 3

您可以使用地图和排序轻松完成：

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

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

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

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

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

速度

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

Answer 4

警告！
不推荐使用该算法，因为它效率低下且存在强烈偏差；见评论。它被留在这里以供将来参考，因为这个想法并不罕见。

[1,2,3,4,5,6].sort( () => .5 - Math.random() );

---

这个https://javascript.info/array-methods#shuffle-an-array 教程简单地解释了差异。

Answer 5

使用 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();

Answer 6

新的！

更短和更短可能*更快的 Fisher-Yates 洗牌算法

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
}

脚本大小（以 fy 作为函数名称）：90bytes

DEMO
http://jsfiddle.net/vvpoma8w/

*可能在除 Chrome 之外的所有浏览器上速度更快。

如果您有任何问题，请尽管提问。

编辑

是的，它更快

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

使用投票最多的函数。

编辑
计算量过多（不需要--c+1）并且没有人注意到

更短（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
}

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

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

可读版本 (使用原始版本。这比较慢，变量没有用，比如闭包和“;”，代码本身也更短......也许阅读这个如何“缩小”Javascript 代码，顺便说一句，您无法在像上面那样的 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
 }
}

Answer 7

随机排列数组

function shuffleArr (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 纯迭代

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
};

---

可靠性和性能测试

此页面上的一些解决方案并不可靠（它们仅部分随机化数组） 。其他解决方案的效率明显较低。使用 testShuffleArrayFun（见下文），我们可以测试数组混洗函数的可靠性和性能。

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}`)
}

---

其他解决方案

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

ES6 Pure，递归

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 使用 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 使用 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]
    )
}

Answer 8

编辑：这个答案不正确

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

---

对于小型数组来说，一个非常简单的方法就是这样：

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

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

它可能不是很有效，但对于小型数组来说，这工作得很好。这是一个示例，您可以了解它的随机性（或不随机性），以及它是否适合您的用例。

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>

Answer 9

基准

首先让我们看看结果，然后我们将看看下面 shuffle 的每个实现 -

• 

---

拼接速度慢

使用 splice 或 的任何解决方案循环中的 shift 会非常慢。当我们增加数组的大小时，这一点尤其明显。在朴素算法中，我们

1. 在输入数组中获取一个 rand 位置 i，t
2. 添加 t[i] 到数组 t 中的输出
3. splice 位置 i

为了夸大缓慢的效果，我们将在包含一百万个元素的数组上演示这一点。以下脚本近 30 秒 -

const shuffle = t =>
  Array.from(sample(t, t.length))

function* sample(t, n)
{ let r = Array.from(t)
  while (n > 0 && r.length)
  { const i = rand(r.length) // 1
    yield r[i]               // 2
    r.splice(i, 1)           // 3
    n = n - 1
  }
}

const rand = n =>
  0 | Math.random() * n

function swap (t, i, j)
{ let q = t[i]
  t[i] = t[j]
  t[j] = q
  return t
}

const size = 1e6
const bigarray = Array.from(Array(size), (_,i) => i)
console.time("shuffle via splice")
const result = shuffle(bigarray)
console.timeEnd("shuffle via splice")
document.body.textContent = JSON.stringify(result, null, 2)

body::before {
  content: "1 million elements via splice";
  font-weight: bold;
  display: block;
}

---

pop 很快

诀窍是不要拼接，而是使用超高效的pop。为此，您可以

1. 选择要拼接的位置，以代替典型的 splice 调用，i
2. 与最后一个交换 t[i]元素，t[t.length - 1]
3. 将 t.pop() 添加到结果中

现在我们可以随机排列 中的一百万个元素>小于 100 毫秒 -

const shuffle = t =>
  Array.from(sample(t, t.length))

function* sample(t, n)
{ let r = Array.from(t)
  while (n > 0 && r.length)
  { const i = rand(r.length) // 1
    swap(r, i, r.length - 1) // 2
    yield r.pop()            // 3
    n = n - 1
  }
}

const rand = n =>
  0 | Math.random() * n

function swap (t, i, j)
{ let q = t[i]
  t[i] = t[j]
  t[j] = q
  return t
}

const size = 1e6
const bigarray = Array.from(Array(size), (_,i) => i)
console.time("shuffle via pop")
const result = shuffle(bigarray)
console.timeEnd("shuffle via pop")
document.body.textContent = JSON.stringify(result, null, 2)

body::before {
  content: "1 million elements via pop";
  font-weight: bold;
  display: block;
}

---

甚至更快

上面的两个 shuffle 实现会生成一个新输出数组。输入数组未修改。这是我首选的工作方式，但是您可以通过原地洗牌来进一步提高速度。

下面随机播放一百万个元素，不到 10 毫秒 -

function shuffle (t)
{ let last = t.length
  let n
  while (last > 0)
  { n = rand(last)
    swap(t, n, --last)
  }
}

const rand = n =>
  0 | Math.random() * n

function swap (t, i, j)
{ let q = t[i]
  t[i] = t[j]
  t[j] = q
  return t
}

const size = 1e6
const bigarray = Array.from(Array(size), (_,i) => i)
console.time("shuffle in place")
shuffle(bigarray)
console.timeEnd("shuffle in place")
document.body.textContent = JSON.stringify(bigarray, null, 2)

body::before {
  content: "1 million elements in place";
  font-weight: bold;
  display: block;
}

Answer 10

警告！
不建议使用此答案来随机化大型数组、密码学或任何其他需要真正随机性的应用程序，因为它存在偏差且效率低下。元素位置只是半随机的，它们往往会更接近其原始位置。请参阅https://stackoverflow.com/a/18650169/28234。

---

您可以使用 Math.random 任意决定是否返回 1 : -1：

[1, 2, 3, 4].sort(() => (Math.random() > 0.5) ? 1 : -1)

尝试运行以下示例：

const array =  [1, 2, 3, 4];

// Based on the value returned by Math.Random,
// the decision is arbitrarily made whether to return 1 : -1

const shuffeled = array.sort(() => {
  const randomTrueOrFalse = Math.random() > 0.5;
  return randomTrueOrFalse ? 1 : -1
});

console.log(shuffeled);

Answer 11

我发现这个变体挂在这个问题的副本的“作者删除”答案中。与已经有很多赞成票的其他一些答案不同，这是：

1. 实际上是随机的，
2. 不是就地的（因此是 shuffled 名称而不是 shuffle）
3. 此处尚未存在多个变体

这是一个 jsfiddle 显示其使用情况。

Array.prototype.shuffled = function() {
  return this.map(function(n){ return [Math.random(), n] })
             .sort().map(function(n){ return n[1] });
}

Answer 12

在 ES2015 中，你可以使用这个：

Array.prototype.shuffle = function() {
  let m = this.length, i;
  while (m) {
    i = (Math.random() * m--) >>> 0;
    [this[m], this[i]] = [this[i], this[m]]
  }
  return this;
}

用法：

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

Answer 13

//one line solution
shuffle = (array) => array.sort(() => Math.random() - 0.5);


//Demo
let arr = [1, 2, 3];
shuffle(arr);
alert(arr);

https://javascript.info/task/shuffle

Math.random() - 0.5 是一个随机数，可以是正数或
负数，因此排序函数会随机对元素重新排序。

Answer 14

var shuffle = function(array) {
   temp = [];
   originalLength = array.length;
   for (var i = 0; i < originalLength; i++) {
     temp.push(array.splice(Math.floor(Math.random()*array.length),1));
   }
   return temp;
};

Answer 15

递归解决方案：

function shuffle(a,b){
    return a.length==0?b:function(c){
        return shuffle(a,(b||[]).concat(c));
    }(a.splice(Math.floor(Math.random()*a.length),1));
};

Answer 16

使用 ES6 功能的现代短内联解决方案：

['a','b','c','d'].map(x => [Math.random(), x]).sort(([a], [b]) => a - b).map(([_, x]) => x);

（用于教育目的）

Answer 17

Fisher-Yates 在 JavaScript 中随机播放。我将其发布在这里是因为与此处的其他答案相比，使用两个实用函数（swap 和 randInt）澄清了该算法。

function swap(arr, i, j) { 
  // swaps two elements of an array in place
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
function randInt(max) { 
  // returns random integer between 0 and max-1 inclusive.
  return Math.floor(Math.random()*max);
}
function shuffle(arr) {
  // For each slot in the array (starting at the end), 
  // pick an element randomly from the unplaced elements and
  // place it in the slot, exchanging places with the 
  // element in the slot. 
  for(var slot = arr.length - 1; slot > 0; slot--){
    var element = randInt(slot+1);
    swap(arr, element, slot);
  }
}

Answer 18

使用 Fisher-Yates 洗牌算法和 ES6：

// Original array
let array = ['a', 'b', 'c', 'd'];

// Create a copy of the original array to be randomized
let shuffle = [...array];

// Defining function returning random value from i to N
const getRandomValue = (i, N) => Math.floor(Math.random() * (N - i) + i);

// Shuffle a pair of two elements at random position j
shuffle.forEach( (elem, i, arr, j = getRandomValue(i, arr.length)) => [arr[i], arr[j]] = [arr[j], arr[i]] );

console.log(shuffle);
// ['d', 'a', 'b', 'c']

Answer 19

所有其他答案都基于 Math.random() ，它速度快但不适合加密级别随机化。

以下代码使用众所周知的 Fisher-Yates 算法，同时利用 Web Cryptography API 实现加密级别的随机化。

var d = [1,2,3,4,5,6,7,8,9,10];

function shuffle(a) {
	var x, t, r = new Uint32Array(1);
	for (var i = 0, c = a.length - 1, m = a.length; i < c; i++, m--) {
		crypto.getRandomValues(r);
		x = Math.floor(r / 65536 / 65536 * m) + i;
		t = a [i], a [i] = a [x], a [x] = t;
	}

	return a;
}

console.log(shuffle(d));

Answer 20

不更改源数组的随机播放函数

免责声明

请注意，此解决方案不适合大型数组！如果您正在整理大型数据集，则应使用上面建议的 Durstenfeld 算法。

解决方案

function shuffle(array) {
  const result = [], itemsLeft = array.concat([]);

  while (itemsLeft.length) {
    const randomIndex = Math.floor(Math.random() * itemsLeft.length);
    const [randomItem] = itemsLeft.splice(randomIndex, 1); // take out a random item from itemsLeft
    result.push(randomItem); // ...and add it to the result
  }

  return result;
}

工作原理

1. 将初始数组复制到itemsLeft

2. 从 itemsLeft 中选取随机索引，将相应的元素添加到 结果 数组并将其从 itemsLeft 数组中删除

   


3. repeats 步骤 (2) 直到 itemsLeft 数组变为空

4. 返回结果

Answer 21

首先，请查看此处，了解不同排序方法的直观比较在 JavaScript 中。

其次，如果您快速浏览一下上面的链接，您会发现随机顺序排序与其他方法相比似乎表现相对较好，同时实现起来非常容易和快速，如下所示：

function shuffle(array) {
  var random = array.map(Math.random);
  array.sort(function(a, b) {
    return random[array.indexOf(a)] - random[array.indexOf(b)];
  });
}

编辑：正如@gregers所指出的，比较函数是使用值而不是索引来调用的，这就是您需要使用indexOf的原因。请注意，此更改使代码不太适合较大的数组，因为 indexOf 的运行时间为 O(n) 时间。

Answer 22

对CoolAJ86的答案进行简单修改，不修改原始数组：

 /**
 * Returns a new array whose contents are a shuffled copy of the original array.
 * @param {Array} The items to shuffle.
 * https://stackoverflow.com/a/2450976/1673761
 * https://stackoverflow.com/a/44071316/1673761
 */
const shuffle = (array) => {
  let currentIndex = array.length;
  let temporaryValue;
  let randomIndex;
  const newArray = array.slice();
  // While there remains elements to shuffle...
  while (currentIndex) {
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex -= 1;
    // Swap it with the current element.
    temporaryValue = newArray[currentIndex];
    newArray[currentIndex] = newArray[randomIndex];
    newArray[randomIndex] = temporaryValue;
  }
  return newArray;
};

Answer 23

对于我们这些不太有天赋但能够接触到 lodash 奇迹的人来说，有这样的东西 lodash.shuffle。

Answer 24

2019 年我们仍在对数组进行洗牌，所以这是我的方法，这似乎很简洁且快速 对我来说：

const src = [...'abcdefg'];

const shuffle = arr => 
  [...arr].reduceRight((res,_,__,s) => 
    (res.push(s.splice(0|Math.random()*s.length,1)[0]), res),[]);

console.log(shuffle(src));

.as-console-wrapper {min-height: 100%}

Answer 25

您可以使用 lodash 随机播放。就像魅力一样工作

import _ from lodash;

let numeric_array = [2, 4, 6, 9, 10];
let string_array = ['Car', 'Bus', 'Truck', 'Motorcycle', 'Bicycle', 'Person']

let shuffled_num_array = _.shuffle(numeric_array);
let shuffled_string_array = _.shuffle(string_array);

console.log(shuffled_num_array, shuffled_string_array)

Answer 26

使用生成器函数的 ES6 紧凑代码*

它的工作原理是从未洗牌的数组的副本中随机删除项目，直到没有剩余的为止。它使用新的 ES6 生成器 函数。

只要 Math.random() 是公平的，这将是一个完全公平的洗牌。

let arr = [1,2,3,4,5,6,7]

function* shuffle(arr) {
  arr = [...arr];
  while(arr.length) yield arr.splice(Math.random()*arr.length|0, 1)[0]
}

console.log([...shuffle(arr)])

或者，使用 ES6 和 splice：

let arr = [1,2,3,4,5,6,7]

let shuffled = arr.reduce(([a,b])=>
  (b.push(...a.splice(Math.random()*a.length|0, 1)), [a,b]),[[...arr],[]])[1]

console.log(shuffled)

或者，ES6索引交换方法：

let arr = [1,2,3,4,5,6,7]

let shuffled = arr.reduce((a,c,i,r,j)=>
  (j=Math.random()*(a.length-i)|0,[a[i],a[j]]=[a[j],a[i]],a),[...arr])

console.log(shuffled)

Answer 27

随机化数组

 var arr = ['apple','cat','Adam','123','Zorro','petunia']; 
 var n = arr.length; var tempArr = [];

 for ( var i = 0; i < n-1; i++ ) {

    // The following line removes one random element from arr 
     // and pushes it onto tempArr 
     tempArr.push(arr.splice(Math.floor(Math.random()*arr.length),1)[0]);
 }

 // Push the remaining item onto tempArr 
 tempArr.push(arr[0]); 
 arr=tempArr; 

Answer 28

虽然已经建议了许多实现，但我觉得我们可以使用 forEach 循环使其更短、更容易，因此我们不需要担心计算数组长度，而且我们可以安全地避免使用临时变量。

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

myArr.forEach((val, key) => {
  randomIndex = Math.ceil(Math.random()*(key + 1));
  myArr[key] = myArr[randomIndex];
  myArr[randomIndex] = val;
});
// see the values
console.log('Shuffled Array: ', myArr)

Answer 29

最短的 arrayShuffle 函数

function arrayShuffle(o) {
    for(var j, x, i = o.length; i; j = parseInt(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
    return o;
}

Answer 30

有趣的是，没有非变异的递归答案：

var shuffle = arr => {
  const recur = (arr,currentIndex)=>{
    console.log("What?",JSON.stringify(arr))
    if(currentIndex===0){
      return arr;
    }
    const randomIndex = Math.floor(Math.random() * currentIndex);
    const swap = arr[currentIndex];
    arr[currentIndex] = arr[randomIndex];
    arr[randomIndex] = swap;
    return recur(
      arr,
      currentIndex - 1
    );
  }
  return recur(arr.map(x=>x),arr.length-1);
};

var arr = [1,2,3,4,5,[6]];
console.log(shuffle(arr));
console.log(arr);