问题标签 [bucket-sort]

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

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

我刚刚阅读了有关Bucket sort的维基百科页面。在这篇文章中，他们说最坏情况的复杂度是 O(n²)。但我认为最坏情况的复杂度是 O(n + k)，其中 k 是桶的数量。这就是我计算这种复杂性的方式：

1. 将元素添加到存储桶。使用链表这是 O(1)
2. 遍历列表并将元素放入正确的桶中 = O(n)
3. 合并桶 = O(k)
4. O(1) * O(n) + O(k) = O(n + k)

我错过了什么吗？

我试图优化我的快速排序以提高性能。对于 4M (1<<22) 个整数项（每个 4 个字节），在可以支持 72 个并发线程（72 个内核）的系统上进行排序需要 0.5 (0.499703) 秒的并行快速排序算法。我有兴趣了解进一步优化并行快速排序的有效方法。此外，在给定工作量的情况下，如果所有排序算法都有一个排名表，是否有兴趣与其他排序算法进行比较？

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

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

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

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

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

我有四个数据集（请耐心等待）：

• 第一表：matlab 中一列 txt 格式的 10 个股票代码（股票代码）列表。
• 第二个表：一列中数字格式的日期（双格式为 10 天）。
• 第三张表：我有 10*10 的随机数数据集（为简单起见假设 0-1）。（例如每股收益增长每股收益）——所以我希望在我的投资组合构建排名中实现高每股收益增长。
• 第 4 表：我还有另一个 10*10 的随机数数据集（为简单起见假设 0-1）。（例如每天的市盈率）。-所以我希望我的投资组合构建排名中的市盈率较低。

现在：我想对每天由表一中的 3 只股票（最大值）和表 2 中的底部三只股票（最小值）组成的股票组合进行排名。输出必须是基于两个因素的组合排名（如所述的表 3 和 4）的每天的代码列表（在这种情况下为 3 个）。

有任何想法吗？简而言之，我最终需要一个带有三个股票代码的顶级桶......

我正在尝试在 C++ 中创建一个桶排序算法，但它根本不起作用。每次运行时，它都会将许多新数字添加到数组中，这些数字通常非常大，例如数十亿。有人知道为什么是这样吗？这是代码 - （请注意，我传入一个大小为 100 的数组，随机数从 0 到 ~37000，并且插入排序功能功能齐全并经过多次测试）

如果有人能指出问题所在，将不胜感激。

在下面的代码中，我正在对桶排序的实现进行基准测试。

该bucketsort函数使用结果，_bucketsort但将其展平为单个列表。令我惊讶的是，这个过程 ( Map.toList) 需要很多时间。

这是 Criterion 的基准测试的输出：

bucketsort如果我的函数可以写得更好并且希望更快，我不会感到惊讶。但到目前为止我还没有弄清楚怎么做。

此外，非常欢迎对我的 Haskell 代码进行任何改进/评论。

我在 Java 中实现桶排序，我发现当输入数组被排序（升序或降序）而不是随机时，它的排序（升序）更快。为什么是这样？据我了解，它只是遍历数组并在每个元素的索引处递增“计数”数组。我不明白为什么使用排序输入它会运行得更快，但它似乎快了两倍。

谢谢

我正在探索以下算法：

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

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

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

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

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