桶分类--为什么输入范围很重要？
桶分类--为什么输入范围很重要？
提问于 2014-03-24 09:18:14
我正在uni上算法课程，我读了关于算法3ED，p200的介绍的下面一句：
...bucket排序是快速的，因为它假定了输入的某些内容。计数排序假设输入由一个小范围内的整数组成，而桶排序则假设输入是由一个随机过程生成的，该随机过程在间隔[0，1]上均匀和独立地分配元素。
为什么输入必须在[0，1]中？为什么不能使用桶排序对任何均匀分布的序列进行排序？
回答 2
Stack Overflow用户
回答已采纳
发布于 2014-03-24 09:34:21
我设想用区间[0，1]来得到一个理论结果。但是，请注意，任何间隔都可以很容易地转换为给定的间隔，这样就不会失去通用性。也就是说，在实践中，任何均匀分布的序列都可以使用桶排序进行排序。
Stack Overflow用户
发布于 2014-03-24 10:07:20
在你的问题中给出的文本只指出了计数、排序和桶排序的输入条件。对于计数排序，有关输入的假设是，用于排序的列表中的整数范围非常小。其中，作为关于桶排序的语句，可以对输入值进行另一个假设。在这里，范围可以任意大，但在这个范围内的数字分布应该是一致的。关于桶排序的语句中的值[0，1]并不意味着桶排序的有效范围。它简单地告诉您输入值的性质。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22605207
复制相关文章
相似问题
腾讯云开发者
