问题标签 [radix-sort]

我需要创建一个执行基数排序的方法，该方法使用按位运算符（>>、<<、&、|）从值中检索单个位。

该文件看起来像这样：

我目前已读入文件（其大小未知）。起初我将它们作为整数读入，但意识到我正在截断前导零。所以我将它们存储到 String[] 中。

这是我目前导入该文件的方法，该文件正在运行。我的所有其他方法都在工作，除了基数排序，我不确定从哪里开始按位运算。

我有排序如何工作的概念，但实施它似乎更具挑战性。

问候，

麦克风

大家好，我需要为任意数量的数字和值编写 RADIX 排序算法。我认为使用 LL 来操作比使用 Arrays 来存储 0-9 值更容易。我认为使用递归来解决这个问题会更好，但是我遇到了困难并且出错了

我真的很感激任何指导！:)

现在这回来了

最大尺寸？最多 10 个数字？2 未排序

74 63 87 52 1 99 10 74 67 49

已排序 49 63 87 52 1 99 10 74 67 49 结束

我有一个学校项目，我需要使用不同的排序算法对所有类型的数据类型进行排序。基数排序效果很好，但它不能对除整数以外的任何东西进行排序。我可能不会为除整数以外的任何东西添加排序结果，因为每种数据类型都会被排序为整数。

也就是说，我想知道是否有更好的方法将字符串转换为整数？这是我带来的。我不想超越 python 并尝试尽可能多地使用标准函数。

它确实运作良好，但我很高兴知道是否有更好的方法来处理它。对于它的价值，使用基数排序对整数以外的任何东西进行排序听起来毫无意义。因为即使您可以对整数列表进行排序。您必须将所有键的值返回到列表中。

我本来打算做这样的事情。对于我列表中的每个值，获取一个整数键。将该键放入哈希表中，并将值放入该哈希表的列表中。用整数键替换列表中的值，然后对键列表进行排序。

对于排序列表中的每个键，获取该键的值列表并弹出一项。将该项目放入列表中并继续。

我还想知道是否有一种方法可以优化此过程，以使其值得使用基数排序而不是其他不需要任何转换的排序。列表中的项目数量可能超过 50000。

编辑

实际上这里的代码不适用于不同大小的字符串。我不太确定如何检查。用空格填充字符串似乎有效。

大多数时候，我们使用内置库进行排序，它们是通用的。但大多数时候，我们也是根据数字索引或其他可以在索引中转换的值进行排序的。如果我没记错的话，排序数字是 O(n)。那么为什么我们根本不使用数字排序算法呢？

我正在努力在 DirectX11 中实现高效的基数排序。我需要快速排序不超过 256K 的项目。它不需要就地。使用 CUDA / OpenCL 不是一种选择。

我几乎可以使用它，但是它有一些问题：

• 直方图的生成速度很快，但仍然比网上引用的数字要长得多
• 在随后的排序过程中，由于 cp_sort 中直方图缓冲区上的 InterlockedAdd，不保留低位相同的键的顺序（见下文）
• cp_sort真的很慢，因为在同一个 InterlockedAdd 上进行全局内存访问

我一直在尝试了解如何根据在线算法解决此问题，但我似乎无法理解它们。

这是我的 3 个内核。（它用于广告牌粒子系统，所以术语“四边形”仅指要排序的项目）

任何人都可以就如何解决/优化这个问题提供任何帮助吗？我很想了解一些更复杂的 GPU 基数排序算法实际上在做什么！

谢谢！

我正在实现一个 2 字节的基数排序。这个概念是使用计数排序，对整数的低 16 位进行排序，然后对高 16 位进行排序。这允许我在 2 次迭代中运行排序。我的第一个概念是试图弄清楚如何处理底片。由于符号位将被翻转为负数，然后以十六进制形式，这将使负数大于正数。为了解决这个问题，我在符号位为正时翻转了符号位，以使 [0, 2 bil) = [128 000 000 000, 255 255...)。当它是负数时，我翻转了所有位，使其范围为（000 000 ..，127 255 ..）。这个网站帮助我获得了这些信息。为了完成它，我会根据 pass 将整数拆分为顶部或底部 16 位。以下是允许我这样做的代码。

要开始实际的基数排序，我需要形成一个大小为 65536 个元素的直方图。我遇到的问题是输入的元素数量非常大。创建直方图需要一段时间，所以我使用进程和共享内存并行实现它。我将数组划分为大小为 / 8 的子部分。然后在一个大小为 65536 * 8 的共享内存数组上，我让每个进程创建自己的直方图。之后，我将它们加在一起形成一个直方图。以下是代码：

下一部分是我花了大部分时间分析缓存如何影响前缀和的性能的地方。使用 8 位和 11 位通过基数排序，所有直方图都适合 L1 缓存。对于 16 位，它只适合 L2 缓存。最后，16 位直方图的求和速度最快，因为我只需要用它运行 2 次迭代。根据 CUDA 网站的建议，我还并行运行了前缀总和。在 2.5 亿个元素中，这比 16 位整数慢了大约 1.5 秒。所以我的前缀总和最终看起来像这样：

剩下的唯一事情就是向后遍历数组并将所有元素放入临时数组中各自的位置。因为我只需要经历两次，而不是从临时复制回数组，然后再次运行代码。我首先使用数组作为输入运行排序，并将 temp 作为输出。然后使用 temp 作为输入和 array 作为输出第二次运行它。这使我无法两次将内存复制回数组。实际排序的代码如下所示：

这个链接包含我到目前为止的完整代码。我对快速排序进行了测试，整数和浮点数的运行速度提高了 5 到 10 倍，而 8 字节数据类型的运行速度提高了大约 5 倍。有没有办法改善这一点？

我正在尝试提出一种基本的基数排序（我从未真正见过，所以如果我的很糟糕，我很抱歉），但我EXC_BAD_ACCESS在线上遇到了一个错误link = *(link.pointer);。我的C技能不是很好，所以希望有人能教我我做错了什么。

我正在使用 XCode 并且启用了 ARC。

这是代码：

此外，如果有人想对我的排序提出改进建议，那也将不胜感激。

我最近尝试为一对整数向量实现基数排序（其中仅当第一个元素相等时才考虑第二个元素）。我通过两次应用计数排序来做到这一点——首先是对中的第二个元素，然后是第一个元素。这是我最初实现计数排序的方式：

第一个 for 循环显然在 O(n) 中运行。由于“mat”数组正好有 n 个条目，因此在第二个（嵌套）循环中最多会访问 2n 次。这意味着上述代码的时间复杂度应该是 O(n)。

然后我将这段代码的运行时间与 STL sort()（时间复杂度为 O(nlog(n))）进行比较，方法是在 10^6 个元素的数组上运行它们。令我大吃一惊的是，STL sort() 最终表现得比我实现的基数排序稍好。

然后，我将计数排序实现更改为以下内容：

这一次，基数排序确实比 STL sort() 快了大约 5-6 倍。这个观察让我想知道为什么我的第一个基数排序实现比第二个运行慢得多，当它们都是 O(n) 时？

我正在寻找一种快速稳定的基数排序实现（支持浮点数），它返回排序顺序的索引而不是排序值。

Pierre Terdiman在他的文章“Radix Sort Revisited”中的版本正是我想要的，但是它已经超过 13 年了，不适合现代流水线 CPU。

来自“Radix Tricks”的 Michael Herf 的RadixSort11非常快，唯一的问题是它返回排序后的值而不是索引，此外它还破坏了输入数组的值。

任何帮助，将不胜感激。

我在这里使用这个程序作为参考，看看算法是如何实现的。除了这一部分，我理解了大部分内容：

我不明白作者在那个循环中在做什么。有人可以解释发生了什么吗？
是的，我正在用纸笔看看发生了什么。只是想我可以澄清一下