问题标签 [radix-sort]

我正在阅读基数、计数和桶排序的定义，似乎所有这些都只是下面的代码：

我知道我不可能是对的，所以我错过了什么？如果您认为这有助于用 Java 或 C 进行解释，请显示代码。

我已经尝试了几个小时才能让它工作，但无论出于何种原因，我都无法正确打印我的数组。这是我的代码（下面的 .txt 文件）

这是它生成的文本文件的一部分：

我不知道为什么这对我来说很难缠住我的头。我浏览了 wiki 页面和伪代码（以及实际代码），试图了解基数排序算法是如何工作的（关于存储桶）。

我在这里寻找错误的东西吗？我应该研究桶排序吗？有人可以给我一个简化版的它是如何工作的吗？作为参考，这是一个据称执行基数排序的代码块：

我还研究了非递归解决方案：

具体来说，这条线给我带来了麻烦。我试过用笔和纸走过它，但我仍然不知道这是在做什么：

我知道计数和基数排序通常被认为在 O(n) 时间内运行，我相信我明白为什么。然而，我在作业中被要求解释为什么这些排序不一定在 O(n) 时间内对不同的正整数列表进行排序。我想不出任何理由。

任何帮助表示赞赏！

我现在正在研究实现计数排序的基数排序。我想我在很大程度上理解并遵循了伪代码，但是我得到了一个数组越界错误：

我的代码

我正在尝试为整数（包括负整数）实现基数排序。对于非负整数，我计划为数字 0-9 创建一个包含 10 个队列的队列，并实现 LSD 算法。但我有点对负整数感到困惑。我现在在想的是，继续为它们创建另一个包含 10 个队列的队列并分别对它们进行排序，然后最后，我将给出 2 个列表，一个包含已排序的负整数，另一个包含非负整数。最后我会合并它们。

你怎么看待这件事？有没有更有效的方法来处理负整数？

我正在阅读算法介绍第 2 版，有一个问题说我们可以对 n 个整数进行排序，这些整数在线性时间内介于 0 和 n ³ -1 之间。我正在考虑 IBM 的基数排序方法。我从最低有效数字开始，根据最低有效数字分开数字，然后排序，然后根据下一个最低有效数字分开，依此类推。每次分离需要 O(n) 时间。但我有一个疑问，例如，如果其中一个数字由 n 位组成，那么算法需要 O(1*n+2*n+...+n*n)=O(n ² ) 时间，对吗？我们能否保证数字由少于 n 个数字组成，或者任何人都可以为这个问题提供另一个提示？谢谢

我需要一个存储元组的数据结构，并允许我进行如下查询：给定(x,y,z)整数元组，找到下一个（它的上限）。我的意思是考虑自然排序(a,b,c)<=(d,e,f) <=> a<=d and b<=e and c<=f。我尝试过 MSD 基数排序，它将项目分成桶并对它们进行排序（并对元组中的所有位置递归地执行此操作）。有人有其他建议吗？理想情况下，我希望上述查询发生在 O(log n) 内，其中 n 是元组的数量。

我知道基数排序通过比较数字的数字来工作。我的问题是，假设我们有不同位数的不同数字。基数排序在这里工作吗？我们可以简单地假设，例如，如果我们比较两个数字，一个是 3 位数字，一个是 6 位数字，较小数字的前 3 位是 0。但是如何实现呢？我们如何让程序假设如果没有足够的数字，那么这些数字为零？

谢谢你。

我正在探索以下算法：

1. 计数排序
2. 基数排序
3. 桶排序

我知道这三个都能够在最好的情况下以线性时间运行，但是我很难理解这些情况何时发生，除了计数排序的情况。

这是我对计数排序的理解，以及如果可能的话，我希望如何回答其他两种算法：

当您希望排序的信息之间没有大的差距时，计数排序以线性时间运行。例如 1、10^5 和 545 等会创建一个大数组，并且使用内存和遍历效率不高，因此这将是使用计数排序的“最坏情况”，因此最好的情况是当差距很小。

如果有人可以帮助我了解线性时间发生时基数和桶排序最佳情况的条件，我将不胜感激。