十大排序算法 -- 桶排序
桶排序
桶排序是计数排序的升级,计数排序可以看成每个桶只存储相同元素,而桶排序每个桶存储一定范围的元素,通过函数的某种映射关系,将待排序数组中的元素映射到各个对应的桶中,对每个桶中的元素进行排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序),最后将非空桶中的元素逐个放入原序列中。
桶排序需要尽量保证元素分散均匀,否则当所有数据集中在同一个桶中时,桶排序失效。
代码实现
找出数组中的最大值 max 和最小值 min,可以确定出数组所在范围 min~max
根据数据范围确定桶的数量
若桶的数量太少,则桶排序失效
若桶的数量太多,则有的桶可能,没有数据造成空间浪费
所以桶的数量由我们自己来确定,但尽量让元素平均分布到每一个桶里,这里提供一个方式
(最大值 - 最小值)/每个桶所能放置多少个不同数值+1
确定桶的区间,一般是按照
(最大值 - 最小值)/桶的数量
来划分的,且左闭右开
时间复杂度
桶排序算法遍历了 2 次原始数组,运算量为 2N,最后,遍历桶输出排序结果的运算量为 N,初始化桶的运算量为 M。
对桶进行排序,不同的排序算法算法复杂度不同,冒泡排序算法复杂度为 O(N^2),堆排序、归并排序算法复杂度为 O(NlogN),我们以排序算法复杂度为 O(NlogN)进行计算,运算量为 N/M * log(N/M) * M
最终的运算量为 3N+M+N/M * log(N/M) * M,即 3N+M+N(logN-logM),去掉系数,时间复杂度为 O(N+M+N(logN-logM))
参考:桶排序算法详解
算法稳定性
桶排序算法在对每个桶进行排序时,若选择稳定的排序算法,则排序后,相同元素的位置不会发生改变,所以桶排序算法是一种稳定的排序算法。
版权声明: 本文为 InfoQ 作者【阿粤Ayue】的原创文章。
原文链接:【http://xie.infoq.cn/article/bbfcfc9725f0ee70bc7756179】。文章转载请联系作者。
评论