Wozu dient die Radix-Sortierung?

Die Radix-Sortierung ist eine „verteilende Sortierung“. Sie ordnet die zu sortierenden Elemente anhand eines Teils der Schlüsselwertinformationen zu, um den Sortiereffekt zu erzielen, der zum Sortieren von Daten wie Zeit geeignet ist und Saite, deren Gesamtgewicht unbekannt ist.

Radix-Sortierung ist eine „Verteilungssortierung“, auch bekannt als „Bucket-Sortierung“ oder Bin-Sortierung. Wie der Name schon sagt, ordnet sie die zu sortierenden Elemente zu Durch einen Teil der Schlüsselwertinformationen wird ein Sortiereffekt in bestimmten „Eimern“ erzielt. Die Radix-Sortiermethode ist eine stabile Sortierung und ihre zeitliche Komplexität beträgt O (nlog (r) m), wobei r die genommene Basis und m ist ist die Anzahl der Heaps. Manchmal ist die Basissortiermethode effizienter als andere Stabilitätssortiermethoden.

Radix-Sortierung eignet sich zum Sortieren von Daten wie Zeit und Zeichenfolgen, deren Gesamtgewicht unbekannt ist.

Implementierungsmethode

Most Significant Digit First-Methode, auch MSD-Methode genannt: Zuerst nach k1 sortieren und gruppieren, in derselben Gruppe aufzeichnen, Schlüssel If Sind die Codes k1 gleich, dann wird jede Gruppe nach k2 in Untergruppen sortiert. Danach werden die folgenden Schlüsselcodes auf diese Weise weiter sortiert und gruppiert, bis jede Untergruppe nach dem niedrigsten Schlüsselcode kd sortiert ist. Verbinden Sie dann die Gruppen, um eine geordnete Reihenfolge zu erhalten.

Die Methode der ersten Ziffer mit der geringsten Bedeutung, die als LSD-Methode bezeichnet wird: Beginnen Sie mit der Sortierung bei kd, sortieren Sie dann kd-1 und wiederholen Sie den Vorgang, bis k1 sortiert ist und eine geordnete Sequenz erhalten wird.

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