Beherrschen Sie die Methode der zufälligen Sortierung (Shuffling) von Arrays in JavaScript

Question

Ich habe ein Array wie dieses:

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

Wie kann ich es zufällig sortieren/mischen?

Answer 1

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

/* 使用Durstenfeld shuffle算法原地随机排序数组 */
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 2

事实上，无偏的洗牌算法是Fisher-Yates（又称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);