Die Idee des "schnellen Sortierens" ist sehr einfach, und der gesamte Sortiervorgang erfordert nur drei Schritte:
(1) Wählen Sie im Datensatz ein Element als "Basis" (Pivot) aus.
(2) alle Elemente, die kleiner als die "Referenz" sind, werden links von der "Referenz" bewegt. Alle Elemente, die größer als die "Referenz" sind, werden rechts von der "Referenz" bewegt.
(3) Wiederholen Sie für die beiden Untergruppen links und rechts in der "Grundlinie" die ersten und zweiten Schritte, bis in allen Teilmengen nur noch ein Element übrig ist.
Zum Beispiel gibt es jetzt einen Datensatz {85, 24, 63, 45, 17, 31, 96, 50}. Wie sortiere ich es?
Wählen Sie im ersten Schritt das Zwischenelement 45 als "Basis" aus. (Der Referenzwert kann willkürlich ausgewählt werden, aber die Auswahl des Zwischenwerts ist einfacher zu verstehen.)
Der zweite Schritt besteht darin, jedes Element mit der "Basis" zu vergleichen, um zwei Teilmengen zu bilden. Einer ist "weniger als 45" und der andere "größer als 45".
Der dritte Schritt besteht darin, die ersten und zweiten Schritte für die beiden Teilmengen zu wiederholen, bis in allen Teilmengen nur noch ein Element übrig ist.
Das Folgende ist ein Verweis auf die Online -Informationen (hier und hier), um den obigen Algorithmus in JavaScript -Sprache zu implementieren.
Definieren Sie zunächst eine QuickSort -Funktion, deren Parameter ein Array sind.
var quicksort = function (arr) {};Überprüfen Sie dann die Anzahl der Elemente im Array, und wenn es kleiner oder gleich 1 ist, wird es zurückgegeben.
var quicksort = function (arr) {if (arr.length <= 1) {return arr; }};Wählen Sie als nächstes "Pivot" und trennen Sie es vom ursprünglichen Array und definieren Sie dann zwei leere Arrays, um zwei Untergruppen von einem linken und eines rechts zu speichern.
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 links = []; var rechts = [];};Beginnen Sie dann, das Array zu durchqueren, Elemente kleiner als die "Basis" in die Untergruppe links und Elemente, die größer als die Basis in die Teilmenge rechts sind.
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 links = []; var rechts = []; für (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {links.push (arr [i]); } else {rechts.push (arr [i]); }}};Wiederholen Sie diesen Vorgang schließlich kontinuierlich mit Rekursion, um 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) [0]; var links = []; var rechts = []; für (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {links.push (arr [i]); } else {rechts.push (arr [i]); }} return QuickSort (links) .Concat ([Pivot], QuickSort (rechts));};Rufen Sie bei der Verwendung einfach QuickSort () an.
Das obige ist eine detaillierte Erläuterung des QuickSort -Algorithmus -Beispiels der vom Editor vorgestellten JavaScript -Algorithmus -Serie. Ich hoffe, es wird Ihnen hilfreich sein. Wenn Sie Fragen haben, hinterlassen Sie mir bitte eine Nachricht und der Editor wird Ihnen rechtzeitig antworten. Vielen Dank für Ihre Unterstützung auf der Wulin.com -Website!