（十二）Java算法：桶排序（详细图解）

2024-07-17 17:27| 来源: 网络整理| 查看: 265

目录一、前言1.1、概念1.2、算法步骤二、maven依赖三、流程解析3.1、桶编号计算3.2、桶元素排序四、编码实现

一、前言 1.1、概念

计数排序：的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

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

pom.xml

org.springframework.boot spring-boot-starter 2.6.0 org.projectlombok lombok 1.16.14 三、流程解析

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

3.1、桶编号计算

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

桶编号 = (数组元素 - 最小值) * (桶个数 - 1) / (最大值 - 最小值)

数组索引数组数据计算桶编号015 ( 15 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 0 \frac{(15 - 8) * (4 - 1)}{(38 - 8)}=0 (38−8)(15−8)∗(4−1)=018 ( 8 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 0 \frac{(8 - 8) * (4 - 1)}{(38 - 8)}=0 (38−8)(8−8)∗(4−1)=0223 ( 23 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 1 \frac{(23 - 8) * (4 - 1)}{(38 - 8)}=1 (38−8)(23−8)∗(4−1)=1338 ( 38 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 3 \frac{(38 - 8) * (4 - 1)}{(38 - 8)}=3 (38−8)(38−8)∗(4−1)=3428 ( 28 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 2 \frac{(28 - 8) * (4 - 1)}{(38 - 8)}=2 (38−8)(28−8)∗(4−1)=2519 ( 19 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 1 \frac{(19 - 8) * (4 - 1)}{(38 - 8)}=1 (38−8)(19−8)∗(4−1)=1632 ( 32 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 2 \frac{(32 - 8) * (4 - 1)}{(38 - 8)}=2 (38−8)(32−8)∗(4−1)=2721 ( 21 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 1 \frac{(21 - 8) * (4 - 1)}{(38 - 8)}=1 (38−8)(21−8)∗(4−1)=189 ( 9 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 0 \frac{(9 - 8) * (4 - 1)}{(38 - 8)}=0 (38−8)(9−8)∗(4−1)=0

根据计算把数据放到相应的桶中，如下图所示：

在这里插入图片描述

3.2、桶元素排序

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

在这里插入图片描述你可以使用其他任意排序算法进行（比如快速排序，插入排序等等），当然这里递归使用桶排序也是可以的。

四、编码实现 /** * 桶排序 * * @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 bucketList = new ArrayList();// 声明五个桶 for (int i = 0; i // 确定元素存放的桶号 int bucketIndex = (num - min) * (bucketSize - 1) / (max - min);//重点 log.info("({} - {}) * ({} - 1) / ({} - {})={}", num, min, bucketSize, max, min, bucketIndex); log.info("【{}】放入到第【】号桶中：{}", num, bucketIndex + 1); List list = bucketList.get(bucketIndex); list.add(num);// 将元素存入对应的桶中 } // 遍历每一个桶 for (int i = 0, arrIndex = 0; i 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); }

运行结果：

要排序的初始化数据：[15, 8, 23, 38, 28, 19, 32, 21, 9] (15 - 8) * (4 - 1) / (38 - 8)=0 【15】放入到第【】号桶中：1 (8 - 8) * (4 - 1) / (38 - 8)=0 【8】放入到第【】号桶中：1 (23 - 8) * (4 - 1) / (38 - 8)=1 【23】放入到第【】号桶中：2 (38 - 8) * (4 - 1) / (38 - 8)=3 【38】放入到第【】号桶中：4 (28 - 8) * (4 - 1) / (38 - 8)=2 【28】放入到第【】号桶中：3 (19 - 8) * (4 - 1) / (38 - 8)=1 【19】放入到第【】号桶中：2 (32 - 8) * (4 - 1) / (38 - 8)=2 【32】放入到第【】号桶中：3 (21 - 8) * (4 - 1) / (38 - 8)=1 【21】放入到第【】号桶中：2 (9 - 8) * (4 - 1) / (38 - 8)=0 【9】放入到第【】号桶中：1 第【1】桶的数据为：[15, 8, 9] 第【2】桶的数据为：[23, 19, 21] 第【3】桶的数据为：[28, 32] 第【4】桶的数据为：[38] 结果为：[8, 9, 15, 19, 21, 23, 28, 32, 38]

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章