algorithm
Radix Sort
Suche…
Grundlegende Informationen zu Radix Sort
Radix Sort ist ein Algorithmus, der auf einem unteren Grenzwert basiert. Hierbei handelt es sich um einen nicht vergleichenden ganzzahligen Sortieralgorithmus, der Daten mit ganzzahligen Schlüsseln sortiert, indem die Schlüssel nach einzelnen Ziffern gruppiert werden, die eine bedeutende Position und einen bestimmten Wert teilen. Radix-Sortierung ist ein linearer Zeitsortieralgorithmus, der nach O (n + k) -Zeit sortiert, wenn sich Elemente im Bereich von 1 bis k befinden. Die Idee von Radix Sort ist die zeilenweise Sortierung, beginnend mit der niedrigstwertigen Ziffer bis zur höchstwertigen Ziffer. Bei der Radix-Sortierung wird die Sortierung als Subroutine zum Sortieren verwendet. Radix-Sortierung ist die Generalisierung der Bucket-Sortierung.
Pseudo-Code für Bucket Sort:
- Erstellen Sie ein Array von [0..n-1] -Elementen.
- Call Bucket Sortiere wiederholt die niedrigste bis höchstwertige Stelle jedes Elements als Schlüssel.
- Gib das sortierte Array zurück.
Beispiel für Radix Sort:
Weltraumhilfsmittel: O(n)
Zeitkomplexität: O(n)