问题标签 [radix-sort]

我基本上是计算机科学的初学者。如果我问基本问题，请原谅我。我想了解基数排序。我读到一个 32 位无符号整数可以分解为 4 个 8 位块。之后，只需要“4遍”即可完成基数排序。有人可以给我看一个例子，说明这个分解（32 位到 4 个 8 位块）是如何工作的？也许，一个 32 位整数，如 2147507648。

谢谢！

我想了解基数排序。我刚刚在这里发布了这个问题，并了解了如何将 32 位整数分解为 4 位块。4次通过怎么办？例如：2147507648 可以分解为 128 0 93 192。2147507672 产生 128 0 93 216。LSD 基数排序不会将 216 与 192、93 与 93、0 与 0 以及 128 与 128 进行比较吗？将 216 与 128 本身进行比较需要 3 次传球，对吗？

谢谢！

我明白 32 位整数被分解为 8 位块。有人可以给我更多关于通行证如何工作的解释吗？一个简单的例子将帮助我更好地理解它。例如，我有 2147507648 和 2147507672。我将它们分解为 8 位块。128 0 093 216 是 2147507672 的细分，128 0 093 192 是 2147507648 的细分。

我了解 LSD 基数排序如何适用于基数 10。如果有人能告诉我在获得 8 位块后如何对这些 32 位整数进行排序，我将不胜感激。

非常感谢！

我正在尝试在 C 中为整数实现基数排序，但遇到了一个似乎无法修复的循环错误。这是代码和输出。我不知道错误的确切部分，所以请原谅帖子的长度。

有人可以指出我的错误吗？

输出：

未排序的原始列表： 整数：26054 十六进制：0x65c6 整数：3051 十六进制：0xbeb 整数：38586 十六进制：0x96ba 整数：39549 十六进制：0x9a7d

排序列表： 整数：3051 十六进制：0xbeb 整数：3051 十六进制：0xbeb 整数：3051 十六进制：0xbeb 整数：3051 十六进制：0xbeb

排序缓冲区：int：3051 hex：0xbeb int：3051 hex：0xbeb int：3051 hex：0xbeb int：3051 hex：0xbeb

我可以使用一些帮助。你将如何在 python 中编写一个实现基数排序的程序？

这是一些信息：

基数为 10 的整数的基数排序是基于对穿孔卡片的排序，但事实证明这种排序非常有效。排序使用一个主箱和 10 位箱。每个 bin 就像一个队列，并按照它们到达的顺序维护它的值。该算法首先将每个数字放在主箱中。然后它考虑每个值的个位。第一个值被删除并放置在与个位对应的数字箱中。例如，534 放置在 4 号位，662 号放在 2 号位。一旦主箱中的所有值都放入对应的 1 号位中，则从 0 号箱到 9 号箱中收集这些值（在该订单）并放回主箱中。该过程以十位数、数百位数等继续。处理完最后一位数字后，主箱按顺序包含值。使用随机找到的 randint 创建从 1 到 100000 的随机整数。使用列表理解创建不同大小的列表（10、100、1000、10000 等）。要使用索引访问数字，首先将整数转换为字符串。要使这种排序起作用，所有数字必须具有相同的位数。要使用前导零填充整数，请使用字符串方法 str.zfill()。对主 bin 进行排序后，将字符串转换回整数。要使用前导零填充整数，请使用字符串方法 str.zfill()。对主 bin 进行排序后，将字符串转换回整数。要使用前导零填充整数，请使用字符串方法 str.zfill()。对主 bin 进行排序后，将字符串转换回整数。

我不知道如何开始，任何帮助表示赞赏。谢谢你。

我真的很困惑“就地”MSD基数排序算法：

然后使用下一个数字递归处理每个 bin，直到所有数字都用于排序。

我很困惑，因为在我看来递归意味着 O(n) 堆栈空间，其中n是最长字符串的长度（以位数为单位），对吧？

在我看来，避免堆栈溢出的唯一方法是使用堆空间——但是根据任何定义，该算法不再是“就地”的。

那么，如何就地进行 MSD 基数排序呢？

我用 C++ 编写了一个间接基数排序算法（间接，我的意思是它返回项目的索引）：

它的执行速度似乎比std::sort我使用以下代码测试时快 40%（3920 毫秒与 6530 毫秒相比）：

嗯，我想这是我能做的最好的了，我想。

但是在我多次撞墙之后，我意识到在开始时预取radix_ipass可以帮助将结果减少到1440 毫秒（！）：

显然，瓶颈是内存带宽——访问模式是不可预测的。

所以现在我的问题是：我还能做些什么来让它在类似数量的数据上更快？

还是没有太大的改进空间？

（我希望尽可能避免损害代码的可读性，所以如果可读性受到损害，改进应该是显着的。）

我对网络上的许多 python 基数排序实现感到非常沮丧。

他们始终使用 10 为基数，并通过除以 10 的幂或取数字的 log10 来获得他们迭代的数字的位数。这是非常低效的，因为与位移相比，log10 并不是一个特别快的操作，位移快了近 100 倍！

更有效的实现使用 256 的基数并逐字节对数字进行排序。这允许使用非常快速的位运算符来完成所有“字节获取”。不幸的是，似乎绝对没有人在 python 中实现了使用位运算符而不是对数的基数排序。

所以，我把事情掌握在自己手中，想出了这个野兽，它在小型数组上的运行速度大约是 sorted 的一半，在更大的数组上运行速度几乎相同（例如len，大约 10,000,000）：

这个版本的基数排序通过查找它必须排序的字节来工作（如果你只传递低于 256 的整数，它只会排序一个字节，等等），然后通过将每个字节从 LSB 向上排序，将它们按顺序转储到桶中然后只是将桶链接在一起。对需要排序的每个字节重复此操作，您在 O(n) 时间内就有了漂亮的排序数组。

但是，它并没有尽可能快，在我将它作为比所有其他基数排序更好的基数排序之前，我想让它更快。

运行cProfile这个告诉我很多时间都花在了append列表的方法上，这让我觉得这个块：

在radix_sort_offset吃很多时间。这也是一个块，如果你真的看它，它为整个排序完成了 90% 的工作。这段代码看起来可以被numpy-ized，我认为这会带来相当大的性能提升。不幸的是，我对numpy's 更复杂的功能不是很好，所以无法弄清楚。帮助将不胜感激。

我目前正在使用itertools.chain.from_iterable扁平化buckets，但如果有人有更快的建议，我相信它也会有所帮助。

最初，我有一个get_byte返回n数字的第 th 字节的函数，但内联代码给了我巨大的速度提升，所以我做到了。

任何其他关于实现的评论或挤出更多性能的方法也值得赞赏。我想听听你所拥有的一切。

我正在尝试用 Java 编写 RadixSort 的示例，虽然我了解算法的工作原理，但我在实现队列链接列表时遇到了一些问题。

我相信我的问题是当我用新的 Queue 更新第 n 个位置的链表作为它的值时。我相信我对每个节点更新使用相同的队列，这导致我为链表中的每个节点获取相同的值。

所以当从一个数组开始时int[] theArray = {4,3,5,9,7,2,4,1,6,5};

我最终得到了一个包含 10 个节点的链表，每个节点都包含一个队列：{4,3,5,9,7,2,4,1,6,5}

我认为通过使用new关键字它会创建一个新实例，但似乎每次迭代都会继承旧值。

有人可以解释或指出正确的方向来理解为什么会发生这种情况吗？

编辑：（忘记附上代码）

编辑2：

我一直在玩它，它似乎thisQueue是共享的lists。当我对诸如queue执行某些操作时，会全面添加“1”的值。如果我对每个节点执行相同的操作，则填充值 1。thisQueuethisQueue.add(1)listslists.add(1)lists

我记得读过一些关于通过引用传递的对象值（虽然不是对象本身），这与我所经历的有什么关系吗？

编辑3：

我还注意到，如果我在行中使用文字而不是变量，.add()例如

如编辑 2 中所述，这些值不会重复。我尝试将使用的变量转换为int即使它们被声明为 Int，但仍然得到相同的结果。

使用 JAVA 我试图通过基数排序对整数数组（升序）进行排序，但似乎没有解决这个错误。

如果您运行它，您会看到它开始正常，但在第一次迭代中，下一个数字被复制。我尝试了几种方法，但无法弄清楚。

第一次迭代：457、657、839、436、839、355、720，第二次迭代：457、657、436、657、355、720、720，第三次迭代：657、436、657、657、720、720、720 ,