问题标签 [radix-sort]

前几天我决定用 Java编写一个基数排序的实现。基数排序应该是 O(k*N) 但我的最终是 O(k^2*N) 因为将每个数字分解为一个数字的过程。我通过修改（％）前面的数字并除以十来消除后面的数字来分解每个数字。我问我的教授是否有更有效的方法来做到这一点，他说使用位运算符。现在我的问题是：哪种方法在分解 Java 中的每个数字时最快，1) 上述方法。2）将数字转换为字符串并使用子字符串。3) 使用位操作。

如果 3) 那么这将如何工作？

这是一篇长文。请多多包涵。归结起来，问题是：是否有可行的就地基数排序算法？

初步的

我有大量固定长度的小字符串，它们只使用我想要排序的字母“A”、“C”、“G”和“T”（是的，你猜对了：DNA ）。

目前，我使用which 在STL的所有常见实现中std::sort使用introsort。这工作得很好。但是，我相信基数排序非常适合我的问题集，并且在实践中应该工作得更好。

细节

我已经用一个非常幼稚的实现测试了这个假设，并且对于相对较小的输入（大约 10,000 个）这是正确的（嗯，至少快两倍以上）。但是，当问题规模变大（N > 5,000,000）时，运行时间会大大降低。

原因很明显：基数排序需要复制整个数据（实际上在我的幼稚实现中不止一次）。这意味着我已将 ~ 4 GiB 放入我的主内存中，这显然会影响性能。即使没有，我也负担不起使用这么多内存，因为问题的大小实际上变得更大了。

用例

理想情况下，该算法应适用于 2 到 100 之间的任何字符串长度，适用于 DNA 和 DNA5（允许额外的通配符“N”），甚至是具有IUPAC 歧义码的 DNA （产生 16 个不同的值）。但是，我意识到无法涵盖所有​​这些情况，因此我对获得的任何速度改进感到满意。代码可以动态决定分派到哪个算法。

研究

不幸的是，关于基数排序的维基百科文章毫无用处。关于就地变体的部分完全是垃圾。NIST-DADS 关于基数排序的部分几乎不存在。有一篇听起来很有前途的论文叫做Efficient Adaptive In-Place Radix Sorting，它描述了算法“MSL”。不幸的是，这篇论文也令人失望。

特别是有以下几点。

首先，该算法包含几个错误并且有很多无法解释的地方。特别是，它没有详细说明递归调用（我只是假设它增加或减少了一些指针来计算当前的移位和掩码值）。此外，它使用函数dest_group并且dest_address没有给出定义。我看不到如何有效地实现这些（也就是说，在 O(1) 中；至少dest_address不是微不足道的）。

最后但同样重要的是，该算法通过将数组索引与输入数组中的元素交换来实现就地性。这显然只适用于数值数组。我需要在字符串上使用它。当然，我可以只是搞砸强类型并继续假设内存将允许我存储不属于它的索引。但这只有在我可以将字符串压缩到 32 位内存（假设为 32 位整数）时才有效。那只有 16 个字符（让我们暂时忽略 16 > log(5,000,000)）。

其中一位作者的另一篇论文根本没有给出准确的描述，但它给出了 MSL 的运行时间是亚线性的，这完全是错误的。

回顾一下：是否有希望找到一个有效的参考实现，或者至少是一个很好的伪代码/描述一个适用于 DNA 字符串的就地基数排序？

如果我有大量的整数或浮点数，那么什么是好的排序算法/实现（在 C 中）？

在游戏中进行编辑有点晚了......但我正在寻找正确性和速度。

我正在尝试通过创建一个程序来改进我的 C++，该程序将采用 1 到 10^6 之间的大量数字。将在每次传递中存储数字的存储桶是一个节点数组（其中节点是我创建的包含一个值和下一个节点属性的结构）。

根据最不重要的值将数字分类到桶中后，我将一个桶的末尾指向另一个桶的开头（这样我就可以快速获取存储的数字而不会破坏顺序）。我的代码没有错误（编译或运行时），但是关于如何解决剩余的 6 次迭代（因为我知道数字的范围），我遇到了困难。

我遇到的问题是，最初这些数字以 int 数组的形式提供给 radixSort 函数。在排序的第一次迭代之后，数字现在存储在结构数组中。有什么方法可以重新编写我的代码，以便我只有一个用于 7 次迭代的 for 循环，或者我需要一个 for 循环运行一次，而它下面的另一个循环将运行 6 次，然后返回完全排序的列表？

最好使用任何非病毒开源许可证

欢迎。我有一个基数排序方法，它使用一个数组来遍历，但必须有另一个数组（bin）将存储在一个空队列中。我对如何为垃圾箱排长队感到困惑。我还有一个 findPlace 方法，可以在调用时找到每个数字的位置。所以，这就是我得到的。有人可以帮我找到我缺少的东西吗？非常感谢您的宝贵时间。

我还做了一个方法来找到存储桶，所以我只需要知道如何将它放入数组中，我会这样做吗？部分.add(getPlace(x, place));?

您能够使用基数排序对您的数据有哪些限制？

如果我正在对大量整数进行排序，是否适合使用基数排序？为什么基数排序没有更多使用？

我有一个带有浮点类型字段的数据结构。这些结构的集合需要按浮点值排序。是否有一个基数排序实现。

如果没有，是否有快速访问指数、符号和尾数的方法。因为如果您首先根据尾数、指数和指数对浮点数进行排序。您在 O(n) 中对浮点数进行排序。

从具有 n 个数字的 int 中获取单个数字以用于基数排序算法的最佳方法是什么？我想知道在 C/C++ 中是否有特别好的方法，如果没有，一般的最佳解决方案是什么？

编辑：为了澄清，我正在寻找一个解决方案，而不是将其转换为字符串并将其视为数字数组。

我正在准备一场关于排序算法的考试。一位朋友给了我这个关于 LSD 基数排序的代码，我不明白他为什么使用数字 96,97 和 64？我读过一些关于 LSD 基数排序的东西，但我不明白它是如何工作的。