基数排序,对浮点数据进行排序

Question

基数排序是否能够对浮动数据进行排序,例如0.5,0.9,1.02等？

Answer 1

对的,这是可能的.它需要额外的传递才能正确处理负值.Pierre Terdiman和Michael Herf的文章详细讨论了如何实现它.简而言之,您将浮点数转换为无符号整数,对它们进行排序,然后将它们转换回浮点数(这是必需的,否则负数值将在正数值之后错误地排序).

他们的方法的优点是您不会在数据中引入任何错误(前提是您的处理器根据IEEE 754标准存储浮点数).

这是另一篇有趣的文章 (http://seven- Degrees-of-freedom.blogspot.com/2010/07/question-of-sorts.html)，将基数排序与合并排序的 SPU 并行化版本进行比较。总而言之，合并排序虽然更复杂（复杂度为 O(n log n)，而基数排序为 O(n)），但可以更容易并行化并最终获胜。 (2认同)

Answer 2

不是开箱即用的，但您有一些选择。您可以离散化数据，例如，通过乘以 100 并四舍五入（这样，对于上面的示例，您将得到 5、9 和 102）。您还可以对数据进行分桶（按范围对数字进行分组，如 0 < x <= 1、1 < x <= 2），然后在每个桶内进行排序。