专业的JAVA编程教程与资源

网站首页 > java教程 正文

Java排序算法之桶排序详解(桶排序 leetcode)

temp10 2024-10-22 16:57:25 java教程 10 ℃ 0 评论

Java排序算法之桶排序详解

概念:桶排序是将数组中的元素放到一个一个的桶中,每个桶(bucket)代表一个区间,里面可以承载一个或者多个元素。然后将桶内的元素进行排序,再按顺序遍历桶,输出桶内元素。

时间复杂度:O(n+m+n(logn-logm)) (n代表数组长度,m代表桶数,当n=m时,时间复杂度为O(n))

Java排序算法之桶排序详解(桶排序 leetcode)

空间复杂度:O(m+n)

缺点:如果数组中除了最后一个元素全部都在第一个桶中,那么查询的时间复杂度会退化为O(nlogn),而且中间白白创建了许多空桶。

代码实现(java)


public static void main(String[] args) {

double[] arr = new double[]{4.12, 6.421, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09};

bucketSort(arr);

for (double v : arr) {

System.out.println(v);

}

}

public static void bucketSort(double[] arr) {

//1.取出数组中的最大值和最小值

double max = Double.MIN_VALUE;

double min = Double.MAX_VALUE;

for (int i = 0; i < arr.length - 1; i++) {

if (arr[i] < min) {

min = arr[i];

}

if (arr[i] > max) {

max = arr[i];

}

}

//2.初始化桶

//桶的数量

int bucketNum = arr.length;

//每个桶的区间跨度

double span = (max - min + 1) / bucketNum;

ArrayList<LinkedList<Double>> bucketList = new ArrayList<LinkedList<Double>>(bucketNum);

//在桶列表中添加元素个数的空桶

for (int i = 0; i < bucketNum; i++) {

bucketList.add(new LinkedList<Double>());

}

//3.遍历原始数组,将每个元素放入桶中

for (int i = 0; i < arr.length; i++) {

//获取桶的下标

int num = (int) Math.floor((arr[i] - min) / span);//这里计算的结果是第几个桶,用Math.floor取到桶的下标,比如计算结果是2.5,说明应该放到第三个桶中,下标为2

bucketList.get(num).add(arr[i]);

}

//4.对桶内元素进行排序

for (int i = 0; i < bucketList.size(); i++) {

Collections.sort(bucketList.get(i));

}

//5.输出全部元素

double[] sortArray = new double[arr.length];

int index = 0;

for (LinkedList<Double> list : bucketList) {

for (Double aDouble : list) {

sortArray[index] = aDouble;

index++;

}

}

}



时间复杂度:假设数组长度为n,桶数为m

  • 第一步求数列最大最小值,运算量为n。
  • 第二步创建空桶,运算量为m。
  • 第三步遍历原始数列,运算量为n。
  • 第四步在每个桶内部做排序,由于使用了O(nlogn)的排序算法,所以运算量为 n/m* log(n/m ) * m。
  • 第五步输出排序数列,运算量为n。加起来,总的运算量为 3n+m+n/m* log(n/m ) * m = 3n+m+n(logn-logm) 。

去掉系数,时间复杂度为:O(n+m+n(logn-logm)) 当n=m时,时间复杂度可以达到O(N)

空间复杂度:空桶占用的空间 + 数列在桶中占用的空间 = O(m+n)

本文暂时没有评论,来添加一个吧(●'◡'●)

欢迎 发表评论:

最近发表
标签列表