Tableau d'algorithmes de brassage aléatoire JS compétences de tri aléatoire_javascript

Lecture recommandée : Notes d'étude JavaScript : Ajouter, supprimer, modifier et vérifier des tableaux

Notes d'étude JavaScript Méthode de somme de tableau

Tableau de notes d'étude JavaScript, tri aléatoire

L'algorithme de brassage est un terme relativement vivant, qui permet essentiellement aux éléments d'un tableau d'être disposés de manière aléatoire. Par exemple, nous avons un tableau comme le montre la figure ci-dessous. La longueur du tableau est de 9 et les valeurs des éléments du tableau sont de 1 à 9 :

.

À partir du tableau ci-dessus, ce que nous devons faire est de perturber l'ordre des éléments dans le tableau :

Mise en œuvre du code

L'entrée de lecture aléatoire Fisher-Yates sur Wikipédia fournit une introduction détaillée à l'algorithme de lecture aléatoire. L'algorithme démontré ci-dessous est également écrit sur la base de la théorie :

Array.prototype.shuffle = function() {
var input = this;
for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1)); 
var itemAtIndex = input[randomIndex]; 
input[randomIndex] = input[i]; 
input[i] = itemAtIndex;
}
return input;
}
var tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
tempArray.shuffle();
// and the result is...
alert(tempArray); 

Dans le code ci-dessus, nous avons créé une méthode shffle(), qui est utilisée pour organiser aléatoirement les éléments dans le tableau. De plus, nous avons monté cette méthode sous le prototype de l'objet Array, donc n'importe quel tableau peut appeler cette méthode directement :

var tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
tempArray.shuffle(); 

Comment ça marche

Après avoir lu le code, voyons ce qu'il fait au tableau. Tout d'abord, cette méthode sélectionne le dernier élément du tableau :

Ensuite, déterminez la plage de sélection des éléments aléatoires. Du premier élément du tableau à l'élément sélectionné à l'étape précédente, ils appartiennent tous à cette plage :

Après avoir déterminé la plage, sélectionnez-en un nombre au hasard, en supposant que l'élément sélectionné au hasard est 4 :

Échangez ensuite les valeurs du dernier élément et de l'élément sélectionné aléatoirement :

Une fois l'échange ci-dessus terminé, cela équivaut à terminer le traitement aléatoire du dernier élément du tableau. Sélectionnez ensuite l'avant-dernier élément du tableau :

La raison pour laquelle nous le traitons de l'arrière vers l'avant est qu'il est plus facile de déterminer la plage de sélection aléatoire. Cette fois, nous supposons que l'élément obtenu aléatoirement est 2 :

Échangez ensuite les valeurs de l'avant-dernier élément et du 2ème élément pour compléter la disposition aléatoire de l'avant-dernier élément. Sélectionnez ensuite l'avant-dernier élément et répétez l'opération précédente :

Le reste est un travail répétitif, je ne le présenterai donc pas beaucoup.

Analyse du code

Dans la section précédente, j'ai utilisé une illustration pour démontrer le processus de brassage. Examinons maintenant le processus de brassage à partir du code lui-même. Commençons par la fonction shuffle :

Array.prototype.shuffle = function() {
var input = this;
for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1)); 
var itemAtIndex = input[randomIndex]; 
input[randomIndex] = input[i]; 
input[i] = itemAtIndex;
}
return input;
} 

La fonction shuffle est montée sous le prototype de l'objet Array, ce qui permet au tableau d'appeler facilement la fonction directement. Dans la fonction shuffle, cela fait référence au tableau dans lequel le shuffle est appelé :

var input = this;

Dans le code ci-dessus, je fais référence à cela avec une nouvelle variable, qui est le tableau sur lequel la fonction shuffle est appelée. Voyons ensuite ce qui se fait dans la boucle for :

for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1)); 
var itemAtIndex = input[randomIndex]; 
input[randomIndex] = input[i]; 
input[i] = itemAtIndex;
}

Cette boucle est utilisée pour parcourir tous les éléments de tous les tableaux et effectuer des échanges aléatoires. Notez que l'ordre de parcours va de l'arrière vers l'avant, c'est-à-dire en commençant par l'élément à la position input.length-1 jusqu'à ce que le premier élément du tableau soit parcouru. La position pendant le parcours est spécifiée par la variable i.

La variable i ici est l'élément sélectionné dans la légende ci-dessus :

Algorithme de brassage

Ensuite, deux lignes de code sont utilisées pour sélectionner un élément aléatoire dans la plage spécifiée :

var randomIndex = Math.floor(Math.random()*(i+1)); 
var itemAtIndex = input[randomIndex];

变量 randomIndex 存储了一个随机数，该随机数可以用作数组的索引，进而提取一个随机元素。注意，该随机数的最大值并不是数组的长度，而是变量 i 的值。

确定了随机元素的索引之后，用新的变量保存该元素的值，然后交换选中元素和随机元素的值：

var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i]; 
input[i] = itemAtIndex;

在这三行代码中，第一行使用新的变量保存了随机元素的值；第二行将选中元素 input[i] 的值赋给随机元素 input[randomIndex]；第三行就随机元素的值 itemAtIndex 赋给选中元素 input[i]。本质上是一个互换两个元素的值的过程，并不难理解。

至此，循环内的逻辑就介绍完了，剩下的都是重复操作。

随机性测试

上图是使用 Highcharts 制作的随机性测试图表，以可视化的方式校验本文中洗牌算法的随机性。每次刷新页面都会重新计算和生成该图表。

生成上图的数据是这样计算而来的：首先创建一个数组（上图使用的数组为 [0, 1, 2 ... 18, 19, 20]），然后使用本文中的洗牌算法重新排序，排序完成后记录每一个元素的值……以此步骤执行 100000 次，最后对同一索引位置上的数值进行求和。如此执行 10000 次之后，索引之间的总值应该相差不大。

由计算可得：

以上内容是小编给大家介绍的JS随机洗牌算法之给数组随机排序的相关叙述，希望对大家有所帮助！