问题标签 [radix-sort]

i was wondering, when i have a list of integers and i need to sort them, and i know that they are integers in 32 bit, can i use radix sort (with counting sort as its stable sort) to sort them in o(n) time?

isn't it just 32 counting sorts using the bits representation on the numbers starting from LSB?

i know that general sorts with no previous knowledge of the numbers take o(nlogn), but isnt the fact that they are 32 bit integers is all i need to make it an o(n) sort?

thanks!

我不确定为什么有人会使用 LSD 基数排序。

MSD的优势：

1. 它可以处理可变长度的字符串
2. 它并不总是需要扫描整个字符串（它可以更快地决定顺序）
3. 可以使用插入排序来规避计数排序的缺点。

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

你好是我项目的一部分。关键是我必须对一个数字数组进行排序（比如 100~200 个 16 位数字，数字和位是事先固定的）。我想使用 GPU 的共享内存在一个块内对其进行排序，作为数据不能在中间离开芯片的要求的一部分。

我在 GPU 上阅读了一些基数排序、双音排序算法。但看起来它们是为大量数字而设计的。我想非常非常快地对这 100~200 个数字进行排序

我感谢任何想法/帮助

我在尝试实现基数排序时遇到了麻烦。这是一项任务，我的教授甚至不愿意为我指明正确的方向。我已经盯着这段代码很久了。有人可以向我解释为什么我的指针不起作用吗？我做了一些检查，发现我的指针甚至没有指向下一个指针，我很困惑为什么。我不是要求任何人做我的任务，只是一些方向。

我使用合并排序和基数排序的实现对一百万个长度约为 20 位的随机正长数进行了排序。归并排序比基数排序快得多，几乎快 6 倍。

我了解基数排序的时间复杂度也取决于整数的位数，但我的合并实现在所有输入大小上都击败了我的基数实现。

我正在使用我自己的队列类，它在我的基数排序中具有恒定的时间 push() 和 pop()。我在合并排序中使用数组。这与此有关吗？

这是合并排序

编辑： 我相当愚蠢地使用 LinkedList 样式队列。我将其更改为使用本机数组，现在合并排序的速度仅为之前的 6 倍。即使对于只有 10 位数长的数字，合并排序仍然更快。我猜 BigO 常数在这里起作用。对 push() 和 pop() 的数百万个函数调用也可能是这里的罪魁祸首。

考虑两个 k 位数（二进制表示）：

为了比较，我们从左到右扫描寻找 a 的出现0并检查相反的数字，如果该数字也是 a 0（对于两个数字），请注意如果找到这样的情况，则 the 的来源0小于 the 的来源1. 但如果数字是：

显然，这将需要扫描整个数字，如果我们事先没有被告知数字并简单地给出它们，那么：

比较需要$O(k)$时间。

因此，当我们查看诸如高性能快速排序之类的排序方法的代码时：

因此：T(n) = O(n) + O(nk) + 2*T(n/2) ---> T(n) = O(nklog(n))

这意味着快速排序比基数排序慢。

那我们为什么还要使用它呢？

我正在阅读 CUB 文档和示例：

在示例中，每个线程有 4 个键。看起来“thread_keys”将被分配到全局本地内存中。如果我每个线程只有 1 个密钥，我可以声明“int thread_key;”吗？并仅在寄存器中创建此变量？

BlockRadixSort(temp_storage).Sort() 将指向键的指针作为参数。这是否意味着密钥必须在全局内存中？

我想使用这段代码，但我希望每个线程在寄存器中保存一个键，并在排序后将其保存在寄存器/共享内存中。提前致谢！

我正在尝试通过一系列辅助函数在 SML 中实现基数排序。我遇到问题的辅助函数称为 sort_nth_digit，它需要一个要排序的数字位置和一个要排序的列表（分别为 n 和 L）。我这样做的方法是找到列表的前两个元素（现在我们可以假设至少有 3 个），按数字 n 比较它们，然后以正确的顺序将它们连接回列表中。该列表应按升序排序。现在，问题：函数编译，但我得到以下信息：

HW4.sml:40.5-44.30 警告：匹配非穷举 (0,L) => ... (n,nil) => ... (n,a :: b :: L) => ...

val sort_nth_digit = fn : int -> int list -> int list

此外，当您传递参数时，您没有得到我认为表明无限递归的答案？

问：匹配如何不详尽，为什么我会无限递归：

我在这里先向您的帮助表示感谢！(*我在stackoverflow上的第一篇文章^.^ *)

非详尽匹配修复：

没有输出的输入，控制台就在这一行：

nth_digit 和匿名助手 pow 的代码：

如果有人认为访问我的其余代码会很有用，我可以通过 github 将其作为 Eclipse 项目提供（如果您没有为 sml 设置 Eclipse，则只需拉取 .sml 文件）

本周，我们学习了各种不同的类型。基数排序的效率是惊人的。然而; 它仅限于某些数据。我想知道它是否可以与字符串一起使用。例如，“星期一”、“星期五”和“星期日”是我的数据集。有谁知道如何使用 Radix sort 对它们进行排序？或者任何人看过任何关于使用 Radix 对字符串进行排序的文章，与我分享。