c++ - C++ 算法/Boost Lib 是否具有基数排序？

Question

我想对整数进行排序，我知道基数排序应该很棒。这种类型的任何库实现？

Answer 1

取决于您定义基数排序的严格程度，因为 Boost 1.58.0 包含Spreadsort，这是一种混合排序算法，启发式地混合了桶排序和比较排序。

对于排序整数并且不需要最坏情况下的 Θ(n) 效率，Spreadsort 应该满足您。

为了论证，您还可以查看我的LSD 基数排序实现，它在内存方面效率相当低，但有时比 Spreadsort 快。您只需要 radix_sort 分支，但我已链接到 speed_test 分支，因为它有自述文件。

Answer 2

更实际的答案是肯定的，因为 1.58 确实如此：

• http://www.boost.org/doc/libs/1_58_0/libs/sort/doc/html/index.html

它有一种叫做 SpreadSort 的东西，并且会“神奇地”检测类型的优化路径std::string，或者可以被视为字节数组的浮点数。