桶排序算法（基于Java实现）

2020-12-19

字数统计: 968字 | 阅读时长≈ 4分

桶排序算法（基于Java实现）

桶排序算法的原理和代码实现

一、桶排序算法的原理

桶排序，顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

整个桶排序算法过程：

①设置一个定量的数组当作空桶；

②遍历输入数据，并且把数据一个一个放到对应的桶里去；

③对每个不是空的桶进行排序；

④从不是空的桶里把排好序的数据拼接起来。

二、桶排序算法的代码实现

package Sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

//桶排序
public class BucketSort2 {
    public static void bucketSort(int[] a) {

        int min = a[0];
        int max = a[0];

        for (int i = 0; i < a.length; i++) {
            max = Math.max(max, a[i]);

            min = Math.min(min, a[i]);

        }
        System.out.println("最大值为："+max);
        System.out.println("最大值为："+min);

        //桶数
        int bucketNum = a.length;
        //这里的处理很巧妙
        //声明并初始化一个ArrayList，用来存放桶的个数，以及桶中的数据。
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketArr.add(new ArrayList<Integer>());
        }

        //将每个元素放入桶中
        for (int i = 0; i < a.length; i++) {
            //加1是为了保证index < a.length，防止程序抛出IndexOutofBoundsEX
            //这里就是一个比例问题，就是看一下a[i]是属于哪一个桶的，因为这里的桶数是数组a的长度。
            int num = (int)((a[i] - min) / (max - min + 1) * a.length);
            bucketArr.get(num).add(a[i]);
        }

        //对每个桶进行排序
        for (int j = 0; j < bucketArr.size(); j++) {
            Collections.sort(bucketArr.get(j));
        }

        //合并数据
        int k = 0;
        for(ArrayList<Integer> arr : bucketArr){
            for(int i : arr){
                a[k++] = i;
            }
        }
    }

    public static void main (String[] args){
        int[] a = {9012, 19702, 398867, 68957, 83556, 102456, 56789, 324567, 556666, 899932, 12345, 432567};

        //int[] a = {6, 11, 3, 9, 8};
        System.out.println("之前的排序：");
        System.out.println(Arrays.toString(a));

        bucketSort(a);
        System.out.println("之后的排序：");
        System.out.println(Arrays.toString(a));
    }
}

输出的结果为：

之前的排序：
[9012, 19702, 398867, 68957, 83556, 102456, 56789, 324567, 556666, 899932, 12345, 432567]
最大值为：899932
最大值为：9012
之后的排序：
[9012, 12345, 19702, 56789, 68957, 83556, 102456, 324567, 398867, 432567, 556666, 899932]

三、桶排序算法的性能分析

如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序，时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候**桶排序的时间复杂度接近 O(n)**。

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

本文作者： feng之锋
本文链接： http://example.com/2020/12/19/桶排序/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！