python 实现·十大排序算法之桶排序 (Bucket Sort)
简介
桶排序(Bucket Sort),也叫箱排序,其主要思想是:将待排序集合中处于同一个值域的元素存入同一个桶中,也就是根据元素值特性将集合拆分为多个区域,则拆分后形成的多个桶,从值域上看是处于有序状态的。对每个桶中元素进行排序,则所有桶中元素构成的集合是已排序的。
桶排序是计数排序的扩展版本,计数排序可以看成每个桶只存储相同元素,而桶排序每个桶存储一定范围的元素。桶排序需要尽量保证元素分散均匀,否则当所有数据集中在同一个桶中时,桶排序失效。
算法实现步骤
根据待排序集合中最大元素和最小元素的差值范围和映射规则,确定申请的桶个数;
遍历排序序列,将每个元素放到对应的桶里去;
对不是空的桶进行排序;
按顺序访问桶,将桶中的元素依次放回到原序列中对应的位置,完成排序。
Python 代码实现
动画演示
算法分析
时间复杂度
最好情况:输入序列是已排好序,那么插入排序的时间复杂度在,即最好情况下时间复杂度为。
最坏情况:对于待排序序列大小为 ,共分为 个桶,需进行次循环,将每个元素装入对应的桶中;次循环,对每个桶中的数据进行排序(平均每个桶有个元素)。
若采用快速排序算法进行排序,单次排序的平均时间复杂度为,最坏时间复杂度为。而桶排序的过程是以链表形式插入的,所以整个桶排序的时间复杂度为:
当时,时间复杂度最低为 ;当时,时间复杂度最高为。所以最坏时间复杂度为:。
平均情况:平均时间复杂度为。
空间复杂度
桶排序过程中需要创建个桶的额外空间,以及个元素的额外空间,所以桶排序的空间复杂度为 。
稳定性
桶排序的稳定性取决于桶内排序使用的算法,如果是队列,可以保证相同的元素取出和放回的相对位置不变,即排序是稳定的,而如果用栈来实现,则排序一定是不稳定的。由于桶排序可以做到稳定,所以桶排序是稳定的排序算法。
综合评价
联系我们
个人博客网站:http://www.bling2.cn/
Github地址:https://github.com/lb971216008/Use-Python-to-Achieve
知乎专栏:https://zhuanlan.zhihu.com/Use-Python-to-Achieve
小专栏:https://xiaozhuanlan.com/Use-Python-to-Achieve
博客园:https://www.cnblogs.com/Use-Python-to-Achieve
版权声明: 本文为 InfoQ 作者【南风以南】的原创文章。
原文链接:【http://xie.infoq.cn/article/d9e7a82be618b034522f10760】。
本文遵守【CC BY-NC】协议,转载请保留原文出处及本版权声明。
评论