排序算法（八）计数排序

计数排序是一种稳定的线性时间排序算法，原理是使用一个额外的数组，其中第i个元素是待排序数组中值等于i的元素的个数。

计数排序的局限性：

• 计数排序只适用于 整数 排序；
• 计数排序只适用于一定范围，如果待排序整数最大值和最小值差较大则不适用（引发大量存储空间浪费）。

复杂度分析

代码中遍历过原始待排序数列和临时的统计数列，假设原始待排序数列规模是N，临时统计数列规模是M，则时间复杂度是O(N+M)，空间复杂度O(M)。

Java 代码实现

import java.util.Arrays;

public class CountSort {

    public static void sort(int[] data) {
        if (data == null || data.length == 0) {
            return;
        }
        // 获取数列最大值
        int max = data[0];
        for (int i = 1; i < data.length; i++) {
            if (data[i] > max) {
                max = data[i];
            }
        }
        // 创建长度为“最大值+1”的统计数组
        int[] count = new int[max + 1];
        // 遍历待排序元素，填充统计数组
        for (int i = 0; i < data.length; i++) {
            count[data[i]]++;
        }
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            if (count[i] > 0) {
                for (int j = 0; j < count[i]; j++) {
                    data[index++] = i;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int[] data = {5, 8, 2, 9, 1, 0, 3, 4, 7, 4, 6, 2, 5};
        sort(data);
        System.out.println(Arrays.toString(data));
    }
}

运行结果

[0, 1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 8, 9]

思考：以上代码存在什么问题？如果待排序整数都是大整数，如针对121, 123, 101, 119, 110, 149, 136排序，一共需要排序的整数有7个，但是按照以上代码逻辑会创建一个容纳150个整数的额外数组，大部分存储空间实际是浪费了。
优化方法：不再以最大值 + 1作为数组长度，以最大值 - 最小值 + 1作为数组长度，同时数组最小位存储偏移量。以121, 123, 101, 119, 110, 149, 136为例，数组长度为149 - 101 + 1 = 49，偏移量为最小值101。优化后代码实现如下：

import java.util.Arrays;

public class CountSort {

    public static void sort(int[] data) {
        if (data == null || data.length == 0) {
            return;
        }
        // 获取数列最大值
        int max = data[0];
        int min = data[0];
        for (int i = 1; i < data.length; i++) {
            if (data[i] > max) {
                max = data[i];
            } else if (data[i] < min) {
                min = data[i];
            }
        }
        // 创建长度为“最大值+1”的统计数组
        int[] count = new int[max - min + 1];
        // 遍历待排序元素，填充统计数组
        for (int i = 0; i < data.length; i++) {
            count[data[i] - min]++;
        }
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            if (count[i] > 0) {
                for (int j = 0; j < count[i]; j++) {
                    data[index++] = i + min;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int[] data = {121, 123, 101, 119, 110, 123, 149, 136};
        sort(data);
        System.out.println(Arrays.toString(data));
    }
}

运行结果

[101, 110, 119, 121, 123, 123, 136, 149]