Heim > Artikel > Backend-Entwicklung > 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
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.
2 Sortierung zusammenführen
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
3 Heap-Sortierung
4 Auswahlsortierung
5-Blasen-Sortierung
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.
6 Einfügungssortierung
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!