Maîtriser la méthode de tri aléatoire (shuffling) des tableaux en JavaScript

Question

J'ai un tableau comme celui-ci :

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

Comment puis-je le randomiser/le mélanger ?

Answer 1

Voici une implémentation JavaScript de Durstenfeld shuffle, qui est une version optimisée de 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;
    }
}

Il sélectionne un élément aléatoire pour chaque élément du tableau d'origine et l'exclut du prochain tirage, tout comme une sélection aléatoire dans un jeu de cartes.

Cette méthode d'élimination intelligente échange l'élément sélectionné avec l'élément actuel, puis sélectionne l'élément aléatoire suivant parmi les éléments restants, en bouclant vers l'arrière avec une efficacité optimale, garantissant que la sélection aléatoire est simplifiée (elle peut toujours commencer à partir de 0), sautant ainsi le dernier élément.

Le temps d'exécution de l'algorithme

est une copie de la méthode O(n)。需要注意的是，这个洗牌是原地进行的，所以如果你不想修改原始数组，请先使用.slice(0).

---

EDIT : Mise à jour vers ES6/ECMAScript 2015

Le nouvel ES6 nous permet d'attribuer deux variables en même temps. Ceci est particulièrement pratique lorsque nous voulons échanger les valeurs de deux variables, car nous pouvons le faire en une seule ligne de code. Il s'agit d'une forme plus courte de la même fonction qui utilise cette fonctionnalité.

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

En fait, l'algorithme de brassage impartial est l'algorithme de brassage Fisher-Yates (alias Knuth).

Vous pouvez voir une superbe visualisation ici (post original lié ici )

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