三分钟搞懂桶排序 (2)

在这里如果到达极限情况n=m时。就能确保避免桶内排序,将数值放到桶中不需要再排序达到O(n)的排序效果,当然这种情况属于计数排序,后面再详解计数排序记得再回顾。

三分钟搞懂桶排序

桶排序适用情况

桶排序并且像常规排序那样没有限制,桶排序有相当的限制。因为桶的个数和大小都是我们人为设置的。而每个桶又要避免空桶的情况。所以我们在使用桶排序的时候即需要对待排序数列要求偏均匀,又要要求桶的设计兼顾效率和空间。

待排序序列要求均匀?我要不均匀又会怎么样呢?
会这样:

三分钟搞懂桶排序


这样其实相当于只用了有效的很少个数桶,而再看桶排序的时间复杂度:O(n+n*(log n -log m))m取向1,log m去向0.整个复杂度变成O(n+nlogn)从级别来看就是O(nlogn),你瞅瞅你瞅瞅,这种情况就跟没用桶一样,就是快排(或其他排序)的时间复杂度。

那,那不能我搞100000个桶嘛?
不可以,真的不可以,如果100000个桶,你看看会造成什么情况:

三分钟搞懂桶排序


这才短短不到100个数,你为了一一映射用100000个空间,空间内容浪费不说,你遍历虽然O(n)也是100000次也比100个的O(nlogn)大上很多啊,真是折了夫人又折兵。

所以现在明白前面说的话了吧:数要相对均匀分布,桶的个数也要合理设计。总之桶排序是一种用空间换取时间的排序。在设计桶排序,你需要知道输入数据的上界和下界,看看数据的分布情况,再考虑是否用桶排序,当然如果能用好桶排序,效率还是很高的!

实现一个桶排序

在这里用java给大家实现一个桶排序。假设序列为:1 8 7 44 42 46 38 34 33 17 15 16 27 28 24;我们选用5个桶进行桶排序。

import java.util.ArrayList; import java.util.List; //微信公众号:bigsai public class test3 { public static void main(String[] args) { int a[]= {1,8,7,44,42,46,38,34,33,17,15,16,27,28,24}; List[] buckets=new ArrayList[5]; for(int i=0;i<buckets.length;i++)//初始化 { buckets[i]=new ArrayList<Integer>(); } for(int i=0;i<a.length;i++)//将待排序序列放入对应桶中 { int index=a[i]/10;//对应的桶号 buckets[index].add(a[i]); } for(int i=0;i<buckets.length;i++)//每个桶内进行排序(使用系统自带快排) { buckets[i].sort(null); for(int j=0;j<buckets[i].size();j++)//顺便打印输出 { System.out.print(buckets[i].get(j)+" "); } } } }

打印结果为:

三分钟搞懂桶排序

结语

至此,桶排序就讲完了,当然本文可能有地方讲的不好或者拥有纰漏之处还请大佬指出,后面还会讲解计数排序、基数排序并且将三者进行归纳总结!

笔者微信公众号:bigsai 一个有趣的小伙子,时常会通过公众号和大家做一些有趣的项目和活动,欢迎关注,您的关注是我源源不断的动力。

三分钟搞懂桶排序

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpjwzy.html