桶排序和基数排序的区别是什么？

Question

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

Answer 1

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

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