掌握JavaScript中數組隨機排序（洗牌）的方法

Question

我有一個像這樣的陣列：

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

如何對它進行隨機化/洗牌？

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