3-桶排序
算法思想:
大家第一眼看到这个算法的名字时相信大家的反应应该和我是一样的,桶排序?排序怎么还需要用到桶呢?桶排序里的桶又是主要是干什么的呢?
其实这个大家类比到我们平常生活中就能基本知道桶排序的桶是干嘛的呢?在我们的日常生活中,我们的桶一般都是用来装东西的,我们可能是用来装水,又或者是装钱的反正不管怎么样,我们的桶最后都是一个容器,是用来存储相应的物质的.
显然我们当前存在的只有我们的待排序的序列,那么我们的桶就是用来存储我们的序列中的元素的.就像下图所示:
可以看到我们把相应的元素放入相应的桶里面了.这个放入的规则是这样的:桶是从大到小排列的,并且每一个桶都会有一个数据范围,意思就是0号桶存放是1~ 2数据范围的数据,1号桶存放3~4数据范围的数据,2号桶存放吧5 ~6数据范围内的数据.详细的放入规则我会在下面的实现步骤里面说.这里大家先简单了解一下.
这里大家要注意的一点就是,我们在把元素放入各自相应的桶里面的时候,是需要对桶内的序列进行排序的,意思就是等到每个元素都放入相应的桶里面之后,桶里面相应的序列本身也已经有序了.就如下图所示:
可以看到上面,每个桶内的序列都已经排好序了,那么很显然我们最后就只需要按照桶的序号大小将桶内的元素打印出来,那么我们的序列就已经排好序了.
说完桶排序的基本思想之后,我们接下来就说一下桶排序在代码上是如何实现的,大致有下面这几步:
1.我们首先需要第一次遍历我们的序列,得到我们序列中的最大值MAX以及序列中的最小值MIN,找到我们序列中的最大值与最小值之后,那么我们就可以确定序列中的所有都是在MIN~MAX这个数据范围区间之中.
2.第二步我们就是需要根据序列的数据范围来确定我们到底需要几个桶来存放我们的元素,这一步其实是比较关键的,因为桶的数量太多或者太少都会降低桶排序的效率.
我们举两个例子:
假设我们桶的数量太少,就比如说只有一个桶:
那么很显然我们的桶排序就又重新退化成我们前两篇内容里介绍的比较算法了.
又假设我们桶的数量太多,就比如说有MAX-MIN+1个桶:
那么很显然这时候的桶排序又重新退化成了我们上面刚刚讲解过的计数排序了.
所以说我们需要确定好一个适中的桶的数量,不然回就会出现我们上面所说到的几种情况.但是有没有一个特定的公式来确定桶的数量.所以我们还是只能自己确定桶的数量.但是有一个规则我们还是可以考虑进去的,那就是最好让元素平均的分散到每一个桶里.
3.确定完桶的数量之后,我们就可以给每个桶来划分数据范围了.一般是这样划分的,(MAX-MIN+1)/桶的数量,得到的结果就是桶长.之后每个桶的数据范围就通过桶的编号以及桶长就可以确定每个桶的数据范围.就如下面的公式:
左闭右开
桶的数据范围=[MIN+(桶的编号-1)*桶长,MIN+桶的编号 *桶长)
有了每个桶的数据范围时候,我们第二次遍历序列将每个元素存到相应的桶里面了.这个过程我们要注意,在往桶里面添加元素的时候,就需要在每个桶里面将元素排好序.
4.当我们第二次遍历结束之后,我们就只需要按照桶的编号,在将该编号的桶里面的元素打印出来,桶排序就已经完成了.
接下来我们还是通过下面的图来动态演示一下桶排序的过程:
了解完桶排序的基本思想之后,按照惯例我们还是来简单分析一下他的一些特点:
桶排序是稳定的,原因和上面计数排序的理由是一样的.
桶排序也是一个通过空间换取时间的算法,但是他的空间复杂度是可以控制的.就像我们上面说的主要就是控制桶的数量.如果桶的数量设置的合理,既能降低时间复杂度,也能降低空间复杂度.
算法图解:
示例代码:
//在链表中添加元素的同时需要进行元素的排序 public static void sort(ArrayList<Integer>list,int i) { if(list==null) list.add(i); //这里采用的排序方式为插入排序 else { int flag=list.size()-1; while(flag>=0&&list.get(flag)>i) { if(flag+1>=list.size()) list.add(list.get(flag)); else list.set(flag+1, list.get(flag)); flag--; } if(flag != (list.size()-1)) //注意这里是flag+1,自己可以尝试将这里换成flag看看,会出现数组越界的情况 list.set(flag+1, i); else list.add(i); } } public static void Bucketsort(int []num,int sum) { //遍历得到数组中的最大值与最小值 int min=Integer.MAX_VALUE; int max=Integer.MIN_VALUE; for(int i=0;i<num.length;i++) { min = min <= num[i] ? min: num[i]; max = max >= num[i] ? max: num[i]; } //求出每个桶的长度,这里必须使用Double double size=(double)(max-min+1)/sum; ArrayList<Integer>list[]=new ArrayList[sum]; for(int i=0;i<sum;i++) { list[i]=new ArrayList<Integer>(); } //将每个元素放入对应的桶之中同时进行桶内元素的排序 for(int i=0;i<num.length;i++) { System.out.println("元素:"+String.format("%-2s", num[i])+", 被分配到"+(int)Math.floor((num[i]-min)/size)+"号桶"); sort(list[(int)Math.floor((num[i]-min)/size)], num[i]); } System.out.println(); for(int i=0;i<sum;i++) { System.out.println(String.format("%-1s", i)+"号桶内排序:"+list[i]); } System.out.println(); //顺序遍历各个桶,得出我们 已经排序号的序列 for(int i=0;i<list.length;i++) { if(list[i]!=null){ for(int j=0;j<list[i].size();j++) { System.out.print(list[i].get(j)+" "); } } } System.out.println(); System.out.println(); } public static void main(String[] args) { int []num ={7,4,9,3,2,1,8,6,5,10}; long startTime=System.currentTimeMillis(); //这里桶的数量可以你自己定义,这里我就定义成了3 Bucketsort(num, 3); long endTime=System.currentTimeMillis(); System.out.println("程序运行时间： "+(endTime-startTime)+"ms"); }
这里的时间是不准确的,因为我需要将每轮排序的结果打印出来给大家看,所以会多花费一些时间,如果大家想要看真实的时间的话,大家可以把我打印结果的代码注释掉再看看算法的执行时间.
复杂度分析:
理解完桶排序的基本思想之后,我们就需要来分析一下他的时间复杂度,空间复杂度.
时间复杂度
桶排序的时间复杂度和上面的计数排序是一样的,同样也是线性级别的,但是也是增加了桶的时间,所以也是O(n+k)
空间复杂度
上面我们已经说过了,桶排序本身也是一个通过空间来换取时间的算法,所以很明显他的空间复杂度就会很高.并且这个空间复杂度主要就取决于桶的数量以及桶的范围,所以假设有k个桶的话,那么空间复杂度就为O(n+k)
