Detaillierte Erläuterung des Algorithmus zur Implementierung von Quicksort in Javascript_Javascript-Kenntnissen

Derzeit gibt es etwa sieben oder acht gängigste Sortieralgorithmen, von denen „Quicksort“ der am weitesten verbreitete und schnellere ist. Es wurde 1960 vom Turing-Preisträger C. A. R. Hoare (1934--) vorgeschlagen.

Die Idee der „Schnellsortierung“ ist sehr einfach Der gesamte Sortiervorgang erfordert nur drei Schritte:

(1) Wählen Sie im Datensatz ein Element als „Pivot“ aus.

(2) Alle Elemente, die kleiner als „base“ sind, werden nach links von „base“ verschoben; alle Elemente, die größer als „base“ sind, werden nach rechts von „base“ verschoben.

(3) Wiederholen Sie den ersten und zweiten Schritt für die beiden Teilmengen links und rechts der „Grundlinie“, bis in allen Teilmengen nur noch ein Element übrig bleibt.

Zum Beispiel gibt es einen Datensatz {85, 24, 63, 45, 17, 31, 96, 50}.

Der erste Schritt besteht darin, das mittlere Element 45 als „Grundlinie“ auszuwählen. (Der Basiswert kann beliebig gewählt werden, die Wahl eines Wertes in der Mitte ist jedoch einfacher zu verstehen.)

Der zweite Schritt besteht darin, jedes Element mit der „Grundlinie“ zu vergleichen, um zwei Teilmengen zu bilden, eine „weniger als 45“ und die andere „größer oder gleich 45“.

Der dritte Schritt besteht darin, den ersten und zweiten Schritt für die beiden Teilmengen zu wiederholen, bis nur noch ein Element in allen Teilmengen übrig bleibt.

Das Folgende bezieht sich auf die Informationen im Internet und verwendet die Javascript-Sprache, um den oben genannten Algorithmus zu implementieren.

Definieren Sie zunächst eine QuickSort-Funktion, deren Parameter ein Array ist.

var quickSort = function(arr) {
};

Überprüfen Sie dann die Anzahl der Elemente im Array und geben Sie sie zurück, wenn sie kleiner oder gleich 1 ist.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
};

Als nächstes wählen Sie den „Pivot“ aus, trennen ihn vom ursprünglichen Array und definieren dann zwei leere Arrays, um zwei Teilmengen zu speichern, eine links und eine rechts.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2) ;
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
};

Dann beginnen Sie mit dem Durchlaufen des Arrays und fügen Sie Elemente, die kleiner als die „Grundlinie“ sind, in die linke Teilmenge und Elemente, die größer als die „Grundlinie“ sind, in die rechte Teilmenge ein.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2) ;
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
};

Verwenden Sie abschließend die Rekursion, um diesen Vorgang zu wiederholen und das sortierte Array zu erhalten.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1);
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat(pivot, quickSort(right));
};
 
var dataArray = [85,24,63,45,17,31,96,50];
console.log(dataArray.join(","));
console.log(quickSort(dataArray).join(","));

Ich hoffe, dass dieser Artikel für das JavaScript-Programmierdesign aller hilfreich sein wird.