Wie verwende ich die Verteilungssortierung (Radix-Sortierung usw.), um Zeichenfolgen zu sortieren?

Question

Ich weiß, wie man die Basissortierung zum Sortieren von Ganzzahlen verwendet.

Aber wie kann man damit Strings sortieren?oder Float-Zahlen?

Answer 1

Die Radix-Sortierung oder jede andere Verteilungssortierung kann zum Sortieren von Gleitkommazahlen verwendet werden, wenn Sie einige Besonderheiten dieser Zahlen wie Unendlichkeit, Nicht-Zahlen-Werte und zwei verschiedene Darstellungen von Null außer Acht lassen. IEEE 754-2008 Gleitkommazahlen haben binäre Darstellungen, die in der Sortierreihenfolge mit Ganzzahlen kompatibel sind.Also, wenn man Nicht-A-Zahlen ausschließt und neu interpretiert float oder double als int32 oder int64, können Sie jede Verteilungssortierung direkt auf sie anwenden. Bearbeiten: Negative Gleitkommazahlen bedürfen einer besonderen Behandlung (wie von AShelly hervorgehoben), da ihre Sortierreihenfolge der Sortierreihenfolge von Ganzzahlen entgegengesetzt ist.

Bei Strings ist es aufgrund der variablen Länge schwieriger.Eine andere Art der Verteilungssortierung (Bucket-Sortierung) kann verwendet werden und wird häufig für Zeichenfolgen verwendet.Für die Bucket-Indizierung werden mehrere Anfangszeichen der Zeichenfolge verwendet. Anschließend wird eine beliebige Vergleichssortierung verwendet, um die Zeichenfolgen innerhalb der Buckets zu sortieren.

Wenn alle Saiten fast die gleiche Länge haben und/oder eine Technik verwendet wird, um Unterschiede zwischen Saiten zu verstärken (wie in Kapitel 6 von beschrieben). "SCHNELL:Schnelle architektursensitive Baumsuche auf modernen CPUs und GPUs), dann kann auch die Radix-Sortierung verwendet werden:Teilen Sie die Zeichenfolge in Gruppen von Zeichen (oder besser in Gruppen von Bits) gleicher Länge auf, interpretieren Sie diese Gruppen als Ganzzahlen neu und fahren Sie fort, als ob es sich um eine Basissortierung für Ganzzahlen handeln würde.

Bearbeiten: Alle Arten der Verteilungssortierung funktionieren garantiert nur für ASCII-Zeichenfolgen ordnungsgemäß.Andere Zeichenfolgenkodierungen erfordern möglicherweise eine andere Sortierreihenfolge oder hängen vom Parameter „collate“ des Gebietsschemas ab.

Answer 2

ja es ist möglich.

siehe Radix Sortieren, sortieren einer Float-Daten für Floats.Es verwendet die Tatsache, dass Floats an Integertypen korrekt verglichen werden (einst Negativen korrigieren).Siehe Dieser Artikel für Details

Bei den Zeichenfolgen können Sie das Problem mit variablen Längen lösen, indem Sie einen MSD-Radix sortieren, und stellen Sie sicher, dass Sie auf dem Laufenden aufhören, wenn Sie auf NULLS stoßen.Siehe Radix Sort implementiert in C ++ für String .