JS-Random-Shuffling-Algorithmus-Array, zufällige Sortierung_Javascript-Fähigkeiten

Empfohlene Lektüre: JavaScript-Studiennotizen: Hinzufügen, Löschen, Ändern und Überprüfen von Arrays

JavaScript Study Notes Array Sum Method

JavaScript Study Notes Array Random Sorting

Shuffling-Algorithmus ist ein relativ anschaulicher Begriff, der es im Wesentlichen ermöglicht, die Elemente in einem Array zufällig anzuordnen. Zum Beispiel haben wir ein Array wie in der folgenden Abbildung gezeigt. Die Länge des Arrays beträgt 9 und die Werte der Elemente im Array sind 1 bis 9:

Ausgehend vom obigen Array müssen wir die Reihenfolge der Elemente im Array ändern:

Code-Implementierung

Der Fisher-Yates-Shuffle-Eintrag auf Wikipedia bietet eine detaillierte Einführung in den Shuffle-Algorithmus. Der unten gezeigte Algorithmus basiert ebenfalls auf der Theorie:

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

Im obigen Code haben wir eine shffle()-Methode erstellt, die verwendet wird, um die Elemente innerhalb des Arrays zufällig anzuordnen. Darüber hinaus haben wir diese Methode unter dem Prototyp des Array-Objekts gemountet, sodass jedes Array diese Methode direkt aufrufen kann:

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

Wie es funktioniert

Nachdem wir den Code gelesen haben, wollen wir sehen, was er mit dem Array macht. Zuerst wählt diese Methode das letzte Element des Arrays aus:

Bestimmen Sie als Nächstes den Bereich für die Auswahl zufälliger Elemente. Vom ersten Element des Arrays bis zum im vorherigen Schritt ausgewählten Element gehören sie alle zu diesem Bereich:

Wählen Sie nach der Bestimmung des Bereichs zufällig eine Zahl daraus aus, vorausgesetzt, dass das zufällig ausgewählte Element 4 ist:

Dann vertauschen Sie die Werte des letzten Elements und des zufällig ausgewählten Elements:

Nachdem der obige Austausch abgeschlossen ist, entspricht dies dem Abschluss der zufälligen Verarbeitung des letzten Elements des Arrays. Wählen Sie als Nächstes das vorletzte Element im Array aus:

Der Grund, warum wir es von hinten nach vorne verarbeiten, besteht darin, dass es einfacher ist, den Bereich der Zufallsauswahl zu bestimmen. Dieses Mal gehen wir davon aus, dass das zufällig erhaltene Element 2:

ist

Dann tauschen Sie die Werte des vorletzten Elements und des zweiten Elements aus, um die zufällige Anordnung des vorletzten Elements zu vervollständigen. Wählen Sie dann das drittletzte Element aus und wiederholen Sie den vorherigen Vorgang:

Der Rest ist repetitive Arbeit, daher werde ich nicht viel darüber erzählen.

Code analysieren

Im vorherigen Abschnitt habe ich eine Illustration verwendet, um den Mischvorgang zu demonstrieren. Schauen wir uns nun den Mischvorgang anhand des Codes selbst an. Beginnen wir mit der Shuffle-Funktion:

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

Die Shuffle-Funktion wird unter dem Prototyp des Array-Objekts bereitgestellt, sodass das Array die Funktion einfach direkt aufrufen kann. Innerhalb der Shuffle-Funktion bezieht sich dies auf das Array, in dem der Shuffle aufgerufen wird:

var input = this;

Im obigen Code verweise ich darauf mit einer neuen Variablen, bei der es sich um das Array handelt, für das die Shuffle-Funktion aufgerufen wird. Schauen wir uns als Nächstes an, was in der for-Schleife geschieht:

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

Diese Schleife wird verwendet, um alle Elemente in allen Arrays zu durchlaufen und zufällige Austausche durchzuführen. Beachten Sie, dass die Durchlaufreihenfolge von hinten nach vorne erfolgt, d. h. beginnen Sie mit dem Element an der Position input.length-1, bis Sie zum ersten Element im Array gelangen. Die Position während der Durchquerung wird durch die Variable i angegeben.

Die Variable i hier ist das ausgewählte Element in der Legende oben:

Mischalgorithmus

Als nächstes werden zwei Codezeilen verwendet, um ein zufälliges Element im angegebenen Bereich auszuwählen:

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随机洗牌算法之给数组随机排序的相关叙述，希望对大家有所帮助！