如何使用分配排序（基数排序等）对字符串进行排序？

Question

我知道如何使用基数排序整数。

但如何使用它来排序字符串？或浮点数？

Answer 1

基数排序或任何其他分布排序可用于排序浮点数，如果您忽略它们的某些特性，如无穷大，非数值和两个不同的零表示。 IEEE 754-2008浮点数具有二进制表示形式，与整数排序顺序兼容。因此，如果您排除非数字并重新解释float或double为int32或int64，您可以直接对其应用任何分配排序。 编辑：负浮点数需要特殊处理（由AShelly指出），因为它们的排序顺序与整数排序顺序相反。

对于字符串，由于它们的可变长度而变得更加困难。其他类型的分配排序（桶排序）可以被使用并且经常用于字符串。该字符串的几个起始字符用于存储桶索引，然后使用任何比较排序来对该存储桶内的字符串进行排序。

如果所有字符串具有几乎相等的长度和/或某些技术被用于扩增串之间的差异，然后基数排序可以被用作孔（比如在"FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs" 6章中的说明）：所述字符串分割字符组（或者更好），将这些组重新解释为整数，并继续，就像对整数进行基数排序一样。

编辑：各种分配排序保证只适用于ASCII字符串。其他字符串编码可能需要不同的排序顺序，或者可能取决于语言环境的“collat​​e”参数。

Answer 2

是的，这是可能的。

请参阅Radix Sort, Sorting a float data浮标。它使用浮点数转换为整数类型比较正确的事实（一旦消极被纠正）。有关详细信息，请参阅this article

对于字符串，可以通过执行MSD基数排序来解决可变长度问题，并确保在遇到空值时停止下降。请参阅Radix sort implemented in c++ for string。