理解桶排序算法原理

我是攻城师

发布于 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）。

下面看下示例代码：

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

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