algorithm - 使用桶算法排序

Question

排序时究竟是什么定义了桶的大小？就像在计算大小将从 0 到最大值，在基数中，桶大小为 0-9。

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) 的时间复杂度内时，这是非常低效的，这使得桶排序与传统的比较排序算法一样耗时(如果不是，则更糟)。但是，如果条件合适，那么桶排序可能是一个不错的选择。