是什么使Bucket Sort好?

因此,我无意间发现了基于非比较排序的算法桶排序是准确的,我无法确切地知道为什么它是好的。

我有一个想法,但我需要有人确认。

假设我要排序一个1000个元素的数组,如果它是均匀分布并存储在10个存储桶中的,每个存储桶有100个元素。

使用n log(n)算法将10个元素排序10次= 10 * 100 log(100)= 1000 log(100)= 2000

使用n log(n)算法对1000个元素进行排序时= 1000 log(1000)= 3000

因此,该算法利用以下方法:如果n = m + l,则(m + 1)^ 2> m ^ 2 + l ^ 2,并且同样适用于n log(n)算法

因此,将数据存储在桶中越均匀,存储桶排序的性能就越好

这是正确的吗 ?

最佳的桶数是多少? (我认为这是时空折衷的事情,但也取决于要排序的数据的一致性)

评论