一个快速,基于排名的Radix Sort for floats？

Question

我正在寻找一个快速稳定的基数排序实现(支持浮点数),它返回排序顺序的索引而不是排序值.

Pierre Terdiman在其文章"Radix Sort Revisited"中的版本完全符合我的要求,但它已超过13年,并不适合现代流水线CPU.

来自"Radix Tricks"的Michael Herf的 RadixSort11 非常快,唯一的问题是它返回排序值而不是索引,此外它还会破坏输入数组的值.

任何帮助,将不胜感激.

Answer 1

你可以

1. 展开每个项目以包含其原始索引（这可以在第一次计数过程中完成）。当然，出于排序目的，索引数字被忽略。

2. 将索引而不是值存储到存储桶中。每次需要数字时查找该值。

第一个占用更多空间，但具有更好的引用局部性，第二个节省空间。