【排序】桶排序 bucket sort
2021-03-02 07:27
阅读：457
-
思想：
将待排序集合中处于同一值域的元素存入同一个桶中，
这样的话，集合中的元素就被拆分成多个桶，再对每个桶中的元素排序，再将有序的桶放回原集合中。
一句话：通过“分配”和“收集”实现排序。
Notes：
(1).桶排序是对计数排序的改进。计数排序是给每一个元素都开辟空间，记录出现次数，以达到排序。
所以，对于数值过大的元素或者浮点数，计数排序就不能很很好的解决。
所以应用桶排序，可以很好的解决，根据元素的分布利用一个hash函数将值域相同的元素放到一个桶。
(2).桶排序的时间复杂度O(N)~O(N*logN)，N为元素个数。
(3).桶排序适用于元素均匀分布的情况。 -
算法过程：
(1).搭建桶的结构，使用单链表；
(2).hash函数定义：即如何确定元素是否在同一值域中，(value * len) / (max_value + 1)；
value:当前计算的元素
len:待排序集合的长度
max_value：集合中数值最大的元素
(3).桶中元素排序：链表中元素的插入；
(4).出桶，排序输出。
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【排序】桶排序 bucket sort
文章链接：http://soscw.com/index.php/essay/58930.html
文章标题：【排序】桶排序 bucket sort
文章链接：http://soscw.com/index.php/essay/58930.html
评论
亲，登录后才可以留言！