桶排序 | god-jiang的git个人博客

桶排序（百度百科）

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是比较排序，他不受到 O(n*log n) 下限的影响。

排序思路（图片来自小灰）

桶排序是计数排序的升级版，可以不用局限于整数。思路大致相似。首先要确定桶的区间范围。计算方式是（Max - Min）/ （length -1）。length表示桶的数量，然后最后一个桶表示最大值，其他的桶就分范围来存储数据。

然后遍历数据把数据填入桶中。

桶内进行排序。

最后遍历所有桶，把数据以此输出0.5、0.84、2.18、3.25、4.5。然后排序结束。

代码

package sort;

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

/**
 * @author god-jiang
 * @date 2020/3/7  13:38
 */
public class BucketSort {
    public static double[] bucketSort(double[] array) {
        double max = Double.MIN_VALUE;
        double min = Double.MAX_EXPONENT;
        //求出array数组的最大值和最小值
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            } else if (array[i] < min) {
                min = array[i];
            }
        }
        //计算出差值
        double d = max - min;
        //初始化桶
        int bucketNum = array.length;
        ArrayList<LinkedList<Double>> bucketList = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new LinkedList<>());
        }

        for (int i = 0; i < array.length; i++) {
            int num = (int) ((array[i] - min) * (bucketNum - 1) / d);
            bucketList.get(num).add(array[i]);
        }

        //JDK底层采用了归并排序或归并的优化版本进行排序
        for (int i = 0; i < bucketList.size(); i++) {
            Collections.sort(bucketList.get(i));
        }

        //输出结果
        double[] sortedArray = new double[array.length];
        int index = 0;
        for (LinkedList<Double> list : bucketList) {
            for (double element : list) {
                sortedArray[index++] = element;
            }
        }
        return sortedArray;
    }

    //主函数
    public static void main(String[] args) {
        double[] array = new double[]{3.14, 0.002, 6.6, 3.0, 10.01, 8.8, 4.55, 7.89};
        double[] sortedArray = bucketSort(array);
        System.out.println(Arrays.toString(sortedArray));
    }
}