algorithm - 使用桶算法排序

Question

排序时到底是什么定义了桶的大小？就像计数一样，大小将从 0 到最大，而在基数中，桶大小是 0-9。

标签： algorithmsorting

Answer 1

桶排序中“桶”的数量对应于并取决于要排序的可能值的范围。例如，如果我正在考虑以下值：

1, 4, 10000, 5, 12

我排序的值的范围是 9999。

range = (highest value) - (lowest value) = 10000 - 1 = 9999 buckets

这意味着我将需要 9999 个桶来尽可能高效地对这些值进行排序。这是因为桶排序不是比较排序。这意味着值不会相互比较以确定它们的顺序。它们被简单地放置在代表它们的值的桶中。桶排序因此而被誉为O(n)，但实际上由于需要创建大量桶，它的效率往往要低得多。

在前面的示例中，我们只对 5 个值进行排序，但需要创建超过 10,000 个桶。当桶的数量在O(N^2)的时间复杂度内时，这是非常低效的，这使得桶的排序与传统的比较排序算法一样耗时（如果不是，更糟）。但是，如果条件合适，那么桶排序可能是一个不错的选择。