Was ist Einfügungssortierung?

Einfügungssortierung hat zwei Arten: einfache Einfügungssortierung und Hill-Sortierung. Die zeitliche Komplexität der einfachen Einfügungssortierung ist [O(N2) stabile Sortierung], und die zeitliche Komplexität der Hill-Sortierung ist [und inkrementelle Reihenfolge] Auswählen verwandte, instabile Sortierung].

Einfügesortierung

Einfache Einfügungssortierung

Legen Sie die zu sortierende Gruppe fest Die Sequenz ist in zwei Teile unterteilt: sortiert und unsortiert. Im Anfangszustand enthält die sortierte Sequenz nur das erste Element, und die Elemente in der unsortierten Sequenz sind N-1-Elemente, außer dem ersten in der sortierten Reihenfolge werden nacheinander in die sortierte Reihenfolge eingefügt. 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 „Intervall“ wird zu Beginn größer eingestellt 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 zusammen

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