Java 十大排序算法之计数排序刨析
作者:龍弟-idea 发布时间:2023-11-28 19:21:26
标签:Java,计数排序,排序算法
计数排序是非比较的排序算法,用辅助数组对数组中出现的数字计数,元素转下标,下标转元素
计数排序优缺点
优点:快
缺点:数据范围很大,比较稀疏,会导致辅助空间很大,造成空间的浪费
使用范围:数据较为密集或范围较小时适用。
思路
1.找出最大元素max
2.初始化一个max+1的数组
3.将每个元素的计数存储在数组中各自的索引处
4.存储计数数组元素的累积和
5.数组中找到原始数组的每个元素的索引
计数排序代码实现
public class CountingSort {
private static int[] countingSort(int[] arr) {
//1、求取最大值和最小值,计算中间数组的长度:中间数组是用来记录原始数据中每个值出现的频率
int min = arr[0], max = arr[0];
for (int i : arr) {
if (i > max) {
max = i;
}
if (i < min) {
min = i;
}
}
//2、有了最大值和最小值能够确定中间数组的长度
//例如存储 5-0+1=6
int[] countArray = new int[max - min + 1];
//3、循环遍历旧数组计数排序: 就是统计原始数组值出现的频率到中间数组B中
for (int i : arr) {
countArray[i - min] += 1; //数的位置上+1
}
//4、统计数组做变形,后边的元素等于前面的元素之和
for (int i = 1; i < countArray.length; i++) {
countArray[i] += countArray[i - 1];
}
//5、倒序遍历原始数组,从统计数组中找到正确的位置,输出到结果数组
int[] resultArray = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
//给resultArray的当前位置赋值
resultArray[countArray[arr[i] - min] - 1] = arr[i];
//给countArray的位置的值--
countArray[arr[i] - min]--;
}
return resultArray;
}
public static void main(String[] args) {
int[] arr = {1,28,3,21,11,7,6,18};
int[] sortedArr = countingSort(arr);
System.out.println(Arrays.toString(sortedArr));
}
}
时间复杂度:O(n+k)
来源:https://blog.csdn.net/weixin_48838340/article/details/121451443
0
投稿
猜你喜欢
- 杨辉三角的规律:1.每行的数据个数和在第几行一样。2.每行第一个数和最后一个数都是1.3.每行除了第一个数据和最后一个数据 其他数据的值等于
- 在C#的List集合操作中,有时候需要查找到List集合中的最大值,此时可以使用List集合的扩展方法Max方法,Max方法有2种形式,一种
- 抽象方法与虚方法的区别先说两者最大的区别:抽象方法是需要子类去实现的。虚方法是已经实现了的,可以被子类覆盖,也可以不覆盖,取决于需求。因为抽
- 前言这篇博客学习下Mybatis操作中使用Redis做缓存。这里其实主要学习几个注解:@CachePut、@Cacheable、@Cache
- 一、前言:垃圾回收:在未来的JDK中可能G1会为ZGC所取代先问自己几个问题:什么是垃圾?垃圾就是堆内存中(范指)没有任何指针指向的对象实体
- 合并有序数组的实现java版本:实例代码public class Merge {//合并有序数组 public static v
- 概念Java中的集合就是一种容器,可以容纳不同种类的数据,这些容纳是建立在未知的基础上。优点1.可以动态保存任意多个对象,使用比较方便。2.
- 在上篇文章给大家介绍了Spring boot + mybatis + Vue.js + ElementUI 实现数据的增删改查实例代码(一)
- 今天记录一下验证码的实现,希望能够帮助到大家!首先我们看一下实现的效果:此验证码的实现没有用到太多的插件,话不多说直接上代码,大家拿过去就可
- 一般而言,Android 应用在请求数据时都是以 Get 或 Post 等方式向远程服务器发起请求,那你有没有想过其实我们也可以在 Andr
- 1.鼠标右击我的电脑–》属性–》高级系统设置2.把下面的变量名称和电脑文件的本地路径填进去即可(注意:变量值后面后面不要带分号)jdk环境变
- 0-1背包的问题背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重
- 1.组件添加1.1@Configuration@Configuration:告诉SpringBoot这是一个配置类配置类里面使用@Bean标
- 本文实例讲述了Java获得当前时间前指定几个小时具体时间的方法。分享给大家供大家参考,具体如下:package getBeforeHourD
- 限流器算法目前常用限流器算法为两种:令牌桶算法和漏桶算法,主要区别在于:漏桶算法能够强行限制请求速率,平滑突发请求,而令牌桶算法在限定平均速
- 说点对这几个容易混淆的词的理解:1、c++中的virtual方法的 virtual关键字主要是防止继承中重复继承父类的同一个方法而设置的标识
- 1 引入 pom 包<dependency> <groupId>io.github.res
- 1.场景线程池使用DiscardOldestPolicy拒绝策略,阻塞队列使用ArrayBlockingQueue,发现在某些情形下对于得到
- 一、Spring Bean 集合注入在【Spring学习笔记(三)】已经讲了怎么注入基本数据类型和引用数据类型,接下来介绍如何注入比较特殊的
- 为什么要自定义缓存注解?Spring Cache本身提供@Cacheable、@CacheEvict、@CachePut等缓存注解,为什么还