Was ist Hill-Sortierung?

Hill-Sortierung ist eine Art Einfügungssortierung, die auch als „reduzierende inkrementelle Sortierung“ bezeichnet wird. Es handelt sich um eine effizientere und verbesserte Version des Direkteinfügungs-Sortieralgorithmus Die Methode geht auf „D.L.Shell“ zurück, das 1959 vorgeschlagen und nach ihr benannt wurde.

Hügelsortierung

Teilt einen Satz zu sortierender Elemente in bestimmte Intervalle in mehrere Sequenzen auf werden separat eingefügt und sortiert. 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-Sequenzauswahl im Zusammenhang mit instabiler Sortierung

Einführung:

Hill-Sortierung (Shell's Sort) ist eine Art Einfügungssortierung, auch bekannt als „Diminishing Increment Sort“ (Diminishing Increment Sort). ), bei dem es sich um eine direkte, effizientere und verbesserte Version des Einfügungssortierungsalgorithmus handelt. Hill-Sortierung ist ein instabiler Sortieralgorithmus. Diese Methode ist nach D.L. Shell benannt, der sie 1959 vorgeschlagen hat.

Hill-Sortierung besteht darin, Datensätze nach einem bestimmten Inkrement des Index zu gruppieren und jede Gruppe mithilfe des Sortieralgorithmus für direkte Einfügung zu sortieren. Mit zunehmender Inkrementierung enthält jede Gruppe immer mehr Schlüsselwörter auf 1, die gesamte Datei wird in eine Gruppe aufgeteilt und der Algorithmus wird beendet.

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