我从另一篇文章中阅读了此评论 - 并想提出一个单独的问题：
桶排序对于“密集”数组更有效，而基数排序可以很好地处理稀疏（嗯，不完全稀疏，但间隔）数组。
请帮助理解这是怎么回事？
据我了解，人口的“密度”将平等地影响两种算法的桶数。
此外，插入排序（在每个桶中）不会受到密度的太大影响 - 或者是吗？
问问题
1076 次
2 回答
3
我认为“密集”与“间隔”背后的区别归结为被排序数据分布的均匀性，均匀分布的数据被认为是“密集”。
由于桶排序根据数字值的上半部分按桶划分其输入，因此具有均匀分布的输入将在每个桶中形成很好的短列表。相反，具有大间隙的输入会形成许多空列表，以及与原始输入长度相当的少量长列表。这对于基数排序的中间步骤来说是个坏消息，其中单个桶被排序，因为“分散”步骤并没有减少原来的问题那么多。
另一方面，基数排序不关心输入中数字的分布：该算法对其最大成员中相同大小和相同位数的任何输入花费相同的时间。每个“数字”的步数都采取精确的O(N)步数；一旦你完成了最重要的数字，你就完成了。被排序的值的分布不会影响算法的时间。
于 2013-07-15T14:15:07.350 回答
2
我猜该评论中的“稀疏”和“密集”指的是最终在同一个存储桶中的元素数量。
桶排序将输入范围拆分为多个桶，将每个元素放入正确的桶中，然后对这些桶进行排序。
例如，如果我们使用 10 个桶对 0 到 999 之间的数字进行排序，则第一个桶是[0-99]，第二个是[100-199]，依此类推。
如果几乎所有的值都小于 100，那么它们最终都会在同一个存储桶中。在这种情况下，桶排序将与对单个桶进行排序的算法（可能是插入排序）一样慢。
基数排序不使用另一种排序算法（如插入排序）对桶进行排序，而只是对每个数字分别应用某种桶排序。对于基数排序，有多少元素最终在同一个桶中是无关紧要的。
要添加后者的示例，假设我们尝试对[711, 411, 611, 911, 211]. 按最低有效位排序会将所有元素放在同一个桶中（顺序不变）。对第二个有效数字进行排序也是如此。只有当最高有效位被排序时，元素才会被放入不同的桶中。这对性能没有影响。
于 2013-07-15T14:02:10.767 回答