什么是桶排序

什么是桶排序？针对这个问题，这篇文章详细介绍了相对应的分析和解答，希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

桶排序是一个排序算法，工作的原理是将数组分到有限数量的桶子里；桶排序也是鸽巢排序的一种归纳结果，当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间，但桶排序并不是比较排序，他不受到“ O(n log n)”下限的影响。

桶排序

如果已知 N 个关键字的取值范围是在 0 到 M-1 之间，而 M 比 N 小的多，则桶排序算法将关键字的每个取值建立一个"桶"，即建立 M 个桶，在扫描 N 个关键字时，将每个关键字放入相应的桶中，然后按桶的顺序收集一遍就自然有序了

简介：

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

定义

假定：输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…将n个输入元素分配到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组，指向桶（链表）。

关于什么是桶排序问题的解答就分享到这里了，希望以上内容可以对大家有一定的帮助，如果你还有很多疑惑没有解开，可以关注亿速云行业资讯频道了解更多相关知识。