Was ist Radix-Sortierung?

Die Radix-Sortierung ist eine Verallgemeinerung der Bucket-Sortierung. Die zu sortierenden Datensätze enthalten mehr als ein Schlüsselwort. Die Elemente werden bestimmten „Buckets“ zugeordnet, um eine Sortierung zu erreichen. Die Radix-Sortiermethode ist eine stabile Sortiermethode.

Radix-Sortierung

Radix-Sortierung ist eine Verallgemeinerung der Bucket-Sortierung, die die enthaltenen Ranking-Datensätze berücksichtigt mehr als ein Schlüsselwort.

Einführung:

Die Radix-Sortierung ist eine „Verteilungssortierung“, die auch als „Bucket-Sortierung“ oder „Bin-Sortierung“ bezeichnet wird Zu sortierende Elemente werden bestimmten „Buckets“ zugewiesen, um den Sortiereffekt zu erzielen. Die Basissortiermethode ist eine stabile Sortierung und ihre Zeitkomplexität beträgt O (nlog(r)m), wobei r die genommene Basis und m ist Die Anzahl der Heaps ist zu bestimmten Zeiten effizienter als andere Stabilitätssortiermethoden.

Implementierungsmethode

Most Significant Digit First-Methode, auch MSD-Methode genannt: Zuerst die Gruppen nach k1 sortieren, in derselben Gruppe aufzeichnen, der Schlüsselcode k1 ist gleich, und dann jede Gruppe gruppieren Die Gruppe wird gemäß der K2-Sortierung in Untergruppen unterteilt, und dann werden die nachfolgenden Schlüsselcodes weiterhin auf diese Weise 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 Signifikanz, 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 vonWas ist Radix-Sortierung?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!