问题标签 [radix-sort]

基数排序是否能够对浮点数据进行排序，例如 0.5、0.9、1.02 等？

我刚刚写了一个简单的迭代基数排序，我想知道我是否有正确的想法。
递归实现似乎更为常见。

我正在排序 4 字节整数（无符号以保持简单）。
我使用 1 字节作为“数字”。所以我有 2^8=256 个桶。
我首先对最高有效数字 (MSD) 进行排序。
每次排序后，我按照它们在桶中存在的顺序将它们放回数组中，然后执行下一个排序。
所以我最终做了4桶排序。
它似乎适用于一小组数据。因为我正在做 MSD，所以我猜它不稳定，可能会因不同的数据而失败。

我错过了什么重要的事情吗？

更新：
似乎以 LSD 形式运行良好，可以通过更改基数中的块循环来修改它，如下所示：

好的，所以我必须为无符号整数和浮点数创建一个基数排序。我的无符号整数版本可以正常工作，但我在让它用于浮点值时遇到了一些麻烦。基本上它按浮点数的整数值对我的数组的值进行排序，但它不会根据十进制值对其进行排序。（例如 36.65234 将出现在 36.02311 之前，如果它在未排序的数组中排在第一位）这个代码段是我进行位操作和屏蔽的地方，我很确定这是我的问题所在。

提前致谢！

我还在学习 Haskell，我写了以下基数排序函数。它似乎工作正常，但问题是它的内存效率相当低。如果使用 ghc 编译，内存已经超过 500MB，输入列表大小为 10000 个元素。

所以我想问你如何改进以下算法/代码以使其在速度和内存方面更有效率。最好的起点是什么？

基数排序从租用有效位到最高有效位对数字进行排序。我有以下情况：

我的字母表是英文字母表，因此我的“数字”是英文字符串。这些字符串的字符从左到右一次显示一个。也就是说，首先显示所有字符串的最高有效数字，依此类推。在任何阶段，我都会有一组经过排序的 k 个字符的长字符串。此时，每个字符串都会显示一个字符。我想对新的字符串集进行排序。我如何在不从头开始的情况下有效地做到这一点？

例如，如果我有以下排序集 { for, for, sta, sto, sto }

并且在每个字符都显示出来之后，集合是 { form, fore, star, stop, stoc }

新的排序集应该是 {fore, form, star, stoc, stop }

我希望在添加每个新字符后有一个复杂度 O(n)，其中 n 是集合的大小。

正如标题所说，基数排序是唯一的非比较排序算法吗？我的猜测是肯定的。

我正在尝试实现块排序。这是来自 Burrows Wheeler 的论文。

（在此步骤之前，您创建一个 S 的 V 后缀数组）

Q4。[基数排序]
对 V 的元素进行排序，使用每个后缀的前两个字符作为排序键。这可以使用基数排序有效地完成。

所以我知道您正在使用基数排序对后缀进行排序。
这应该如何更新数组 V？只有在基数排序完成后，我才能知道后缀的排序位置。假设第 4 个后缀最终成为排序后的第一个。所以 V[0] = i。在这种情况下，我们知道（因为我告诉过你）i = 4。但是算法如何知道这一点，因为我们没有跟踪它们的位置。我应该创建一个包含后缀及其后缀编号的类吗？

基数排序的时间复杂度是 O(kn)，其中 n 是要排序的键的数量，k 是键的长度。类似地，在 trie 中插入、删除和查找操作的时间复杂度为 O(k)。但是，假设所有元素都是不同的，不是 k>=log(n) 吗？如果是这样，这意味着基数排序的渐近时间复杂度为 O(nlogn)，与快速排序相同，而 trie 操作的时间复杂度为 O(logn)，与平衡二叉搜索树的时间复杂度相同。当然，常数因子可能有显着差异，但渐近时间复杂度不会。这是真的吗？如果是这样，基数排序和尝试比其他算法和数据结构有其他优势吗？

编辑：

Quicksort 及其竞争对手执行 O(nlogn)比较；在最坏的情况下，每次比较将花费 O(k) 时间（密钥仅在检查的最后一位数字处不同）。因此，这些算法需要 O(knlogn) 时间。按照同样的逻辑，平衡二叉搜索树操作需要 O(klogn) 时间。

我在win-XP + VS2005 下尝试编译美林的基数排序时出现错误。

错误：asm 操作数类型大小 (1) 与约束“r”隐含的类型/大小不匹配。

它出现在以下代码中

谢谢

如果可能在 C# 中（但不是强制性的），我正在为 Dictionary/KeyValuePair Collection 寻找一种快速有效的 Radix-Sort 实现。键是介于 1 000 000 和 9 999 999 999 之间的整数。值的数量在 5 到数千之间变化。目前我正在使用 LINQ-OrderBy，我认为这是 QuickSort。对我来说，性能真的很重要，我想测试 Radix-Sort 是否会更快。我发现只有 Array 实现。当然我可以自己尝试，但因为我是这个主题的新手，我相信它不会是最快和最有效的算法。;-） 谢谢。

雷内