个人中心
gpt4 book ai didi

java 实现计数排序和桶排序实例代码

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 25 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章java 实现计数排序和桶排序实例代码由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

java 实现计数排序和桶排序实例代码 。

目录 。

比较和非比较的区别 。

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置.

在 冒泡排序 之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在 归并排序、快速排序 之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均 O(nlogn) .

比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况.

计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置.

非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度 O(n) .

非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求.

计数排序 。

计数排序适用数据范围 。

计数排序需要占用大量空间，它仅适用于数据比较集中的情况。比如 [0~100]，[10000~19999] 这样的数据.

过程分析 。

计数排序的基本思想是： 对每一个输入的元素arr[i]，确定小于 arr[i] 的元素个数.

所以可以直接把 arr[i] 放到它输出数组中的位置上。假设有5个数小于 arr[i]，所以 arr[i] 应该放在数组的第6个位置上.

下面给出两种实现:

算法流程（1） 。

需要三个数组

待排序数组 int[] arr = new int[]{4,3,6,3,5,1},

辅助计数数组 int[] help = new int[max - min + 1]; //该数组大小为待排序数组中的最大值减最小值+1 。

输出数组 int[] res = new int[arr.length],

1.求出待排序数组的最大值max=6， 最小值min=1 。

2.实例化辅助计数数组help，help数组中每个下标对应arr中的一个元素， help用来记录每个元素出现的次数 。

3.计算 arr 中每个元素在help中的位置 position = arr[i] - min，此时 help = [1,0,2,1,1,1]; （3出现了两次，2未出现） 。

4.根据 help 数组求得排序后的数组，此时 res = [1,3,3,4,5,6] 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static int [] countSort1( int [] arr){
   if (arr == null || arr.length == 0 ) {
     return null ;
   }
  
   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 help[] = new int [max];
  
   //找出每个数字出现的次数
   for ( int i = 0 ; i < arr.length; i++){
     int mapPos = arr[i] - min;
     help[mapPos]++;
   }
  
   int index = 0 ;
   for ( int i = 0 ; i < help.length; i++){
     while (help[i]-- > 0 ){
       arr[index++] = i+min;
     }
   }
  
   return arr;
}

算法流程（2） 。

需要三个数组

待排序数组 int[] arr = new int[]{4,3,6,3,5,1},

辅助计数数组 int[] help = new int[max - min + 1]; //该数组大小为待排序数组中的最大值减最小值+1 。

输出数组 int[] res = new int[arr.length],

1.求出待排序数组的最大值max=6， 最小值min=1 。

2.实例化辅助计数数组help， help用来记录每个元素之前出现的元素个数 。

3.计算 arr 每个数字应该在排序后数组中应该处于的位置，此时 help = [1,1,4,5,6,7],

4.根据 help 数组求得排序后的数组，此时 res = [1,3,3,4,5,6] 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static int [] countSort2( 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 [] help = new int [max - min + 1 ];
  
   //找出每个数字出现的次数
   for ( int i = 0 ; i < arr.length; i++){
     int mapPos = arr[i] - min;
     help[mapPos]++;
   }
  
   //计算每个数字应该在排序后数组中应该处于的位置
   for ( int i = 1 ; i < help.length; i++){
     help[i] = help[i- 1 ] + help[i];
   }
  
   //根据help数组进行排序
   int res[] = new int [arr.length];
   for ( int i = 0 ; i < arr.length; i++){
     int post = --help[arr[i] - min];
     res[post] = arr[i];
   }
  
   return res;
}

桶排序 。

网络流传桶排序算法勘误 。

网络各博文中流程的桶排序算法实际上都是计数排序，并非标准的桶排序。有问题的文章:

经典排序算法 - 桶排序Bucket sort 。

桶排序算法 。

排序算法 之 桶排序 。

最快最简单的排序算法：桶排序 桶排序适用数据范围 。

桶排序可用于最大最小值相差较大的数据情况，比如[9012,19702,39867,68957,83556,102456].

但桶排序要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000], 这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效.

过程分析 。

桶排序的基本思想是： 把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并 .

计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况.

1.找出待排序数组中的最大值max、最小值min 。

2.我们使用 动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1 。

3.遍历数组 arr，计算每个元素 arr[i] 放的桶 。

4.每个桶各自排序 。

5.遍历桶数组，把排序好的元素放进输出数组 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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 ;
   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);
     bucketArr.get(num).add(arr[i]);
   }
  
   //对每个桶进行排序
   for ( int i = 0 ; i < bucketArr.size(); i++){
     Collections.sort(bucketArr.get(i));
   }
  
   System.out.println(bucketArr.toString());
  
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！ 。

最后此篇关于java 实现计数排序和桶排序实例代码的文章就讲到这里了,如果你想了解更多关于java 实现计数排序和桶排序实例代码的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

25 4 0
文章推荐： PHP使用strrev翻转中文乱码问题的解决方法
文章推荐： 使用php完成常见的文件上传功能(推荐)
文章推荐： Yii2实现增删改查后留在当前页的方法详解
文章推荐： PHP文件上传、客户端和服务器端加限制、抓取错误信息、完整步骤解析
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com