本文共 1774 字，大约阅读时间需要 5 分钟。

import java.util.*;/** * 桶排序，是一种线性时间的排序算法，需要创建若干个桶来协助排序，每个桶代表一个区间范围，里面可以承载一到多个元素 * 时间复杂度：平均复杂度为O(n) * 第一步：求数列最大、最小值，运算量为n * 第二步：创建空桶，运算量为n * 第三步：把原始数据的元素分配到各个桶中，运算量为n * 第四步：在每个桶内部做排序，在元素分配相对均匀的情况下，所有桶的运算量之和为n * 第五步：输出排序数列，运算量为n * 因此，桶排序的总体时间复杂度为O(n) * 桶排序的性能并非绝对稳定，如果元素极不均衡，在极端情况下，第一个桶中有n-1个元素，最后一个桶中只有一个元素，此时的时间复杂度为O(nlogn)，而且还白白创建了许多空桶 */public class BucketSort {    public static double[] bucketSort(double[] arr) {        //1、得到数组的最大值、最小值和差值d        double max = arr[0];        double min = arr[0];        for (double i : arr) {            if (i > max) {                max = i;            }            if (i < min) {                min = i;            }        }        double d = max - min;        //2、初始化桶        int bucketNum = arr.length;        List
   
    
     > bucketList = new ArrayList<>();        for (int i = 0; i < bucketNum; i++) {            bucketList.add(new LinkedList<>());        }        //3、遍历原始数组，将每个元素放入桶中        for (double i : arr) {            int num = (int) ((i - min) * (bucketNum - 1) / d);            bucketList.get(num).add(i);        }        //4、对每个桶内部进行排序        for (LinkedList item : bucketList) {            Collections.sort(item);        }        //5、输出全部元素        double[] sortArray = new double[arr.length];        int index = 0;        for (LinkedList
     
       item : bucketList) {            System.out.println("----" + Arrays.toString(item.toArray()));            for (double i : item) {                sortArray[index++] = i;            }        }        return sortArray;    }    public static void main(String[] args) {        double[] array = new double[]{4.12, 6.421, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09};        double[] sortArray = bucketSort(array);        System.out.println(Arrays.toString(sortArray));    }}
     
    
   

转载地址：http://nqsvi.baihongyu.com/