Dynamische Diagrammerklärung häufig verwendeter Sortieralgorithmen

Dieser Artikel verwendet hauptsächlich mehrere häufig verwendete Sortieralgorithmen, die visuell intuitiv sind und einen bestimmten Referenzwert haben. Interessierte Freunde können sich auf

beziehen, um mehrere häufig verwendete Sortieralgorithmen intuitiv zu erleben. Der spezifische Inhalt ist wie folgt >

1 Schnellsortierung

Einführung:

Die Schnellsortierung ist eine vom Tony-Hall-Algorithmus entwickelte Sortierung. Im Durchschnitt erfordert das Sortieren von n Elementen O(n log n) Vergleiche. Im schlimmsten Fall sind O(n2)-Vergleiche erforderlich, aber diese Situation ist ungewöhnlich. Tatsächlich ist Quicksort oft deutlich schneller als andere Ο(n log n)-Algorithmen, da seine innere Schleife auf den meisten Architekturen effizient implementiert werden kann und bei den meisten realen Anwendungen gut funktioniert. Daten können Entwurfsentscheidungen bestimmen, wodurch die Möglichkeit quadratischer Terme verringert wird rechtzeitig erforderlich.

Schritte:

Wählen Sie ein Element aus der Sequenz aus, das als „Pivot“ bezeichnet wird.

Ordnen Sie die Sequenz neu an und platzieren Sie alle Elemente, die kleiner als der Pivotwert sind, vor dem Pivot, also allen Elementen Werte, die größer als der Basiswert sind, werden hinter der Basis platziert (die gleiche Zahl kann auf beide Seiten gehen). Nachdem diese Partition beendet wurde, befindet sich die Basis in der Mitte der Sequenz. Dies wird als Partitionsvorgang bezeichnet.
Sortieren Sie rekursiv das Subarray der Elemente, die kleiner als der Basiswert sind, und das Subarray der Elemente, die größer als der Basiswert sind.

Sortiereffekt:

2 Sortierung zusammenführen

Einführung:

Zusammenführungssortierung (Zusammenführungssortierung, taiwanesische Übersetzung: Zusammenführungssortierung) ist ein effektiver Sortieralgorithmus, der auf Zusammenführungsoperationen basiert. Dieser Algorithmus ist eine sehr typische Anwendung der Divide-and-Conquer-Methode (Pide and Conquer).

Schritte:

Beantragen Sie den Raum so, dass seine Größe der Summe aus zwei sortierten Sequenzen und dem Raum entspricht dient zum Speichern der zusammengeführten Sequenz

Setzen Sie zwei Zeiger, die Anfangspositionen sind die Startpositionen der beiden sortierten Sequenzen
Vergleichen Sie die Elemente, auf die die beiden Zeiger zeigen, wählen Sie das relativ kleine Element aus und legen Sie es in den Zusammenführungsraum , und bewegen Sie den Zeiger zur nächsten Position
Wiederholen Sie Schritt 3, bis ein bestimmter Zeiger das Ende der Sequenz erreicht
Kopieren Sie alle verbleibenden Elemente der anderen Sequenz direkt an das Ende der zusammengeführten Sequenz

Sortiereffekt:

3 Heap-Sortierung

Einführung:

Heapsort bezieht sich zur Verwendung Ein Sortieralgorithmus, der für die Datenstruktur eines Heaps entwickelt wurde. Ein Heap ist eine Struktur, die sich einem vollständigen Binärbaum annähert und die Heap-Eigenschaft erfüllt: Das heißt, der Schlüsselwert oder Index eines untergeordneten Knotens ist immer kleiner (oder größer) als sein übergeordneter Knoten.

Schritte:

(Es ist komplizierter, schauen Sie es sich online an)

Sortiereffekt:

4 Auswahlsortierung

Einführung:

Auswahlsortierung ist ein einfacher und intuitiver Sortieralgorithmus. So funktioniert es. Suchen Sie zunächst das kleinste Element in der unsortierten Sequenz und speichern Sie es am Anfang der sortierten Sequenz. Suchen Sie dann weiterhin das kleinste Element aus den verbleibenden unsortierten Elementen und fügen Sie es dann am Ende der sortierten Sequenz ein. Und so weiter, bis alle Elemente sortiert sind.

Sortiereffekt:

5-Blasen-Sortierung

Einführung:

Bubble Sort (Bubble Sort, aus Taiwan übersetzt als: Bubble Sort oder Bubble Sort) ist ein einfacher Sortieralgorithmus. Es durchläuft wiederholt die zu sortierende Sequenz, vergleicht jeweils zwei Elemente und vertauscht sie, wenn sie in der falschen Reihenfolge sind. Der Besuch des Arrays wird wiederholt, bis kein Austausch mehr erforderlich ist, was bedeutet, dass das Array sortiert wurde. Der Name dieses Algorithmus rührt von der Tatsache her, dass kleinere Elemente durch den Austausch langsam an die Spitze des Arrays „schweben“.

Schritte:

Benachbarte Elemente vergleichen. Wenn das erste größer als das zweite ist, tauschen Sie beide aus.

Machen Sie dasselbe für jedes Paar benachbarter Elemente, beginnend mit dem ersten Paar und endend mit dem letzten Paar. Zu diesem Zeitpunkt sollte das letzte Element die größte Zahl sein.
Wiederholen Sie die obigen Schritte für alle Elemente außer dem letzten.
Wiederholen Sie die obigen Schritte jedes Mal für immer weniger Elemente, bis keine Zahlenpaare mehr zum Vergleichen vorhanden sind.

Sortiereffekt:

6 Einfügungssortierung

Einführung:

Die Algorithmusbeschreibung von Insertion Sort ist ein einfacher und intuitiver Sortieralgorithmus. Es funktioniert, indem es eine geordnete Sequenz erstellt. Bei unsortierten Daten scannt es die sortierte Sequenz von hinten nach vorne, findet die entsprechende Position und fügt sie ein. Bei der Implementierung der Einfügungssortierung wird normalerweise die In-Place-Sortierung verwendet (d. h. eine Sortierung, die nur O(1) zusätzlichen Platz beansprucht). Daher ist es während des Scanvorgangs erforderlich, die Sortierung wiederholt und schrittweise zu verschieben Sortiert Elemente rückwärts und bietet Platz zum Einfügen für das neueste Element.

Schritte:

Beginnen Sie mit dem ersten Element, das als sortiert betrachtet werden kann
Nehmen Sie das nächste Element heraus und scannen Sie es von hinten nach vorne in der Reihenfolge der sortierten Elemente
Wenn das Element (sortiert) größer als das neue Element ist, verschieben Sie das Element an die nächste Position
Wiederholen Sie Schritt 3, bis Sie eine Position finden, an der das sortierte Element kleiner oder gleich dem neuen Element ist
Fügen Sie das neue ein Element in diese Position Wiederholen Sie Schritt 2 in

7 Hügelsortierung

Einführung:

Hügelsortierung, auch absteigend genannt Der inkrementelle Sortieralgorithmus ist eine schnelle und stabile verbesserte Version der Einfügungssortierung.

Die Hill-Sortierung schlägt eine verbesserte Methode vor, die auf den folgenden zwei Eigenschaften der Einfügungssortierung basiert:

Die Einfügungssortierung ist hocheffizient, wenn sie mit Daten arbeitet, die fast sortiert wurden, d. h. sie kann Folgendes erreichen: Effizienz der linearen Sortierung
Aber die Einfügungssortierung ist im Allgemeinen ineffizient, da die Einfügungssortierung Daten jeweils nur um ein Bit verschieben kann

Sortiereffekt:

Das obige ist der detaillierte Inhalt vonDynamische Diagrammerklärung häufig verwendeter Sortieralgorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!