Was sind die grundlegenden Sortiermethoden?

Grundlegende Sortiermethoden umfassen: 1. Auswahlsortierung, die in „einfache Auswahlsortierung“ und „Heap-Sortierung“ unterteilt ist; 2. Einfügungssortierung, die in „einfache Einfügungssortierung“ und „Hill-Sortierung“ unterteilt ist; 3. Die Austauschsortierung ist in „Blasensortierung“ und „Schnellsortierung“ unterteilt. 4. Zusammenführungssortierung.

Grundlegende Sortiermethode

Sortieren

Keine Ein Sortieralgorithmus ist unter allen Umständen optimal, und der optimale Algorithmus muss entsprechend der tatsächlichen Situation ausgewählt werden, um das Problem zu lösen

Stabilität des Algorithmus: In einem Satz zu sortierender Datensätze, wenn zwei gleiche Datensätze vorhanden sind R und S, und in den zu sortierenden Datensätzen liegt R vor S. Wenn R nach der Sortierung immer noch vor S liegt, das heißt, ihre vordere und hintere Position ändern sich vor und nach der Sortierung nicht, dann wird der Sortieralgorithmus als stabil

• Auswahlsortierung

Einfache Auswahlsortierung

Einfache Auswahlsortierung ist ein intuitiver Sortieralgorithmus zur Auswahl das kleinste Element in der unsortierten Sequenz und tauscht es mit dem ersten Element der Sequenz aus, wählt dann das kleinste Element in der verbleibenden unsortierten Sequenz aus und tauscht es mit dem zweiten Element der Sequenz aus und so weiter klein bis groß wird gebildet

Zeitkomplexität: O(N2)

Heap-Sortierung

Erzeugt eine ungeordnete Sequenz in einem maximalen Heap und platziert die Spitze des Heaps. Tauschen Sie die aus Elemente mit dem letzten Element und generieren Sie den maximalen Heap mit den verbleibenden Elementen. Tauschen Sie die Elemente der Reihe nach aus und generieren Sie den maximalen Heap

Zeitkomplexität: O(NlogN) Raumkomplexität: O(1)

• Einfügungssortierung

Einfache Einfügungssortierung

Teilen Sie eine Reihe von zu sortierenden Sequenzen in sortierte Es gibt zwei Teile, geordnet und unsortiert. Im Anfangszustand enthält die sortierte Sequenz nur das erste Element, und die Elemente in der unsortierten Sequenz sind N-1 Elemente mit Ausnahme des ersten. Danach werden die Elemente in der unsortierten Sequenz einzeln hinzugefügt . In sortierte Reihenfolge einfügen. Auf diese Weise ist nach N-1 Einfügungen die Anzahl der Elemente in der unsortierten Sequenz 0, dann ist die Sortierung abgeschlossen

Zeitkomplexität: O(N2) Stabile Sortierung

Hill-Sortierung

Teilen Sie einen Satz zu sortierender Elemente in bestimmten Abständen in mehrere Sequenzen auf und führen Sie jeweils eine Einfügungssortierung durch. Das zu Beginn festgelegte „Intervall“ ist größer und das Intervall wird in jeder Sortierrunde schrittweise verringert, bis das „Intervall“ 1 beträgt. Das heißt, der letzte Schritt besteht darin, eine einfache Einfügungssortierung durchzuführen

Zeitkomplexität : Summeninkrement Die Auswahl der Sequenzen hängt mit der instabilen Sortierung

• Austauschsortierung

Blasensortierung

für Elemente Beim Sortieren von N zu sortierenden Sequenzen werden insgesamt N-1 Zyklen durchgeführt. In der k-ten Schleife werden die Elemente vom 1. bis zum N-ten von vorne nach hinten verglichen, und jedes Mal werden die beiden benachbarten Elemente verglichen. Wenn das erstere Element größer als das letztere Element ist, tauschen die beiden Positionen aus. andernfalls bleiben sie ortsinvariant

Zeitkomplexität: O(N2)

Schnellsortierung

Teilt die unsortierten Elemente in zwei Teilsequenzen basierend auf einem „Pivot“ als Basis auf, Die Datensätze einer Teilsequenz sind alle größer als das Pivot-Element, während die Datensätze der anderen Teilsequenz kleiner als das Pivot-Element sind. Anschließend werden die beiden Teilsequenzen mit einer ähnlichen Methode rekursiv sortiert

Zeitkomplexität: O( Nlog2N)

• Sortierung zusammenführen

Betrachten Sie eine Sequenz der Größe N als N Teilsequenzen der Länge 1. Weiter Zusammenführen benachbarter Teilsequenzen in Paaren, um N/2(+1) geordnete Teilsequenzen mit einer Länge von 2 (oder 1) zu bilden; dann werden benachbarte Teilsequenzen paarweise zusammengeführt, bis eine Sequenz der Länge N übrig bleibt, die Sequenz ist das Ergebnis der Sortierung der ursprünglichen Sequenz

Zeitkomplexität: O(Nlog2N) Raumkomplexität: O(N)

• Radix-Sortierung

Bucket-Sortierung

Wenn bekannt ist, dass der Wertebereich von N Schlüsselwörtern von 0 bis M -1 reicht und M viel kleiner als N ist, erstellt der Bucket-Sortieralgorithmus Für jeden Wert des Schlüsselworts wird ein „Eimer“ erstellt, d geordnet

Radix-Sortierung

Die Radix-Sortierung ist eine Verallgemeinerung der Bucket-Sortierung und berücksichtigt die zu sortierenden Datensätze. Enthält mehr als ein Schlüsselwort

Das obige ist der detaillierte Inhalt vonWas sind die grundlegenden Sortiermethoden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!