作者：敲代码の流川枫
博客主页：流川枫的博客
专栏：和我一起学java
语录：Stay hungry stay foolish
工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
文章目录
算法思想
一提到排序，大多的思路都离不开数据之间的比较，今天分享一种不需要比较的排序思路
计数排序就是一个排序时不比较元素大小的排序算法
对一定范围内的整数排序的时候速度非常快，优于其他算法。同时局限性也比较大，只能对于整数进行排序，并且待排序元素分布较连续，跨度小的情况
如果一个数组里所有元素都是整数，且在0—k以内，那对于这个数组的每个元素来说，如果能知道数组里有多少项小于或等于该元素，就能准确地给出该元素在排序后的数组的位置
具体操作步骤
我们来看这个数组
对于这个数组，元素5之前有8个元素小于或等于5，包含5，因此排序后5所在的位置肯定是7
因此我们构造一个（5+1）大小的数组，里面存下所有对应A中每个元素之前的元素个数，就能在线性时间内完成排序
算法图解
升序图示：
接下来我们的操作是：初始化一个大小为（5+1）的计数数组，所有元素值为0，遍历整个数组，将原始数组中的每个元素值转化为计数数组的下标，并将计数数组下标对应的元素值大小+1
接下来我们开始遍历计数数组，然后对原数组进行操作
计数数组0位置的值是2，我们在原始数组的前两个位置放入0，放入一个值后，计数数组该位置的值就减1，原始数组索引向后移动准备存放下一个值
当计数数组的0位置元素值减为0时，计数数组索引向后移动指向下一个位置，如果下一个位置元素为0 ，即证明没有当前下标的元素，索引继续后移
每次在原始数组放进一个元素时，计数数组的某个位置的元素值都会减一，直到计数数组的值全为0时，排序已经完成
代码实现
在实际应用中，我们会同时找出数组中的max和min，主要为了节省空间。如果[1004,1020,1070]这样的数据要排序，是不需要建立1070+1这样的计数数组的，只需要长度为1070-1004+1=67的数组，就能囊括从最小到最大元素之间的所有元素了
如果待排序数组的元素值跨度太大了，就不要用计数排序了，太浪费空间了
我们看计数排序的代码:
import java.util.Arrays;
public class CountingSort {
public int[] sortArray(int[] nums){
if(nums.length==0)return nums;
//寻找最大值和最小值
//bias：偏移量，用于定位每个元素在计数数组中的下标位置
int bais,min=nums[0],max = nums[0];
for (int i = 1; i < nums.length ; i++) {
if(nums[i]>max)
max = nums[i];
if(nums[i]<min)
min = nums[i];
}
bais = 0-min;
//获得计数数组内容
int[] counterArray = new int[max-min+1];
Arrays.fill(counterArray,0);
//遍历整个数组，将原始数组每个元素转化为计数数组的下标
//并将计数数组下标对应的元素值大小进行累加
for (int i = 0; i < nums.length; i++) {
counterArray[nums[i]+bais]++;
}
System.out.println("计数数组为");
PrintArray.print(counterArray);
System.out.println("-----------");
int index = 0;//访问原始数组的下标计数器
int i = 0;//访问计数数组的下标计数器
//开始访问计数数组，将计数数组的元素转换后，重新写回原始数组
while(index<nums.length){
//只要计数数组当前下标元素的值不是0，就将计数数组的元素转换后重新写回原始数组
if(counterArray[i]!=0){
nums[index] = i-bais;
counterArray[i]--;
index++;
}
else i++;
PrintArray.print(counterArray);
PrintArray.print(nums);
System.out.println("---------");
}
return nums;
}
public static void main(String[] args) {
int[] array = {2,5,3,0,2,3,0,3};
CountingSort countingSort = new CountingSort();
countingSort.sortArray(array);
}
}
class PrintArray{
public static void print(int[] nums){
System.out.println(Arrays.toString(nums));
}
}
结果：
算法特点
时间复杂度为O(n+k)，空间复杂度为O(n)，适合数据范围跨度较小的排序
" 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！
原文链接: https://blog.csdn.net/chenchenchencl/article/details/126695716