前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >理解桶排序算法原理

理解桶排序算法原理

作者头像
我是攻城师
发布2018-10-19 16:43:21
1.8K0
发布2018-10-19 16:43:21
举报
文章被收录于专栏:我是攻城师

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

桶排序的步骤是:

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

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

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

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

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

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

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

下面看下示例代码:

代码语言:javascript
复制
private static void bucketSort(){

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

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

        for(int i:arr){
            max=Math.max(max,i);
            min=Math.min(min,i);
        }

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

        int bucketSize=5;

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

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

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

        for (int i = 0; i <arr.length ; i++) {
              int findIndex=(int)Math.floor(arr[i]/divider);
              if(storeResults[findIndex]==null){
                  storeResults[findIndex]=new ArrayList<Integer>();
              }
              storeResults[findIndex].add(arr[i]);
        }

        int ndx=0;
        for(List bucket:storeResults){
            if(bucket==null) continue;
            //每个桶的数据,可以采用不同的排序方式,这里用Java内置的集合排序
            Collections.sort(bucket);
            //排序完的数据,即可归并
            for (Object i:bucket){
                 arr[ndx]=(int)i;
                 ndx++;
            }
        }

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

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

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

总结:

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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-10-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 我是攻城师 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档