Tajuk yang ditulis semula: Ketahui cara mengisih (kocok) tatasusunan JavaScript secara rawak

Question

Saya mempunyai tatasusunan seperti ini:

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

Bagaimana cara saya mengacak/kocoknya?

Answer 1

Ini ialah pelaksanaan JavaScript Durstenfeld shuffle, yang merupakan versi optimum algoritma 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 melukis secara rawak daripada dek kad.

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

Masa berjalan bagi

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

---

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. Berikut ialah bentuk yang lebih pendek bagi fungsi yang sama yang menggunakan fungsi 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);