Schnelle Sortierung, auch als Partitionierung und Tauschsortierung bekannt. Ein schneller Sortieralgorithmus, der mit der Strategie der Teilen und Eroberung implementiert ist.
In diesem Artikel wird hauptsächlich über die Verwendung von JavaScript zur Implementierung der schnellen Sortierung von In-Place-Ideen gesprochen
Methoden teilen und behandeln:
In der Informatik ist die Aufteilung und die Eroberermethode ein sehr wichtiges Algorithmus -Paradigma, das auf mehreren Zweigreensionen basiert. Die buchstäbliche Erklärung ist "teilt und erobert", was bedeutet, ein komplexes Problem in zwei oder mehr identische oder ähnliche Unterprobleme zu unterteilen, bis das Ende des Unterproblems einfach und direkt gelöst werden kann, und die Lösung des ursprünglichen Problems ist der Zusammenschluss der Lösungen des Unterproblems. (Auszug aus Wikipedia)
Schnelle Sortieridee
Geben Sie ein Element im Array als Lineal an, platzieren Sie das größere als es und setzen Sie das kleinere als es vor dem Element. Wiederholen Sie dies, bis alle in positiver Reihenfolge angeordnet sind.
Die schnelle Sortierung ist in drei Schritte unterteilt:
Wählen Sie einen Benchmark: Wählen Sie ein Element als Benchmark in der Datenstruktur (Pivot) aus.
Partition: Beziehen Sie sich auf die Größe des Referenzelement -Werts und teilen Sie den ungeordneten Bereich auf. Alle Daten, die kleiner als das Referenzelement sind, werden in einem Intervall platziert, und alle Daten, die größer als das Referenzelement sind, werden in einem anderen Intervall platziert. Nach Abschluss der Partitionoperation ist die Position des Referenzelements die Position, in der es nach der endgültigen Sortierung sein sollte.
Rekursion: Rufen Sie die Algorithmen in Schritt 1 und Schritt 2 zum ersten Mal rekursiv auf, bis in allen ungeordneten Intervallen nur noch ein Element übrig ist.
Lassen Sie uns nun über die gemeinsamen Implementierungsmethoden sprechen (kein In-Place-Algorithmus wird verwendet)
Funktion QuickSort (arr) {if (arr.length <= 1) return; // Bitte der Ziffern -Benchmark, der der Mitte des Arrays am nächsten liegt, nehmen ungerade Zahlen und sogar Zahlen unterschiedlich, aber ich denke nicht. Natürlich können Sie die erste oder die letzte Zahl als Benchmark auswählen, und es gibt hier keine zu viel Beschreibung var pivotIndex = math.floor (arr.länge/2); var pivot = arr.spleplice (pivotindex, 1) [0]; // linke und linke Intervalle werden verwendet, um Sortenzahlen zu speichern. . {rechts.push (arr [i]); console.log ('right:' + (arr [i])}}} // Der Hakenoperator wird hier verwendet, um das linke Intervall, die Referenz und das rechte Intervall in ein neues Array zu spleißen // dann rekursiv 1 und 2 Schritte, bis alle nicht angeordneten Intervalle links und das regelmäßige Ende des Endes (links) (links) (Pival) und das regelmäßige Ende (Pivot) (Pivot) (Pivot) (Pivot) (Pivot) (Pival. Quicksort (rechts));} var arr = [14, 3, 15, 7, 2, 76, 11]; Konsole.Log (Quicksort (arr));/** Wenn die Basis 7 ist, wird die erste Partition mit zwei Untergruppen links und rechts erhalten [3, 2,] 7, 15, 76, 76]. Die Sortierung der linken Untergruppe endet* mit der Referenz als 76, die rechte Untergruppe wird geteilt und sortiert, um zu erhalten [14, 15, 11] 76*. Zu diesem Zeitpunkt ist das oben genannte [14, 15, 11] geteilt und sortiert in das obige [14, 15, 11]. Es ist geteilt und sortiert in die oben genannte [14, 11]. Die oben genannten Sortierungen. [14, 11] ist geteilt und sortiert in das oben genannte [11] wird geteilt und in die Basis 11, 11 [14]*In allen ungeordneten Intervallen und dem rekursiven Ende **/ sind nur ein Element übrig gebliebenDurch Bruchpunkt -Debugging können die Ergebnisse erzielt werden.
Nachteile:
Es erfordert zusätzlichen Speicherplatz von ω (n), was so schlecht ist wie das Zusammenführen der Sortierung. In einer Produktionsumgebung ist zusätzlicher Speicherplatz erforderlich, was die Leistung beeinflusst.
Gleichzeitig denken viele Leute, dass das oben genannte eine sehr schnelle Art ist. Im Folgenden muss daher die schnelle Sortierung des In-Place-Algorithmus empfohlen werden
Informationen zum In-situ-Algorithmus finden Sie in Wikipedia. Die Schüler, die unter der Wand stehen, ähneln Baidu.
Einort
Die schnelle Sortierung wird im Allgemeinen mit Rekursion implementiert. Das Wichtigste ist die Teilungssegmentierungsfunktion, die das Array in zwei Teile unterteilt, einer ist kleiner als Pivot und der andere größer als Pivot. Das spezifische Prinzip wurde oben erwähnt
Funktion QuickSort (arr) {// Swap -Funktionswap (arr, a, b) {var temp = arr [a]; arr [a] = arr [b]; arr [b] = temp;} // Partition Funktion Partition (arr, links, rechts) {/*** Am Anfang kennen Sie nicht. = arr [rechts];/*** Beim Speichern von Elementen kleiner als Pivot befinden sie sich neben dem vorherigen Element, ansonsten kann das in der Spalt gespeicherte Element größer als Pivot sein. */var storeIndex = links; für (var i = links; i <rechts; i ++) {if (arr [i] <pivot) {/*** durch das Array und finde das Element kleiner als Pivot, (Elemente größer als Pivot werden übersprungen)* Legen Sie das Element, das das Element erhalten hat, das Element erhalten. ausgetauscht*/swap (arr, storeIndex, i); storeIndex ++;}} // Schließlich: Swap Pivot auf StoreIndex, platzieren Sie das Benchmark -Element an der endgültigen korrekten Position Swap (arr, rechts, storeIndex); return storeIndex; 1); sort (arr, storeIndex + 1, rechts);} sortieren (arr, 0, arr.Length - 1); return arr;} console.log (QuickSort ([8, 4, 90, 8, 34, 67, 1, 26, 17]);Trennungsoptimierung
Bei der Auswahl verschiedener Benchmarks können sorgfältige Schüler hier fragen, ob es unterschiedliche Leistungsleistung gibt. Die Antwort lautet ja, aber weil ich eine Front-End-Person bin und nicht viel über den Algorithmus weiß, bleibt diese Grube mächtigen Menschen überlassen, sich zu füllen.
Komplexität
Schnelles Sortieren ist der schnellste Sortieralgorithmus, und seine Zeitkomplexität ist O (log n)
In der durchschnittlichen Situation erfordert die Reihenfolge von N -Elementen (n log n) Vergleiche. Im schlimmsten Fall sind Vergleiche (n2) Vergleiche erforderlich.
https://github.com/lyz0106/
Das obige ist die Schnellsortiermethode der vom Editor eingeführten Ideen für die JavaScript-Implementierung. Ich hoffe, es wird für alle hilfreich sein. Wenn Sie Fragen haben, hinterlassen Sie mir bitte eine Nachricht. Der Herausgeber wird Ihnen rechtzeitig antworten. Vielen Dank für Ihre Unterstützung für die Wulin Network -Website!