Java实现桶排序经典代码和算法思路

文
章
目
录

• 桶排序算法原理
• 桶排序算法描述
• 桶排序算法步骤
• 桶排序流程解析图解
• 1、桶编号计算
• 2、桶元素排序
• Java代码实现
•  总结

本文主要讲解Java实现桶排序经典代码和算法思路。

桶排序算法原理

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）

桶排序算法描述

人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3）；

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

对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；

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

注意，如果递归使用桶排序为各个桶排序，则当桶数量为1时要手动减小 BucketSize 增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。

桶排序算法步骤

• 找出待排序的数组中的最大元素max和最小元素min
• 根据指定的桶数创建桶，本文使用的桶是List结构，桶里面的数据也采用List结构存储
• 根据公式遍历数组元素：桶编号 = (数组元素 – 最小值) * (桶个数 – 1) / (最大值 – 最小值)，把数据放到相应的桶中
• 从小到大遍历每一个桶，同时对桶里的元素进行排序
• 把排好序的元素从索引为0开始放入（因为前一个桶的数据一定小于后一个桶的数据，然后每个桶里的数据又是有序的），完成排序

桶排序流程解析图解

假设我们要排序的数据是：15, 8, 23, 38, 28, 19, 32, 21, 9

1、桶编号计算

通过我们的整体流程图，来看看数据是怎么分，又是怎么合成的。

桶编号 = (数组元素 – 最小值) * (桶个数 – 1) / (最大值 – 最小值)根据计算把数据放到相应的桶中，如下图所示：

2、桶元素排序

接下里我们对桶里的元素进行排序，我这里为了省事就采用自带的排序了，排序结果如下：

Java代码实现

/**
 * 桶排序
 *
 * @param arr
 * @param bucketSize
 */
public static void bucketsort(int[] arr, int bucketSize) {
    // 初始化最大最小值
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    // 找出最小值和最大值
    for (int num : arr) {
        max = Math.max(max, num);
        min = Math.min(min, num);
    }

    // 创建bucketSize个桶
    List<List<Integer>> bucketList = new ArrayList<>();// 声明五个桶
    for (int i = 0; i < bucketSize; i++) {
        bucketList.add(new ArrayList<>());// 确定桶的格式为ArrayList
    }

    // 将数据放入桶中
    for (int num : arr) {
        // 确定元素存放的桶号
        int bucketIndex = (num - min) * (bucketSize - 1) / (max - min);//重点
        log.info(\"({} - {}) * ({} - 1) / ({} - {})={}\", num, min, bucketSize, max, min, bucketIndex);
        log.info(\"【{}】放入到第【】号桶中：{}\", num, bucketIndex + 1);
        List<Integer> list = bucketList.get(bucketIndex);
        list.add(num);// 将元素存入对应的桶中

    }
    // 遍历每一个桶
    for (int i = 0, arrIndex = 0; i < bucketList.size(); i++) {
        List<Integer> list = bucketList.get(i);
        log.info(\"第【{}】桶的数据为：{}\", i + 1, list);
        list.sort(null);// 对每一个桶排序
        for (int value : list) {
            arr[arrIndex++] = value;
        }
    }
}

public static void main(String[] args) {
    int[] arr = {15, 8, 23, 38, 28, 19, 32, 21, 9};
    log.info(\"要排序的初始化数据：{}\", arr);
    //从小到大排序
    bucketsort(arr, 4);
    log.info(\"结果为：{}\", arr);
}

 总结

以上就是Java实现桶排序经典代码和算法思路的全部内容，希望对你与帮助！