问题标签 [radix-sort]

假设我有一堆数字。我必须首先将最低有效数字放入相应的存储桶中。例如： 530 ，我必须先放入 0 号桶。对于 61 号，我必须放入 1 号桶。

我计划使用多维数组来做到这一点。所以我创建了一个二维数组，它的 nrows 是 10（对于 0~9），ncolumns 是 999999（因为我不知道这个列表会有多大）：

然后我创建了一个节点调用 a。在这个节点a中，有一个值50。为了找出我想把它放在哪个桶里，我计算了“左”，我得到了0。所以我想把这个a->值放到桶0里。但是现在我我被困住了。如何将此值放入存储桶中？我必须使用指针数组来做到这一点。

想了很久，还是没有找到好的办法。所以请和我分享一些想法。谢谢你！

我有一个队列和一个队列数组。buckets是数组，collector是队列。pass是一个整数，它保存了它的传递。我有一个方法可以将队列的第一个单元格的包含返回给我peek()。shiftOne()是一种将一个队列的头部移动到另一个队列尾部的方法。

现在这段代码对我不起作用

我一步一步地走了，结果我没有正确地掩盖这些位。我可以改变它们，但仅此而已。所以我将尝试访问元素 102 以获得 10 元素数组。我究竟做错了什么？我知道peek()，shiftOne()因为我可以使用幂和模数进行排序。

我知道如何使用基数排序对整数进行排序。

但是如何使用它对字符串进行排序呢？还是浮点数？

我的家庭作业有问题，我不知道我哪里做错了。我必须为带有 aa 桶和 k 轮的基数排序设计一个函数。我需要保留桶中列表项的顺序，因此我需要为每个桶保留两个点 - 前后。但是，当我编译代码并使用需要排序的 10 个数字运行测试代码时，我的输出仅包含 3 个数字。如果它有 20 个数字，它只打印 2。你能帮帮我吗？这是我的代码，感谢您抽出宝贵时间。编辑：至少SigDig我的意思是有效数字我必须改变它，因为它的名字不好

I was studying the radix sort algorithm but I could not understand some of the original source code.

I don't know why its using this line for (i = 0; i < len; i++) x[i] ^= INT_MIN;

I know its xor but I don't understand the use of this operator in this context.

我有一组整数值，我想使用 Thrust 对它们进行排序。在这种排序中是否有可能只使用一些高位/低位。如果可能的话，我不想使用用户定义的比较器，因为它将使用的算法从基数排序更改为合并排序，并大大增加了经过的时间。

我认为当所有数字在一个位上具有相同的值时，在排序时会跳过该位，因此使用尽可能低的位号是否可行，并希望它就足够了。（即：对于 5 位，使用 8 位的 char 并将高 3 位设置为 0）

例子：

仅使用 4 位排序，高或低..

类似于 http://www.moderngpu.com/sort/mgpusort.html

我想知道遵循基数排序程序的逻辑。

我被卡住了，因为我不太了解 while(1) 循环..

到目前为止，我所知道的是：

bit这与in的值相同rad_short_u()

我已经调试了程序，由于rand() % 512-256，还生成了一些 -ve 值，

在第一次传递期间，它将所有 -ve 值交换到一侧（从开始）和 +ve 之后从下一次传递它向左移动到 1 位，因此位的值从那时变为 1073741824 直到它变成 1 数组保持不变。

请帮助我理解程序逻辑。

如果我们必须对 4 个数字中的 7 个数字进行排序，那么在最坏的情况下需要进行多少次比较？（基数排序）选项是 - 40,38,47,280。

我的解决方案——我拿了 10 个桶（0 到 9）（链表）。然后对于第 i 个数字的每个数字，我将其放入 Bucket 中，对应于其数字的值。然后我将这些数字收集到数组中。对所有数字重复此过程，因此我的原始数组已排序。比较总数= 10*4=40（10，因为我遍历了所有的桶来寻找对应的桶）。

现在问题出在蒂莫西·J·威廉姆斯（Timothy J Williams）的书中，给出的比较数=数字数*数字数*桶数=4 * 7 * 10 = 280。我无法理解。有人可以解释一下这是怎么回事。

“算法简介”一书提到了基数排序的 LSD（最低有效位）版本。但是，正如其他人在 stackoverflow 中指出的那样，还存在 MSD（最高有效位）版本。所以我想知道这些的优缺点。我的猜测是 LSD 版本比 MSD 版本有一些好处，但我不确定。因此问题。

可能重复：
长度为 N 的数组可以包含值 1,2,3 ... N^2。是否可以在 O(n) 时间内排序？

给定n范围内的数字，[0,n^2 -1]我们如何在O(n)运行时间内对它们进行排序？

我有一种解决方案涉及的感觉radix sort，但我仍然缺少一些东西。

n数字是整数。

有任何想法吗 ？

备注：不是作业！

问候