基数排序，对浮点数进行排序

Question

16

基数排序能够对浮点数进行排序，例如0.5、0.9、1.02等。

- BGV

我想通过将基数排序的桶减少为仅包含0和1来实现它，这意味着我会将每个输入转换为其二进制值，然后进行基数排序。这样做是否可以加快排序速度，还是会使基数排序比以前慢一些？谢谢。 - BGV

你所描述的是“二进制基数排序”。对于32位的float数据，它需要进行32次排序。2**32约为40亿，因此除非你有如此多的数据，否则像归并排序这样的O(N lgN)排序可能会更快。（对于64位的double，极限是18万亿亿） - AShelly

2个回答

1

并非开箱即用，但您有一些选项。您可以离散化数据，例如通过乘以100并四舍五入（因此对于上面的示例，您将拥有5、9和102）。您还可以将数据分桶（按范围分组数字，如0

- EmeryBerger

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sylvain Defresne · Accepted Answer

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

他们的方法的优点是您不会引入任何误差到您的数据中（前提是您的处理器按照IEEE 754标准存储浮点数）。