文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java排序算法之计数排序如何实现

2023-06-21 20:25

关注

这篇文章主要为大家展示了“Java排序算法之计数排序如何实现”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“Java排序算法之计数排序如何实现”这篇文章吧。

计数排序是非比较的排序算法,用辅助数组对数组中出现的数字计数,元素转下标,下标转元素

计数排序优缺点

优点:快

缺点:数据范围很大,比较稀疏,会导致辅助空间很大,造成空间的浪费

使用范围:数据较为密集或范围较小时适用。

思路

找出最大元素max

Java排序算法之计数排序如何实现

初始化一个max+1的数组

Java排序算法之计数排序如何实现

将每个元素的计数存储在数组中各自的索引处

Java排序算法之计数排序如何实现

存储计数数组元素的累积和

Java排序算法之计数排序如何实现

数组中找到原始数组的每个元素的索引

Java排序算法之计数排序如何实现

计数排序代码实现

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)

以上是“Java排序算法之计数排序如何实现”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注编程网行业资讯频道!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯