好程序员Java学习路线分享5分钟了解计数排序
文章目录
好程序员Java学习路线分享5分钟了解计数排序,前言:计数排序是一种非比较性质的排序算法,计数排序借助辅助空间记录每个元素出现的次数,根据次数确定每一个元素最终的位置。
计数排序思想介绍
1根据待排序数组,获取最大值和最小值,得到所有元素的范围 [m,n]
2新建一个长度为n-m+1的临时数组
3遍历待排序数组,元素的值-m作为临时数组下标,该下标位置记录元素出现次数
4遍历结束,临时数组就存储了每个元素出现的次数
5根据该临时数组,最终得到排序后元素
算法说明:
待排序数据:12,4,6,7,4,6
数据范围为[4,12],临时数组长度为12-4+1=9
最终得到排序后序列:4,4,6,6,7,12
计数排序的代码实现
- public static void sortCount(int[] arr) {
- int max = 0;
- int min = 0;
- // 获取数组的最大值和最小值
- for(int i = 0; i < arr.length; i++){
- max = Math.max(max, arr[i]);
- min = Math.min(min, arr[i]);
- }
- int len = arr.length;
- // 创建临时数组
- int[] temp = new int[max - min + 1];
- // 计数
- for(int i = 0; i < len; i++) {
- temp[arr[i] - min] += 1;
- }
- // 将临时数组中数据依次放回原数组
- for(int i = 0, index = 0; i < temp.length; i++) {
- int item = temp[i];
- while(item-- != 0) {
- arr[index++] = i + min;
- }
- }
- }
总结
计数排序需要占用额外的存储空间,它比较适用于数据比较集中的情况。

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论