计数排序是一个非基于比较的排序算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。我们估计要有疑问了，这个排序算法这么快，为什么还存在其他的排序算法呢，这就需要要我们综合时间复杂度和空间复杂度那个最优了。

 

        Java底层对不同的数据实现了各种各样的排序算法，而对于计数排序只有在比较byte类型的数字才有效，也就是说数字最大也就是256.Java底层对这个算法实现的相当精巧，基本实现过程如下：（详情可以打开jdk java.util.Arrays.sort(byte[])）。

 

1：初始化一个计数数组，大小是输入数组中的最大的数。

2：遍历输入数组，遇到一个数就在计数数组对应的位置上加一。例如：遇到7，就将计数数组第七个位置的数加一。

3：把计数数组直接覆盖到输出数组（节约空间）。

源码如下：

public static void sort(byte[] a, int left, int right) {        // Use counting sort on large arrays        if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) {     // 初始化了一个大小为256的计数数组            int[] count = new int[NUM_BYTE_VALUES];     // 按照一定的规律把数字放在计数数组相应的加加之后位置上,            //如果重复数字出现则在位置上进行加1            for (int i = left - 1; ++i <= right;                count[a[i] - Byte.MIN_VALUE]++            );     //把计数数组直接覆盖到原数组进行输出            for (int i = NUM_BYTE_VALUES, k = right + 1; k > left; ) {                while (count[--i] == 0);                byte value = (byte) (i + Byte.MIN_VALUE);                int s = count[i];                do {                    a[--k] = value;                } while (--s > 0);            }        }     }

在jdk中这段代码还是存在优化的空间，可以把初始化数组更小， 举个例子：

比如说我输入了一个数组{4, 1, 4, 2, 3}，初始化数组大小为4即可，（按照算法导论中对计数排序的理论，即：计数数组的大小为排序数组中数字最大的数）

  建立计数数组{0, 0, 0, 0}。

遍历输入数组：

{3, 4, 3, 2, 1} -> {0, 0, 1, 0}

{3, 4, 3, 2, 1} -> {0, 0, 1, 1} {3, 4, 3, 2, 1} -> {0, 0, 2, 1} {3, 4, 3, 2, 1} -> {0, 1, 2, 1} {3, 4, 3, 2, 1} -> {1, 1, 2, 1}

计数数组现在是{1, 1, 2, 1}，我们现在把它写回到输入数组里：

{0, 1, 2, 1} -> {1, 4, 3, 2, 1}

{0, 0, 2, 1} -> {1, 2, 3, 2, 1} {0, 0, 1, 1} -> {1, 2, 3, 2, 1} {0, 0, 0, 1} -> {1, 2, 3, 3, 1} {0, 0, 0, 0} -> {1, 2, 3, 3, 4}

这样就排好序了。

时间：O(n + k)，n是输入数组长度，k是最大的数的大小。 空间：O(n + k)，n是输入数组长度，k是最大的数的大小。

 

如有问题，请扫码回复