Ist die Radix-Sortierung der einzige Sortieralgorithmus ohne Vergleich?

Question

Ist die Radix-Sortierung, wie der Titel schon sagt, der einzige Sortieralgorithmus ohne Vergleich?Meine Vermutung ist ja.

Answer 1

Nein - ua zählen Sortier- und Eimer sortiert.Überprüfen Sie die Wikipedia Artikel für weitere Informationen.

Answer 2

Jeder Satz kann ohne Verwendung von Vergleichen sortiert werden.

Der Prozess ist

• Entscheiden Sie sich für eine überschaubare Größe der Eingabedomäne M, mit der Sie in einem überschaubaren Array aufzeichnen können.Für Zeichen (8-Bit) wäre die Domäne 0-255.
• Teilen Sie die Eingabe auf geordnete Weise in das Array auf.
• Wiederholen und spülen, wenn die Eingabe noch nicht vollständig berücksichtigt wurde, d. h.Alle Bits in M ​​wurden nicht berücksichtigt.

Beispielsweise könnte eine 32-Bit-M-Integer-Sortierung wie folgt ausgeführt werden:

• Schauen Sie sich die ersten 8 Bits an und platzieren Sie sie im 8-Bit-Bereich (Referenzen, Zeiger oder was Ihre Sprache zur Verfügung hat).Fügen Sie sie in ein Array [0-255] ein. Jetzt haben Sie eine grobe (Standard-)Reihenfolge Ihrer Werte.
• Schauen Sie sich die nächsten 8 Bits an, fügen Sie sie in ein ähnliches Array ein und behalten Sie einen Verweis auf die erste Reihenfolge bei.Die nächsten 8x2 Bits werden auf die gleiche Weise behandelt.Zum Extrahieren folgen Sie den Links aus dem ersten Satz.

Die Radix-Sortierung verwendet Ziffern und hat zwei Varianten: (MSB zu LSB) und (LSB zu MSB).

Bei der Zählsortierung wird nur der erste Schritt verwendet

Bucket-Sortierung wird normalerweise verwendet, wenn es um eine Mischung aus Zähl- und Vergleichssortierung geht.

Interessanterweise ist die Vergleichssortierung bei vielen Anwendungsfällen unzureichend.