Erlernen des Schnellsortierungsalgorithmus
Quick Sort ist einer der effizientesten Algorithmen und verwendet die Divide-and-Conquer-Technik zum Sortieren von Arrays.
So funktioniert die Schnellsortierung
Die Hauptidee von Quick Sort besteht darin, einem Element nach dem anderen dabei zu helfen, an die richtige Position in einem unsortierten Array zu gelangen. Dieses Element wird Pivot genannt.
Das Drehelement befindet sich in der richtigen Position, wenn:
- Alle Elemente links davon sind kleiner.
- Alle Elemente rechts davon sind größer.
Es spielt keine Rolle, ob die Zahlen links oder rechts schon sortiert sind. Wichtig ist, dass sich der Drehpunkt an der richtigen Position im Array befindet.
// examples of the pivot 23 positioned correctly in the array: [3, 5, 6, 12, 23, 25, 24, 30] [6, 12, 5, 3, 23, 24, 30, 25] [3, 6, 5, 12, 23, 30, 25, 24]
All dies sind gültige Ausgaben eines Arrays, bei dem der Pivot 23 ist.
Die richtige Position des Drehpunkts finden
Quick Sort hilft dem Pivot, seine richtige Position im Array zu finden. Wenn sich der Pivot beispielsweise am Anfang des Arrays befindet, aber nicht die kleinste Zahl ist, bestimmt Quick Sort, dass er sich um 5 Schritte bewegen muss, um Platz für die 5 kleineren Elemente im Array zu schaffen – vorausgesetzt, es gibt 5 solcher Elemente Zahlen.
Nehmen wir an, wir haben das Array: [10, 4, 15, 6, 23, 40, 1, 17, 7, 8] und 10 ist der Drehpunkt:
An diesem Punkt:
- Die Nummer 10 weiß nicht, ob sie sich an der richtigen Position befindet und wie viele Schritte sie zurücklegen muss, um dorthin zu gelangen. Quick Sort beginnt mit dem Vergleich von 10 mit dem Wert am nächsten Index.
- Wenn Quick Sort erkennt, dass 4 kleiner ist, zeichnet es auf, dass sich der Pivot einen Schritt nach vorne bewegen muss, damit 4 davor kommen kann.
- Also numberOfStepsToMove erhöht sich um 1.
Als nächstes beträgt der Wert bei Index 2 15, was größer als 10 ist. Da keine Anpassung erforderlich ist, Schnellsortierung behält die Schrittanzahl unverändert bei und geht zum nächsten Element im Array über.
Beim nächsten Index ist der Wert 6, was kleiner als 10 ist. Quick Sort erhöht die Schrittzahl auf 2, da der Pivot nun Platz für zwei kleinere Zahlen schaffen muss: 4 und 6 .
Jetzt muss 6 durch 15 ersetzt werden, damit die kleineren Zahlen auf der linken Seite des Arrays nebeneinander bleiben. Wir tauschen die Zahlen basierend auf den aktuellen Index- und numberOfStepsToMove-Werten aus.
Quick Sort durchläuft weiterhin das Array und erhöht die Zahl „NumberOfStepsToMove“ basierend darauf, wie viele Zahlen kleiner als der Pivot sind. Dadurch lässt sich ermitteln, wie weit sich der Drehpunkt in die richtige Position bewegen muss.
Die numberOfStepsToMove ändert sich bei 23 oder 40 nicht, da beide Werte größer als der Pivot sind und im Array nicht davor stehen sollten:
Wenn Quick Sort nun eine Schleife zum Wert 1 an Index 6 durchläuft, erhöht sich numberOfStepsToMove auf 3 und tauscht die Zahl an Index 3 aus:
Quick Sort setzt diesen Vorgang fort, bis das Ende des Arrays erreicht ist:
Da wir nun das Ende des Arrays erreicht haben, wissen wir, dass es 5 Zahlen gibt, die kleiner als 10 sind. Daher muss sich der Drehpunkt (10) 5 Schritte nach vorne zu seiner richtigen Position bewegen, wo er größer als alle ist Zahlen davor.
Mal sehen, wie das im Code aussieht:
// examples of the pivot 23 positioned correctly in the array: [3, 5, 6, 12, 23, 25, 24, 30] [6, 12, 5, 3, 23, 24, 30, 25] [3, 6, 5, 12, 23, 30, 25, 24]
Da wir nun eine Funktion haben, die uns hilft, die Position des Pivots zu finden, sehen wir uns an, wie Qucik Sort das Array in kleinere Arrays aufteilt und die Funktion getNumberOfStepsToMove verwendet, um alle Array-Elemente zu platzieren.
const getNumberOfStepsToMove = (arr, start = 0, end = arr.length - 1) => { let numberOfStepsToMove = start; // we're picking the first element in the array as the pivot const pivot = arr[start]; // start checking the next elements to the pivot for (let i = start + 1; i <= end; i++) { // is the current number less than the pivot? if (arr[i] < pivot) { // yes - so w should increase numberOfStepsToMove // or the new index of the pivot numberOfStepsToMove++; // now swap the number at the index of numberOfStepsToMove with the smaller one [arr[i], arr[numberOfStepsToMove]] = [arr[numberOfStepsToMove], arr[i]]; } else { // what if it's greater? // do nothing -- we need to move on to the next number // to check if we have more numbers less that pivot to increase numberOfStepsToMove or not } } // now we know the pivot is at arr[start] and we know that it needs to move numberOfStepsToMove // so we swap the numbers to place the pivot number to its correct position [arr[start], arr[numberOfStepsToMove]] = [ arr[numberOfStepsToMove], arr[start], ]; return numberOfStepsToMove; };
Schnellsortierung nutzt Rekursion, um das Array effizient in kleinere Unterarrays zu unterteilen und sicherzustellen, dass Elemente sortiert werden, indem sie mit einem Pivot verglichen werden.
function quickSort(arr, left = 0, right = arr.length - 1) { // pivotIndex the new index of the pivot in in the array // in our array example, at the first call this will be 5, because we are checking 10 as the pivot // on the whole array let pivotIndex = getNumberOfStepsToMove(arr, left, right); }
- Der Algorithmus sortiert rekursiv das linke Subarray, das Elemente enthält, die kleiner als der Pivot sind.
- Die Rekursion stoppt, wenn das Subarray ein oder kein Element enthält, da es bereits sortiert ist.
Jetzt müssen wir den gleichen Vorgang auf der rechten Seite des Arrays durchführen:
// examples of the pivot 23 positioned correctly in the array: [3, 5, 6, 12, 23, 25, 24, 30] [6, 12, 5, 3, 23, 24, 30, 25] [3, 6, 5, 12, 23, 30, 25, 24]
In diesem Beispiel ist die rechte Seite bereits sortiert, aber der Algorithmus weiß das nicht und sie wäre sortiert worden, wenn dies nicht der Fall gewesen wäre.
Das obige ist der detaillierte Inhalt vonErlernen des Schnellsortierungsalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Heiße KI -Werkzeuge

Undresser.AI Undress
KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover
Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool
Ausziehbilder kostenlos

Clothoff.io
KI-Kleiderentferner

Video Face Swap
Tauschen Sie Gesichter in jedem Video mühelos mit unserem völlig kostenlosen KI-Gesichtstausch-Tool aus!

Heißer Artikel

Heiße Werkzeuge

Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6
Visuelle Webentwicklungstools

SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Heiße Themen











Python eignet sich besser für Anfänger mit einer reibungslosen Lernkurve und einer kurzen Syntax. JavaScript ist für die Front-End-Entwicklung mit einer steilen Lernkurve und einer flexiblen Syntax geeignet. 1. Python-Syntax ist intuitiv und für die Entwicklung von Datenwissenschaften und Back-End-Entwicklung geeignet. 2. JavaScript ist flexibel und in Front-End- und serverseitiger Programmierung weit verbreitet.

Die Verschiebung von C/C zu JavaScript erfordert die Anpassung an dynamische Typisierung, Müllsammlung und asynchrone Programmierung. 1) C/C ist eine statisch typisierte Sprache, die eine manuelle Speicherverwaltung erfordert, während JavaScript dynamisch eingegeben und die Müllsammlung automatisch verarbeitet wird. 2) C/C muss in den Maschinencode kompiliert werden, während JavaScript eine interpretierte Sprache ist. 3) JavaScript führt Konzepte wie Verschlüsse, Prototypketten und Versprechen ein, die die Flexibilität und asynchrone Programmierfunktionen verbessern.

Zu den Hauptanwendungen von JavaScript in der Webentwicklung gehören die Interaktion der Clients, die Formüberprüfung und die asynchrone Kommunikation. 1) Dynamisches Inhaltsaktualisierung und Benutzerinteraktion durch DOM -Operationen; 2) Die Kundenüberprüfung erfolgt vor dem Einreichung von Daten, um die Benutzererfahrung zu verbessern. 3) Die Aktualisierung der Kommunikation mit dem Server wird durch AJAX -Technologie erreicht.

Die Anwendung von JavaScript in der realen Welt umfasst Front-End- und Back-End-Entwicklung. 1) Zeigen Sie Front-End-Anwendungen an, indem Sie eine TODO-Listanwendung erstellen, die DOM-Operationen und Ereignisverarbeitung umfasst. 2) Erstellen Sie RESTFUFFUPI über Node.js und express, um Back-End-Anwendungen zu demonstrieren.

Es ist für Entwickler wichtig, zu verstehen, wie die JavaScript -Engine intern funktioniert, da sie effizientere Code schreibt und Leistungs Engpässe und Optimierungsstrategien verstehen kann. 1) Der Workflow der Engine umfasst drei Phasen: Parsen, Kompilieren und Ausführung; 2) Während des Ausführungsprozesses führt die Engine dynamische Optimierung durch, wie z. B. Inline -Cache und versteckte Klassen. 3) Zu Best Practices gehören die Vermeidung globaler Variablen, die Optimierung von Schleifen, die Verwendung von const und lass und die Vermeidung übermäßiger Verwendung von Schließungen.

Python und JavaScript haben ihre eigenen Vor- und Nachteile in Bezug auf Gemeinschaft, Bibliotheken und Ressourcen. 1) Die Python-Community ist freundlich und für Anfänger geeignet, aber die Front-End-Entwicklungsressourcen sind nicht so reich wie JavaScript. 2) Python ist leistungsstark in Bibliotheken für Datenwissenschaft und maschinelles Lernen, während JavaScript in Bibliotheken und Front-End-Entwicklungsbibliotheken und Frameworks besser ist. 3) Beide haben reichhaltige Lernressourcen, aber Python eignet sich zum Beginn der offiziellen Dokumente, während JavaScript mit Mdnwebdocs besser ist. Die Wahl sollte auf Projektbedürfnissen und persönlichen Interessen beruhen.

Sowohl Python als auch JavaScripts Entscheidungen in Entwicklungsumgebungen sind wichtig. 1) Die Entwicklungsumgebung von Python umfasst Pycharm, Jupyternotebook und Anaconda, die für Datenwissenschaft und schnelles Prototyping geeignet sind. 2) Die Entwicklungsumgebung von JavaScript umfasst Node.JS, VSCODE und WebPack, die für die Entwicklung von Front-End- und Back-End-Entwicklung geeignet sind. Durch die Auswahl der richtigen Tools nach den Projektbedürfnissen kann die Entwicklung der Entwicklung und die Erfolgsquote der Projekte verbessert werden.

C und C spielen eine wichtige Rolle in der JavaScript -Engine, die hauptsächlich zur Implementierung von Dolmetschern und JIT -Compilern verwendet wird. 1) C wird verwendet, um JavaScript -Quellcode zu analysieren und einen abstrakten Syntaxbaum zu generieren. 2) C ist für die Generierung und Ausführung von Bytecode verantwortlich. 3) C implementiert den JIT-Compiler, optimiert und kompiliert Hot-Spot-Code zur Laufzeit und verbessert die Ausführungseffizienz von JavaScript erheblich.
