Wie kann man ein JavaScript-Array randomisieren (mischen)?

Der de-facto unvoreingenommene Shuffle-Algorithmus ist der Fisher-Yates (alias Knuth) Shuffle.

Siehe https://github.com/coolaj86/knuth-shuffle

Sie können eine großartige Visualisierung hier sehen (und den ursprünglichen Beitrag der mit diesem verlinkt ist)

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

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

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

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

  return array;
}

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

Einige weitere Informationen über den verwendeten Algorithmus.

Hier ist eine JavaScript-Implementierung des Durstenfeld shuffle, einer computeroptimierten Version von Fisher-Yates:

/**
 * Randomize array element order 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;
    }
}

Der Fisher-Yates-Algorithmus funktioniert, indem er für jedes ursprüngliche Array-Element ein Zufallselement auswählt und es dann bei der nächsten Ziehung ausschließt. Genau wie bei der zufälligen Auswahl aus einem Kartenspiel.

Dieser Ausschluss erfolgt auf eine clevere Art und Weise (die von Durstenfeld für die Verwendung durch Computer erfunden wurde), indem das ausgewählte Element mit dem aktuellen Element vertauscht wird und dann das nächste Zufallselement aus dem Rest ausgewählt wird. Um eine optimale Effizienz zu erreichen, läuft die Schleife rückwärts, so dass die Zufallsauswahl vereinfacht wird (sie kann immer bei 0 beginnen) und das letzte Element übersprungen wird, weil es keine andere Auswahlmöglichkeit mehr gibt.

Die Laufzeit dieses Algorithmus ist O(n). Beachten Sie, dass das Mischen an Ort und Stelle erfolgt. Wenn Sie also das ursprüngliche Array nicht verändern wollen, erstellen Sie zuerst eine Kopie davon mit .slice(0).

Aktualisierung auf ES6 / ECMAScript 2015

Das neue ES6 erlaubt es uns, zwei Variablen gleichzeitig zuzuweisen. Dies ist besonders praktisch, wenn wir die Werte von zwei Variablen vertauschen wollen, da wir dies in einer einzigen Codezeile tun können. Hier ist eine kürzere Form der gleichen Funktion, die diese Funktion nutzt.

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

Man könnte (oder sollte) es als Protoyp von Array verwenden:

Von 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;
}