计数排序算法

 

 作者：敲代码の流川枫

博客主页：流川枫的博客

专栏：和我一起学java

语录：Stay hungry stay foolish

工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网

点击免费注册和我一起刷题吧    

文章目录

1. 算法思想

2. 算法图解

3. 代码实现

4. 算法特点

---

1. 算法思想

一提到排序，大多的思路都离不开数据之间的比较，今天分享一种不需要比较的排序思路

计数排序就是一个排序时不比较元素大小的排序算法

对一定范围内的整数排序的时候速度非常快，优于其他算法。同时局限性也比较大，只能对于整数进行排序，并且待排序元素分布较连续，跨度小的情况

如果一个数组里所有元素都是整数，且在0—k以内，那对于这个数组的每个元素来说，如果能知道数组里有多少项小于或等于该元素，就能准确地给出该元素在排序后的数组的位置

具体操作步骤

我们来看这个数组

 对于这个数组，元素5之前有8个元素小于或等于5，包含5，因此排序后5所在的位置肯定是7

因此我们构造一个（5+1）大小的数组，里面存下所有对应A中每个元素之前的元素个数，就能在线性时间内完成排序

2. 算法图解

 升序图示：

接下来我们的操作是：初始化一个大小为（5+1）的计数数组，所有元素值为0，遍历整个数组，将原始数组中的每个元素值转化为计数数组的下标，并将计数数组下标对应的元素值大小+1

接下来我们开始遍历计数数组，然后对原数组进行操作

计数数组0位置的值是2，我们在原始数组的前两个位置放入0，放入一个值后，计数数组该位置的值就减1，原始数组索引向后移动准备存放下一个值

当计数数组的0位置元素值减为0时，计数数组索引向后移动指向下一个位置，如果下一个位置元素为0 ，即证明没有当前下标的元素，索引继续后移

每次在原始数组放进一个元素时，计数数组的某个位置的元素值都会减一，直到计数数组的值全为0时，排序已经完成

3. 代码实现

在实际应用中，我们会同时找出数组中的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));
    }
}

结果：

4. 算法特点

时间复杂度为O(n+k)，空间复杂度为O(n)，适合数据范围跨度较小的排序

“ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！