问题标签 [radix-sort]

首先，我应该提到我的编码时间并不长，尽管从我的代码中可能很明显：P

我遇到了两个问题，首先排序功能不正常，但确实按长度对数字进行了排序。这里的任何帮助将不胜感激。

其次，它同时改变了它抓取的表和它返回的表（不知道为什么）。我如何防止它改变它抓住的桌子？

如果人们没有发布完全优化的预制代码，我会更喜欢，因为我不会以这种方式学习或理解任何东西。

下面是来自教科书的 Java 中的 LSD 基数排序实现，用于对字符串数组进行排序，其中每个字符串都包含精确的W字符。

我想计算运行时数组访问的次数。我读过 LSD 排序应该需要n * c数组访问，其中n字符串c的数量和每个字符串中的字符数量是多少。但是，下面的算法会多次访问多个数组。如果我在其中的每一个上增加一个计数器，我最终会得到nc.

那么在算法的上下文中究竟是什么构成了“数组访问”呢？是否只有一个数组访问实例被认为更重要，我应该在这里计算，或者这个示例实际上是一个低效的实现，它使用了比必要更多的数组访问？

如果我们有一些m > 0 并且需要提供一种算法来在时间 O(mn)内对 0 到n^m -1 范围内的n 个整数进行排序。我的建议是：

我的论点是，上述内容将以 O(mn) 运行，因为对于每个数字 t - 插入排序将花费 O(n) 时间，因为每次运行的范围很小。

这是正确的建议吗？上面的空间要求应该是多少？

谢谢。

我正在为本周的考试而学习，我遇到了一个复习问题，问...

0 范围内的两千万个正整数。. . 99,999,999 将通过 LSD 基数排序进行排序。比较使用 radix 0 的性能。. . 9999 和基数 0 。. . 9. 展示你的作品。

我知道基数排序的时间是 theta(d(k+n)); 其中 d = 位数 k = 基数的大小和 n = 记录数。

我知道十进制基数是 theta(8(10+20,000,000))，对吗？

千位基数是多少？θ（3（1000+20,000,000））？

我正在尝试编写一个基数排序，它使用一个随机数向量和一个向量向量作为 bin。

这是代码，错误在收集和/或分发函数中的某个地方 - 任何帮助将不胜感激，我只是没有发现它。它没有给我一条错误消息，只是崩溃了。这是我的代码：

我正在尝试实施美式桶排序。Wiki 说“首先计算将落入每个箱子的对象数量，然后将每个对象放入其桶中。”

在第二阶段，将对象放置在适当的桶中时，我需要使用辅助数组吗？有没有办法通过在线性时间内交换数组元素来做到这一点？

我使用来自SciPy的数组重写了来自Wikipedia的 Python 原始基数排序算法，以提高性能并减少代码长度，我设法完成了这一点。然后我从Literate Programming中采用了经典的（基于内存的、基于枢轴的）快速排序算法，并比较了它们的性能。

我曾期望基数排序会在超过某个阈值时击败快速排序，但事实并非如此。此外，我发现Erik Gorset 的博客提出了一个问题“基数排序比整数数组的快速排序更快吗？ ”。答案是

.. 基准测试显示 MSB 就地基数排序始终比大型数组的快速排序快 3 倍以上。

不幸的是，我无法重现结果；不同之处在于 (a) Erik 选择了 Java 而不是 Python，并且 (b) 他使用MSB in-place radix sort ，而我只是在 Python 字典中填充存储桶。

根据理论，基数排序应该比快速排序更快（线性）；但显然这在很大程度上取决于实施。那么我的错误在哪里？

这是比较两种算法的代码：

这是比较大小在 2 到 1250 范围内的整数数组（水平轴）的排序持续时间（以秒为单位）（对数垂直轴）的结果；下面的曲线属于快速排序：

• 基数与快速排序比较

快速排序在功率变化时是平滑的（例如在 10、100 或 1000），但基数排序只是跳跃一点，但在质量上遵循与快速排序相同的路径，只是慢得多！

在我的日常工作中，我经常使用包含数百万行，有时是数亿行，有时甚至超过 10 亿行的数据集。这些数据集通常需要排序。键几乎总是大整数值（通常是 9 位）。有时数据集具有 9 位和 3 位的复合键。

我想知道是否有可能在 SAS 中实现一个（LSD 优先）基数排序宏，它可以用来代替PROC SORT减少对这些数据集进行排序所花费的时间。我已经调整了排序以在适当的情况下使用压缩，仅保留相关字段（或使用标签排序），适当调整字段长度，不要进行不必要的排序等等......

我使用的硬件有局限性——假设我只有 2G 的内存可供 SAS 使用，因此该解决方案不需要将所有键值放在内存中的临时数组中（至少不是一次全部）。

该解决方案是否会比 proc 排序提供性能改进？有没有人已经实施过这样的事情或有经验？我在浪费时间吗？

试图了解我的数据结构类的基数排序。我的老师向我们展示了 C++ 中的基数排序示例。我不明白数字的 for 循环是做什么的，她说了一些关于最大数字的事情。此外，当我在 VS 中尝试此操作时，它说 log10 是对重载函数的模棱两可的调用。

谁能解释这个 for 循环的作用以及为什么我得到那个模棱两可的调用错误？谢谢

我尝试编写 C++ 代码来对整数进行基数排序。看了网上的教程，我发现我们必须把每个整数放到正确的桶里，从最不重要的数字开始。我的问题是，在基数排序的普通算法中，我是否需要从 0 到 9 的 10 个桶？如果我将这些存储桶分配为链表（例如 *list1 ~~~ *list9），会不会有点奇怪？

感谢您的时间。这不是功课，只是出于好奇。