一、前言
1.1、概念
计数排序
：的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是
有确定范围的整数
。
1.2、算法步骤
-
找出待排序的数组中的最大元素
max
和最小元素
min
-
根据指定的桶数创建桶，本文使用的桶是
List
结构，桶里面的数据也采用
List
结构存储 -
根据公式遍历数组元素：
桶编号 = (数组元素 – 最小值) * (桶个数 – 1) / (最大值 – 最小值)
，把数据放到相应的桶中 - 从小到大遍历每一个桶，同时对桶里的元素进行排序
- 把排好序的元素从索引为0开始放入（因为前一个桶的数据一定小于后一个桶的数据，然后每个桶里的数据又是有序的），完成排序
二、maven依赖
pom.xml
<dependencies>
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter</artifactId>
<version>2.6.0</version>
</dependency>
<dependency>
<groupId>org.projectlombok</groupId>
<artifactId>lombok</artifactId>
<version>1.16.14</version>
</dependency>
</dependencies>
三、流程解析
假设我们要排序的数据是：
15, 8, 23, 38, 28, 19, 32, 21, 9
3.1、桶编号计算
通过我们的整体流程图，来看看数据是怎么分，又是怎么合成的。
桶编号 = (数组元素 – 最小值) * (桶个数 – 1) / (最大值 – 最小值)
| 数组索引 | 数组数据 | 计算桶编号 |
|---|---|---|
|
0 |
15 |
( 15 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 0 \frac{(15 – 8) * (4 – 1)}{(38 – 8)}=0 ( 3 8 − 8 ) ( 1 5 − 8 ) ∗ ( 4 − 1 ) = 0 |
|
1 |
8 |
( 8 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 0 \frac{(8 – 8) * (4 – 1)}{(38 – 8)}=0 ( 3 8 − 8 ) ( 8 − 8 ) ∗ ( 4 − 1 ) = 0 |
|
2 |
23 |
( 23 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 1 \frac{(23 – 8) * (4 – 1)}{(38 – 8)}=1 ( 3 8 − 8 ) ( 2 3 − 8 ) ∗ ( 4 − 1 ) = 1 |
|
3 |
38 |
( 38 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 3 \frac{(38 – 8) * (4 – 1)}{(38 – 8)}=3 ( 3 8 − 8 ) ( 3 8 − 8 ) ∗ ( 4 − 1 ) = 3 |
|
4 |
28 |
( 28 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 2 \frac{(28 – 8) * (4 – 1)}{(38 – 8)}=2 ( 3 8 − 8 ) ( 2 8 − 8 ) ∗ ( 4 − 1 ) = 2 |
|
5 |
19 |
( 19 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 1 \frac{(19 – 8) * (4 – 1)}{(38 – 8)}=1 ( 3 8 − 8 ) ( 1 9 − 8 ) ∗ ( 4 − 1 ) = 1 |
|
6 |
32 |
( 32 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 2 \frac{(32 – 8) * (4 – 1)}{(38 – 8)}=2 ( 3 8 − 8 ) ( 3 2 − 8 ) ∗ ( 4 − 1 ) = 2 |
|
7 |
21 |
( 21 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 1 \frac{(21 – 8) * (4 – 1)}{(38 – 8)}=1 ( 3 8 − 8 ) ( 2 1 − 8 ) ∗ ( 4 − 1 ) = 1 |
|
8 |
9 |
( 9 − 8 ) ∗ ( 4 − 1 ) ( 38 − 8 ) = 0 \frac{(9 – 8) * (4 – 1)}{(38 – 8)}=0 ( 3 8 − 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<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);
}
运行结果：
要排序的初始化数据：[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]