桶排序
# LeetCode-桶排序
桶排序算法回顾
示例1
输入: nums = [4,0,1,2,0,5]
输出: [0,0,1,2,4,5]
# 解题思路
桶排序(Bucket Sort)的原理很简单，它是将数组分到有限数量的桶子里。是一种非比较的排序方法
在了解桶排序之前，先了解计数排序
其中计数排序思想如下：
假设待排序的数组a中共有N个整数，并且已知数组a中数据的范围[0, MAX)。在桶排序时，创建容量为MAX的桶数组r，并将桶数组元素都初始化为0；将容量为MAX的桶数组中的每一个单元都看作一个"桶"。 在排序时，逐个遍历数组a，将数组a的值，作为"桶数组r"的下标。当a中数据被读取时，就将桶的值加1。例如，读取到数组a[3]=5，则将r[5]的值+1。
# Java代码1
public class BucketSort2 {
public static void main(String[] args) {
int[] arr = {4, 0, 1, 2, 0, 10};
bucketSort2(arr);
for (Integer i : arr) {
System.out.print(i);
}
}
public static void bucketSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int[] bucket = new int[max + 1];
for (int i = 0; i < arr.length; i++) {
bucket[arr[i]]++;
}
int index = 0;
for (int j = 0; j < bucket.length; j++) {
while (bucket[j]-- > 0) {
arr[index++] = j;
}
}
}
}
桶排序可以看做是计数排序的扩展，在计数排序中，每个桶只存储相同的元素
而桶排序中每个桶存储一定范围的元素，通过映射函数，将待排序数组中的元素存储到各个对应的桶中
之后对每个桶中的元素进行排序
最后将非空桶中的元素逐个放入原序列中
桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序就会失效
桶排序的稳定性取决于桶内部使用的排序算法
# Java代码2
import java.util.ArrayList;
import java.util.Collections;
public class BucketSort {
public static void main(String[] args) {
int[] arr = {4, 0, 1, 2, 0, 5};
bucketSort(arr);
for (Integer i : arr) {
System.out.print(i);
}
}
public static void bucketSort(int[] arr) {
// 计算最大值与最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
// 计算桶的数量
int bucketNum = (max - min) / arr.length + 1; //保证每个桶存的区间范围平均，+1代表余数补1个桶
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketArr.add(new ArrayList<Integer>());
}
// 将每个元素放入桶
for (int i = 0; i < arr.length; i++) {
int num = (arr[i] - min) / (arr.length); //确定arr[i]存储在哪个桶
bucketArr.get(num).add(arr[i]);
}
// 对每个桶进行排序
for (int i = 0; i < bucketArr.size(); i++) {
Collections.sort(bucketArr.get(i)); // 内层排序算法可选择
}
// 将桶中的元素赋值到原序列
int index = 0;
for (int i = 0; i < bucketArr.size(); i++) {
for (int j = 0; j < bucketArr.get(i).size(); j++) {
arr[index++] = bucketArr.get(i).get(j);
}
}
}
}
# 时间复杂度
对于待排序序列大小为N，共分为M个桶，主要步骤有：
- N次循环，将每个元素装入对应的桶中
- M次循环，对每个桶中的数据进行排序(平均每个桶有N/M个元素)
一般使用较为快速的排序算法，时间复杂度为O(nlogn)，实际的桶排序过程是以链表形式插入的
整个桶排序的时间复杂度为：
O(N)+O(M*(N/M*log(N/M)))=O(N*(log(N/M)+1))
当N=M时，复杂度为O(N)
# 空间复杂度
O(N+M)
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-07-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。