计数排序概念

计数排序（Counting Sort）是一个非基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。

 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

基本思想

对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。

具体步骤

1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中每个值为  的元素出现的次数，存入数组  的第  项；
3. 对所有的计数累加（从  中的第一个元素开始，每一项和前一项相加）；
4. 反向填充目标数组：将每个元素i放在新数组的第  项，每放一个元素就将  减去

动态过程展示

（引用一个别人做的GIF，非常清晰明了）

优势

在对一定范围内的整数排序时，它的复杂度为（其中k是整数的范围），快于任何比较排序算法。

劣势

这是一种牺牲空间换取时间的做法，而且当的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是, 如归并排序，堆排序）

代码实现

一维数组

假设现在有一个一维数组 arr = [1, 62, 81, 0, 23, 55, 76, 87, 20, 54, 65, 76, 1]

常规版

import java.util.Arrays;

// 计数排序（Counting Sort）
public class CountingSort {
    public static void main(String[] args) {
        // 给定的数组
        int[] arr = {1, 62, 81, 0, 23, 55, 76, 87, 20, 54, 65, 76, 1};
        // 调用CountingSort方法，将数组arr作为参数传递给它
        arr = CountingSort(arr);
        // 打印排序后结果
        System.out.println(Arrays.toString(arr));
    }
    // CountingSort方法
    public static int[] CountingSort(int[] a) {
        // 找出数组中最大的数，将其赋值给max
        int max = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        // 找出数组中最小的数，将其赋值给min
        int min = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] < min) {
                min = a[i];
            }
        }
        // 有了最大值和最小值能够确定计数数组的长度（计数数组是用来记录原始数据中每个值出现的频率）
        // 创建计数数组，长度为max-min+1,
        int[] count = new int[max - min + 1];
        // 循环遍历旧数组计数排序: 就是统计原始数组值出现的频率到计数数组count中
        // 遍历数组a,将每个元素在计数数组count中对应的位置进行累加
        for (int i = 0; i < a.length; i++) {
            count[a[i] - min]++;
        }
        // 遍历输出计数数组
        int index = 0;
        // 先循环每一个元素,在计数排序器的下标中
        // 外层for循环,变量i表示计数数组count的索引
        for (int i = 0; i < count.length; i++) {
            // 内层while循环
            while (count[i] > 0) {
                // 将i赋值给输入数组a的索引位置index,即对应元素的排列位置
                // 我们向数组中计数时，下标要减去一个偏移量min，输出数组的时候，要加上这个偏移量
                a[index++] = i + min;
                // 将count[i]的值减1，用于记录已经将该元素放入输入数组a的次数
                count[i]--;
                // 将index加1，以便将下一个相同元素放入输入数组a的正确位置
            }
        }
        // 排序完成后，输入数组a中的元素将按照升序排列
        return a;
    }
}

复杂度

• 最优时间复杂度：
• 最坏时间复杂度：
• 平均时间复杂度：
• 空间复杂度：
• 稳定性：稳定