理解桶排序算法原理

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

桶排序的步骤是:

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

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

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

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

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

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

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

下面看下示例代码:

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的内置集合工具类来排的顺序,这块的排序算法不限制也可以采用计数排序,插入排序等。

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

总结:

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

原文发布于微信公众号 - 我是攻城师(woshigcs)

原文发表时间:2018-10-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云霄雨霁

字符串排序----三向字符串快速排序

24000
来自专栏ACM算法日常

一次看懂进制转换(阶乘是关键) - HDU 2031

对于二进制的转换,我们通常有这样的公式,例如对于一个二进制111001,转换为十进制xx:

22130
来自专栏ACM算法日常

基础算法|7 希尔排序 HDU 1425

我们从最初的冒泡排序算法,到上篇文章的折半插入排序算法,我们一共学习了5种排序算法,相信以大家的聪明才智肯定都消化了^_^。在本篇文章中,我们又将学习第6种排序...

9520
来自专栏mathor

十大经典排序算法(动图演示)

不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面。 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。 ...

2.2K40
来自专栏python学习之旅

算法笔记(八):复杂度分析(二)

#感兴趣的可以去订阅极客时间前谷歌工程师的专栏:数据结构与算法之美,个人觉得写的很不错。这里只是我自己做的一个简单的笔记

15820
来自专栏前端儿

前缀式计算

输入有多组测试数据,每组测试数据占一行,任意两个操作符之间,任意两个操作数之间,操作数与操作符之间都有一个空格。输入的两个操作数可能是小数,数据保证输入的数都是...

17110
来自专栏数据结构与算法

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记...

34170
来自专栏机器学习和数学

[编程经验] Python 中列表list介绍

列表是Python中非常重要的一种数据结构,使用频率非常高,本文主要介绍对于学习python的新手来说,需要掌握的一些基础知识。 1. 创建列表 ? 列表用中括...

38650
来自专栏用户画像

7.6.1 内部排序算法的比较

1、简单选择排序、直接插入排序和冒泡排序的平均情况下的时间复杂度都为O(n^2),并且实现过程比较简单,但直接插入排序和冒泡排序在最好的情况下时间复杂度可以达到...

7420
来自专栏wym

字符串--Kmp详解+代码

        给定文本串text和模式串pattern,要求从文本串中找到模式串第一次出现的位置。

17210

扫码关注云+社区

领取腾讯云代金券