排序算法-计数排序

计数排序（Counting Sort）是一种基于计数数组的非比较排序算法，特别适用于整数数据且范围较小，分布比较连续，跨度小的情况。它的核心思想是通过统计每个元素出现的次数，然后直接计算元素在有序序列中的位置。

计数排序的核心思想

1. 统计频率：遍历原数组，统计每个元素出现的次数，存入计数数组。

2. 累加计数：将计数数组转换为前缀和形式，表示每个元素在有序数组中的最后位置。

3. 反向填充：从原数组末尾开始，根据计数数组确定元素位置，保持排序的稳定性。

 代码实现

package Sort;

import java.util.Arrays;

public class CountingSort {
    public static void main(String[] args) {
        int[] res = getCountSort(new int[]{5,8,9,3,1,2,6,4,7});
        for (int i = 0; i < res.length; i++) {
            System.out.print(res[i]+" ");
        }
    }
    //步骤：
    //1.寻找数组中的最大和最小值，用于计算计数数组的容量
    //2.遍历原数组，将原数组中每个元素的值转化为计数数组的下标
    //并统计元素的个数
    //3.遍历访问计数数组，将计数数组中的元素转换后，重新写回到原数组
    public static int[] getCountSort(int[] nums){
        if (nums.length == 0) return nums;
        //1.寻找数组中最大，最小值，
        //bias：偏移量，用于定位原数组每个元素在计数数组中的下标位置
        int bias;
        int 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];
            }
        }
        bias = 0 - min;

        //获得计数数组的容量
        int[] counterArray = new int[max-min+1];
        Arrays.fill(counterArray,0);//将计数数组初始化为0

        //2.遍历原始数组，将原始数组的每个元素作为计数数组的下标，并统计元素的个数作为计数数组的值
        for (int i = 0; i < nums.length; i++) {
            counterArray[nums[i] + bias]++;
        }

        //3.遍历访问计数数组，将计数数组中的元素转换后，重新写回到原数组
        int index = 0;//访问原始数组时的下标计数器
        int i =0;//访问计数数组时的下标计数器
        while (index < nums.length){
            //只要计数数组中当前下标元素的值不为0，就将计数数组中的元素转换，重写到原数组中
            if (counterArray[i] != 0){
                nums[index] = i - bias;
                counterArray[i]--;
                index++;
            }else {
                i++;
            }
        }
        return nums;
    }
}

时间复杂度

• O(n + k)，其中 n 是元素个数，k 是数据范围（最大值 max）。

• 当 k = O(n) 时，效率极高（线性时间）。

空间复杂度

• O(n + k)（需要计数数组和输出数组）。

适用场景

• 数据为整数（或可映射为整数）。

• 数据范围较小（否则计数数组会过大）。