Kuasai kaedah pengisihan rawak (shuffling) tatasusunan dalam JavaScript

Question

Saya mempunyai tatasusunan seperti ini:

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

Bagaimana cara saya mengacak/kocoknya?

Answer 1

Berikut ialah pelaksanaan JavaScript Durstenfeld shuffle, yang merupakan versi dioptimumkan 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;
    }
}

Ia memilih elemen rawak untuk setiap elemen tatasusunan asal dan mengecualikannya daripada cabutan seterusnya, sama seperti memilih secara rawak daripada dek kad.

Kaedah penyingkiran pintar ini menukar elemen yang dipilih dengan elemen semasa, kemudian memilih elemen rawak seterusnya daripada elemen yang tinggal, menggelung ke belakang dengan kecekapan optimum, memastikan pemilihan rawak dipermudahkan (ia sentiasa boleh bermula dari 0), dengan itu melangkau elemen terakhir.

Masa berjalan bagi

algoritma ialah salinan kaedah O(n)。需要注意的是，这个洗牌是原地进行的，所以如果你不想修改原始数组，请先使用.slice(0).

---

EDIT: Dikemas kini kepada ES6/ECMAScript 2015

ES6 baharu membolehkan kami menetapkan dua pembolehubah pada masa yang sama. Ini amat mudah apabila kita ingin menukar nilai dua pembolehubah, kerana kita boleh melakukannya dalam satu baris kod. Ini adalah bentuk yang lebih pendek daripada fungsi yang sama yang menggunakan ciri ini.

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

Malah, algoritma shuffling yang tidak berat sebelah ialah algoritma shuffling Fisher-Yates (aka Knuth) .

Anda boleh melihat visualisasi yang hebat di sini (siaran asal dipautkan di sini )

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