我从另一篇文章中读到这条评论 - 并想打开一个单独的问题:
桶排序对于“密集”数组更有效，而基数排序可以很好地处理稀疏(好吧，不完全是稀疏，而是间隔开的)数组。
请帮忙理解这是怎么回事？
据我了解，人口的“密度”将对两种算法的桶数产生同样的影响。
此外，插入排序(在每个桶中)不会受到密度的太大影响 - 或者是吗？
最佳答案
我认为“密集”与“间隔”背后的区别归结为被排序数据分布的均匀性，均匀分布的数据被视为“密集”。
由于桶排序根据数字值的上半部分按桶对其输入进行分区，因此具有均匀分布的输入将在每个桶中形成漂亮的短列表。相反，差距较大的输入会形成大量空列表，以及少量与原始输入长度相当的长列表。这对于基数排序的中间步骤来说是个坏消息，在该步骤中对单个桶进行排序，因为“分散”步骤并没有减少原始问题那么多。
另一方面，基数排序不关心输入中数字的分布:对于相同大小和最大成员中相同位数的任何输入，算法都需要相同的时间。每个“数字”的步骤恰好为 O(N) 个步骤；一旦你完成了最高有效数字，你就完成了。正在排序的值的分布不会影响算法的计时。
关于algorithm - 桶排序与基数排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17655933/