搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 我是攻城师 > 理解桶排序算法原理

理解桶排序算法原理

我是攻城师 2018-10-29

计数排序,基数排序,桶排序是所有排序算法里面时间复杂度能达到O(N)级别的算法,这主要原因是因为他们不采用基于比较的算法,前面的文章已经介绍了计数排序的原理,本片文章我们来学习一下桶排序(Bucket sort)算法。

桶排序的步骤是:

(1)设置一个定量桶的个数,并使用这个数初始化一个数组,元素的类型可以是链表或者数组。

(2)计算出待排序数组的最大值

(3)使用最大值除以桶的个数并向上求整,得到划分区间的divider

(4)遍历待排序数组,取每个元素除以divider并向下取整,放入对应的桶里面

(5)遍历桶数组,对每个桶进行排序,这里排序算法不限,可以采用计数排序,快排,插入都可以。

(6)最终顺序合并每个桶数组,便得到整体有序的数组。

桶排序的平均时间复杂度O(n+k),空间复杂度最快的情况下为O(n*k),桶排序适合数据分布比较均匀 的场景,即每个桶分到的元素个数相差不多,极端情况下,所有的待排序元素都一样,那么最终会分配到一个桶里面 ,此时如果还采用了基于比较的排序算法,那么最坏的时间复杂度会达到O(n^2)。

下面看下示例代码:

 
   
   
 
  1.    private static void bucketSort(){

  2.        int arr[]={1,28,29,29,289,89,30,100,43,-2,36,57,58};

  3.        int max=arr[0],min=arr[0];

  4.        for(int i:arr){

  5.            max=Math.max(max,i);

  6.            min=Math.min(min,i);

  7.        }

  8.        System.out.println("范围:["+min+"->"+max+"]");

  9.        int bucketSize=5;

  10.        int divider= (int)Math.ceil( (max+1)/bucketSize);

  11.        System.out.println(" 桶的个数:"+bucketSize+" 每个桶的范围:"+divider);

  12.        List<Integer>[] storeResults=new ArrayList[bucketSize];

  13.        for (int i = 0; i <arr.length ; i++) {

  14.              int findIndex=(int)Math.floor(arr[i]/divider);

  15.              if(storeResults[findIndex]==null){

  16.                  storeResults[findIndex]=new ArrayList<Integer>();

  17.              }

  18.              storeResults[findIndex].add(arr[i]);

  19.        }

  20.        int ndx=0;

  21.        for(List bucket:storeResults){

  22.            if(bucket==null) continue;

  23.            //每个桶的数据,可以采用不同的排序方式,这里用Java内置的集合排序

  24.            Collections.sort(bucket);

  25.            //排序完的数据,即可归并

  26.            for (Object i:bucket){

  27.                 arr[ndx]=(int)i;

  28.                 ndx++;

  29.            }

  30.        }

  31.        System.out.println("排序后:"+ Arrays.toString(arr));

  32.    }

上面的实现采用了List来存储每个桶的元素,这里还可以采用链表,这样插入的性能会更好一点,分桶完成之后,对每个桶进行排序,仅仅为了演示,我这里使用的Java的内置集合工具类来排的顺序,这块的排序算法不限制也可以采用计数排序,插入排序等。

最终在每一段排完顺序后依次合并即可,合并的时候不需要做任何额外的比较,这一点区别于归并排序。

总结:

总体来说,桶排序与计数排序类似,计数排序可以认为是分了最大数量的桶排序,而桶排序则是,将一堆数据分了固定数量的桶中,然后对每个桶的中的数据进行排序,最后合并,桶的数量会影响桶排序的性能,并不是越大越好,这个可以根据实际的数量来估算。


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《理解桶排序算法原理》的版权归原作者「我是攻城师」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注我是攻城师微信公众号

我是攻城师微信公众号:woshigcs

我是攻城师

手机扫描上方二维码即可关注我是攻城师微信公众号

我是攻城师最新文章

精品公众号随机推荐