桶排序是否要求您事先知道值的范围？

Question

我正在学习桶排序，似乎很多 material 坚持认为当键值“均匀分布并且用于对已知范围内的整数进行排序”时它是有效的。我理解均匀分布的部分，但是你也必须知道范围吗？如果不提供范围，在桶排序时创建辅助数组时，是否可以简单地创建一个可以自行扩展的动态数组（ArrayList）？

Answer 1

如果您不知道范围并且满足值 1000000 - 它属于第一个桶吗？到第 10 个桶？到第 1000 个桶？

假设您认为它属于第 10 个桶（每个桶指的是 100000 个值）。但下一个值为 10 000 000，您需要制作 100 个桶。下一个是 1 000 000 000，现在你需要 10000 个桶（其中大部分是空的！）...

了解值的范围和分布有助于组织正确的桶结构以提供最佳排序时间。

Answer 2

如果对整数类型进行排序，最大范围由整数类型中的位数隐含，对于 32 位整数，最大范围为 2^32。