algorithm - 桶排序和基数排序有什么区别？

Question

桶排序和基数排序是近亲；桶排序从 MSD 到 LSD，而基数排序可以在两个“方向”(LSD 或 MSD)上进行。这两种算法如何工作，特别是它们有何不同？

Answer 1

RadixSort 和 BucketSort 的初始遍历完全相同。元素被放入增量范围(例如 0-10、11-20、... 90-100)的 buckets(或 bins)中，具体取决于最大的数字。

然而，在下一轮中，BucketSort 对这些“桶”进行排序并将它们附加到一个数组中。但是，RadixSort 附加桶而不进一步排序，并根据数字的第二位(十位)“重新分桶”。因此，BucketSort 对于“密集”数组更有效，而 RadixSort 可以很好地处理稀疏(好吧，不是完全稀疏，而是间隔开的)数组。