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

Question

我有一个数组，其形式如下：

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

我该如何对它进行随机排列 / 洗牌？

- Ali

---

抛出一个东西，让你可以通过Mike Bostock制作的可视化工具来看到洗牌函数实际上是多么随机：http://bost.ocks.org/mike/shuffle/compare.html - aug

@Blazemonger jsPref已经无人问津了。你可以在这里发帖询问哪个是最快的？ - eozzy

这句话的意思是将一个名为arr1的数组随机排序，代码中使用了箭头函数以及Math.random()来实现。 - yuval.bl

简短回答：a.sort(() => Math.random() - 0.5) 的意思是将数组 a 随机排序。 - SaboSuke

如果在同一规范中的上几行中看到以下内容：“如果comparefn既不是未定义的，也不是对items元素的一致比较函数，则排序顺序是实现定义的。” - yuval.bl

Answer 1

事实上无偏的洗牌算法是 费雪-耶茨 (又名 Knuth) 洗牌算法。

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

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

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

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

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

  return array;
}

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

关于所使用算法的一些更多信息请点击这里。

- ChristopheD

---

上面的答案跳过了元素0，条件应该是 i-- 而不是 --i。同时，测试语句 if (i==0)... 是多余的，因为如果 i == 0，while 循环将永远不会被进入。使用 ...| 0 可以更快地执行调用到 Math.floor。可以将 tempi 或 tempj 中的一个移除，并将值直接赋给适当的 myArray[i] 或 j。 - RobG

@RobG 上面的实现在功能上是正确的。在 Fisher-Yates 算法中，循环不应该运行到数组的第一个元素。在 维基百科 上有其他跳过第一个元素的实现。同时，查看这篇文章，它解释了为什么循环不运行第一个元素非常重要。 - theon

如果你要在繁忙的循环中进行解构赋值，请务必进行转译——分配对象是昂贵的。 - ggorlen

这是理论的很好展示，但实际实现应该检查输入是否真的是一个数组。因为如果你不小心传入了不同类型的值，那么 while 循环永远不会结束，程序将挂起。 - Isaac King

我有点惊讶这是最佳答案。事实上，有很多问题存在...... 不适当的作用域、忽略了直接使用 for 循环、错误地将 != 与 !== 混淆使用、如果传入一个空数组则会进入无限循环、修改并返回参数。 - Sam

Answer 2

这是一个JavaScript实现的Durstenfeld洗牌算法，它是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]];
    }
}

- Laurens Holst

---

这个答案中的实现偏向于数组的较低端。从困难的方式中发现。Math.random() 不应该乘以循环计数器加1，而是应该乘以 array.length()。请参阅 在 JavaScript 中生成特定范围内的随机整数？ 获取非常全面的解释。 - Marjan Venema

@MarjanVenema 不确定您是否还在关注此问题，但这个答案是正确的，而您建议的更改实际上会引入偏差。请参阅 https://blog.codinghorror.com/the-danger-of-naivete/ 以获取有关此错误的详细信息。 - user94559

重复用户94559的评论，并附上参考资料https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle 要交换的元素（j）应该在0到当前数组索引（i）之间。 - RedPandaCurios

你是不是忘了加上 return array; 了？ - IRvanFauziE

函数在您传递给它的数组上工作。添加return array只会使其更容易地与其他.链式调用。 - AgainPsychoX

Answer 3

你可以很容易地使用map和sort来完成：

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。如果您有一个只有几百个项目的小数组，可以使用此方法。

- superluminary

---

非常好。这是用 JavaScript 实现的 Schwartzian 变换。 - Mark Grimes

这是最佳答案（适用于短数组）的原因有很多。对我来说，它非常有用，因为我正在使用 React，而在2021年，像这样的函数式方法是最好的选择。 - Software Engineer

如果您必须映射两次，则再次考虑复杂性，它已经两次遍历了N个元素，而这还没有考虑JS的.sort算法的快速排序复杂性。 - Ilja KO

@IljaKO - O(2N + 2(N log N)) 简化为O(N log N)，因此它真正的复杂度为O(N log N)。大O符号主要是关于最大的比例因子。我们移除常数因素是因为它们不随着输入大小而缩放，并简化为最大的单一缩放因子。大O符号有意地不涉及细节。 - superluminary

@BlobKat - 对于误解我很抱歉。 - superluminary

Answer 4

警告！
不建议使用此算法，因为它效率低下且严重偏差；请参阅评论。将其保留在这里以供参考是因为其思想并不罕见。

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

---

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

- deadrunk

---

因为这并不十分随机，所以我会将其点踩。我不知道为什么它有那么多赞。请勿使用此方法。它看起来很漂亮，但并不完全正确。以下是在进行了10,000次迭代后，您的数组中每个数字命中索引[0]的次数结果（我也可以提供其他结果）：1 = 29.19％，2 = 29.53％，3 = 20.06％，4 = 11.91％，5 = 5.99％，6 = 3.32％。 - radtad

如果您需要随机化相对较小的数组而不涉及加密事务，则使用更复杂的解决方案可以获取更多"随机性"。我完全同意这一点。请注意，本句中的“随机性”即英文中的“randomness”。 - deadrunk

它也是所有可用方法中效率最低的。 - Blazemonger

问题在于它不是确定性的，这将会导致错误的结果（如果1 > 2并且2 > 3，那么应该得出1 > 3的结论，但这不能保证。这会让排序变得混乱，并给出@radtad所评论的结果）。 - MatsLindh

重要阅读：是否正确使用JavaScript数组排序（Array.sort()）方法来洗牌？ - Bergi

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

- vn_grv

Answer 6

有人可以（但不应该）将其用作Array的原型：

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

- con

---

除非你真的需要在整个程序中洗牌所有或大多数数组，并且你正在一个没有人能找到的地方编写这个程序，否则不要触碰原型。我看到这个答案已经十年了，可能是在“人们停止扩展原型，这是不好的”运动之前发生的。 - Lukas Liesis

在 while 循环中，当 i 等于 0 时，它变为 false，因此忽略了列表中的第一个元素，只对其余部分进行洗牌... 因此第一个元素永远不会被洗牌...扩展原型的 +1，可以使代码在我的情况下更易读。 - Got To Figure

Answer 7

新！

更短、可能更快的费雪耶茨洗牌算法

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作为函数名称）：90字节

演示 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
 }
}

- cocco

---

请查看性能表现……在大多数浏览器上快了2倍……但需要更多的jsperf测试者…… - cocco

JS是一种接受许多快捷方式和不同编写方式的语言。尽管有许多慢而易读的函数，但我只想展示如何以更高效的方式完成它，并节省一些字节...在这里，按位运算符和缩写真的被低估了，而且网络上充满了错误和缓慢的代码。 - cocco

这真是让人又惊又喜。我已经写了20年的JS，但刚刚阅读这篇文章时学到了一些新技巧。我不确定自己是被启迪了还是永远被毁了。 - superluminary

如果你的软件除了洗牌数组之外还有其他有用的功能，微观优化并不重要。如果你的软件只是在洗牌数组而没有其他效果，那么这就是浪费人类时间。‍♂️ - meandre

可以将其重写为一个更短的函数，如下所示：function fy(a,b,c=a.length){while(c)b=Math.random()*(--c+1)|0,[a[c],a[b]]=[a[b],a[c]]} - undefined

Answer 8

原地打乱数组

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 纯递归

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

使用数组 map 方法的 ES6 纯函数

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

使用数组reduce的ES6纯函数

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

- Ben Carp

---

那么，ES6（ES2015）在哪里？[array[i]，array[rand]] = [array[rand]，array[i]]？也许您可以概述一下它的工作原理。为什么选择向下迭代？ - sheriffderek

@sheriffderek 是的，我使用的 ES6 功能是同时赋值两个变量，这使我们能够在一行代码中交换两个变量。 - Ben Carp

感谢@sheriffderek提出的升序算法。升序算法可以通过归纳证明。 - Ben Carp

Answer 9

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

请查看评论和https://dev59.com/IXE95IYBdhLWcg3wHqMV#18650169。这里保留此回答供参考，因为这个想法并不罕见。

---

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

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>

- Kris Selbekk

---

不错，但是它每次都能生成完全随机的元素吗？ - Playdome.io

我不太确定我是否正确理解了你的意思。这种方法确实会在每次调用排序数组时以一种随机的方式（虽然是伪随机）打乱数组 - 这不是一种稳定的排序，原因很明显。 - Kris Selbekk

出于与 https://dev59.com/IXE95IYBdhLWcg3wHqMV#18650169 中解释的相同原因，这样做更有可能让早期元素留在数组的开头。 - AlexC

当您需要对数组进行混淆，但不太关心结果是否具有学术上可证明的随机性时，这是一个很好的、简单的一行代码。有时，追求完美的最后一点要花费比它所值得的时间更多。 - Daniel Griscom

如果这个能够正常工作就太好了，但事实并非如此。由于快速搜索的工作方式，不一致的比较器很可能会使数组元素保持接近其原始位置。你的数组将不会被打乱。 - superluminary

Answer 10

警告！
不建议将此答案用于随机化大型数组、密码学或任何需要真正随机性的应用程序，因为它具有偏差和低效率。元素位置只是半随机化的，并且它们倾向于保持接近其原始位置。请参见https://dev59.com/IXE95IYBdhLWcg3wHqMV#18650169。

---

您可以使用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);

- Rafi Henig

---

这个是否具有公正性？ - Juzer Ali

什么？这太无意义了。它几乎没有可能保持元素不变（随机生成恰好0.5）。 - user151496

我建议删除这个答案。答案不正确，也不是新的。另一个错误的答案留作参考，所以我认为这个可以被删除 :-) - Ben Carp

@BenCarp 首先，非常感谢您的评论和建议！它们将被审查和考虑（至于您声称我的答案并不新颖，我相信它与您所提到的那个不同）。 - Rafi Henig

@RafiHenig 另一个答案的区别非常非常微小。鉴于两者都是不正确的，我看不出有什么意义。 - Ben Carp