我知道如何使用基数排序对整数进行排序。
但是如何使用它对字符串进行排序呢？还是浮点数？
问问题
2995 次
2 回答
4
如果您忽略浮点数的一些特性，例如无穷大、非数字值和零的两种不同表示，则可以使用基数排序或任何其他分布排序来对浮点数进行排序。IEEE 754-2008浮点数具有二进制表示，在排序顺序上与整数兼容。因此，如果您排除 not-a-numbers 并将 or 重新解释float为doubleor int32，int64您可以直接对它们应用任何分布排序。编辑：负浮点数需要特殊处理（如 AShelly 指出的那样），因为它们的排序顺序与整数的排序顺序相反。
对于字符串，由于它们的长度可变，因此更加困难。可以使用其他类型的分布排序（桶排序）并且通常用于字符串。字符串的几个起始字符用于桶索引，然后使用任何比较排序对桶内的字符串进行排序。
如果所有字符串的长度几乎相等和/或使用某种技术来放大字符串之间的差异（如“FAST：现代 CPU 和 GPU 上的快速架构敏感树搜索”的第 6 章中所述），那么也可以使用基数排序：将字符串拆分为等长的字符组（或者更好的是，拆分为位组），将这些组重新解释为整数，并继续进行，就好像它是整数的基数排序一样。
编辑：保证各种分布排序仅适用于 ASCII 字符串。其他字符串编码可能需要不同的排序顺序，或者可能取决于语言环境的“collate”参数。
于 2012-03-09T19:58:01.933 回答
3
是的，有可能。
请参阅基数排序，为浮点数排序浮点数据。它使用浮点数转换为整数类型的事实比较正确（一旦纠正了负数）。详情请看这篇文章
对于字符串，您可以通过执行 MSD 基数排序并确保在遇到 Null 时停止降序来解决可变长度问题。请参阅在 c++ 中实现的基数排序字符串。
于 2012-03-09T20:59:47.170 回答