Heim Web-Frontend js-Tutorial Erlernen des Schnellsortierungsalgorithmus

Erlernen des Schnellsortierungsalgorithmus

Jan 04, 2025 pm 12:11 PM

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:

  1. Alle Elemente links davon sind kleiner.
  2. 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]
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

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:

Learning the Quick Sort Algorithm

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.

Learning the Quick Sort Algorithm

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.

Learning the Quick Sort Algorithm

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 .

Learning the Quick Sort Algorithm

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.

Learning the Quick Sort Algorithm

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:

Learning the Quick Sort Algorithm

Learning the Quick Sort Algorithm

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:

Learning the Quick Sort Algorithm

Learning the Quick Sort Algorithm

Quick Sort setzt diesen Vorgang fort, bis das Ende des Arrays erreicht ist:

Learning the Quick Sort Algorithm

Learning the Quick Sort Algorithm

Learning the Quick Sort Algorithm

Learning the Quick Sort Algorithm

Learning the Quick Sort Algorithm

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.

Learning the Quick Sort Algorithm

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]
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

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;
};
Nach dem Login kopieren

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);
}
Nach dem Login kopieren
  • 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.

Learning the Quick Sort Algorithm

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]
Nach dem Login kopieren
Nach dem Login kopieren
Nach dem Login kopieren

Learning the Quick Sort Algorithm

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!

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

Video Face Swap

Video Face Swap

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

Heißer Artikel

<🎜>: Bubble Gum Simulator Infinity - So erhalten und verwenden Sie Royal Keys
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Nordhold: Fusionssystem, erklärt
4 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Mandragora: Flüstern des Hexenbaum
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Heiße Themen

Java-Tutorial
1670
14
PHP-Tutorial
1273
29
C#-Tutorial
1256
24
Python vs. JavaScript: Die Lernkurve und Benutzerfreundlichkeit Python vs. JavaScript: Die Lernkurve und Benutzerfreundlichkeit Apr 16, 2025 am 12:12 AM

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.

Von C/C nach JavaScript: Wie alles funktioniert Von C/C nach JavaScript: Wie alles funktioniert Apr 14, 2025 am 12:05 AM

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.

JavaScript und das Web: Kernfunktionalität und Anwendungsfälle JavaScript und das Web: Kernfunktionalität und Anwendungsfälle Apr 18, 2025 am 12:19 AM

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.

JavaScript in Aktion: Beispiele und Projekte in realer Welt JavaScript in Aktion: Beispiele und Projekte in realer Welt Apr 19, 2025 am 12:13 AM

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.

Verständnis der JavaScript -Engine: Implementierungsdetails Verständnis der JavaScript -Engine: Implementierungsdetails Apr 17, 2025 am 12:05 AM

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 gegen JavaScript: Community, Bibliotheken und Ressourcen Python gegen JavaScript: Community, Bibliotheken und Ressourcen Apr 15, 2025 am 12:16 AM

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.

Python vs. JavaScript: Entwicklungsumgebungen und Tools Python vs. JavaScript: Entwicklungsumgebungen und Tools Apr 26, 2025 am 12:09 AM

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.

Die Rolle von C/C bei JavaScript -Dolmetschern und Compilern Die Rolle von C/C bei JavaScript -Dolmetschern und Compilern Apr 20, 2025 am 12:01 AM

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.

See all articles