排序(8) 计数排序

无论是冒泡排序，还是快速排序等等，都是基于元素之间的比较来进行排序。有一种特殊的算法叫做 计数排序，这种排序算法不是基于元素比较，而是利用数组下标来确定元素的正确位置。

计数排序

思想

如果通过比较进行排序，那么复杂度的下界是O(nlogn)，但是如果数据本身有可以利用的特征，可以不通过比较进行排序，就能使时间复杂度降低到O(n)。

计数排序要求待排序的数组元素都是整数，有很多地方都要求是 0-K 的正整数，其实负整数也可以通过都加一个偏移量解决的。

计数排序的思想是，考虑待排序数组中的某一个元素a，如果数组中比a小的元素有s个，那么a在最终排好序的数组中的位置将会是s+1，如何知道比a小的元素有多少个，肯定不是通过比较去觉得，而是通过数字本身的属性，即累加数组中最小值到a之间的每个数字出现的次数（未出现则为0），而每个数字出现的次数可以通过扫描一遍数组获得。

计数排序的步骤：

1.找出待排序的数组中最大和最小的元素（计数数组C的长度为max-min+1，其中位置0存放min，依次填充到最后一个位置存放max）
2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4.反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1（反向填充是为了保证稳定性）

计数排序适合数据分布集中的排序，如果数据太分散，会造成空间的大量浪费，假设数据为（1,2,3,1000000），这就需要1000000的额外空间，并且有大量的空间浪费和时间浪费。

示例

数组里有20个随机数，取值范围从0到10,要求用最快的速度把这20个整数从小到大进行排序。

随机整数的取值范围从0到10，这些整数取值范围为0-10这11个数字。根据这个整数取值范围，建立一个长度为11的数组。数组下标从0到10，元素初始值全为0。

假定20个随机整数的值如下：
9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9 ，7，9

如何给这些无序的随机整数排序呢？
非常简单，让我们遍历这个无序的随机数列，每一个整数按照其值对号入座，对应数组下标的元素进行加1操作。
最终，数列遍历完毕时，数组的状态如下：

0	1	2	3	4	5	6	7	8	9	10
1	2	1	3	2	2	1	2	1	4	1

数组每一个下标位置的值，代表了数列中对应整数出现的次数。
有了这个“统计结果”，排序就很简单了。直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次：
0，1，1，2，3，3，3，4，4，5，5，6，7，7，8，9，9，9，9，10
显然，这个输出的数列已经是有序的了。

这就是计数排序的基本过程，它适用于一定范围的整数排序。在取值范围不是很大的情况下，它的性能甚至超过那些O(nlogn)的排序。

计数排序（初步实现）

下面代码在一开头补充了一个步骤，就是求得数列的最大整数值max。后面创建的统计数组countArray，长度就是max + 1，以此保证数组的最后一个下标是max。
代码如下：

计数排序初步实现

public class CountSort {
    public static int[] countSort(int[] arr) {
        // 1. 得到数列的最大值
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[0]) {
                max = arr[i];
            }
        }
        // 2.根据数列最大值确定统计数组的长度
        int[] countArray = new int[max + 1];
        // 3. 遍历数列，填充统计数组
        for (int i = 0; i < arr.length; i++) {
            countArray[arr[i]]++;
        }
        // 4. 遍历统计数组，输出结果
        int index = 0;
        int[] sortedArray = new int[arr.length];
        for (int i = 0; i < countArray.length; i++) {
            for (int j = 0; j < countArray[i]; j++) {
                sortedArray[index++] = i;
            }
        }
        return sortedArray;
    }

    public static void main(String[] args) {
        int[] array = { 4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10 };
        int[] sortedArray = countSort(array);
        System.out.println(Arrays.toString(sortedArray));
    }
}

改进点分析

初始值和偏移量

上面的初步实现，从功能角度，可以实现整数的排序，但是存在一些问题，只以数列的最大值来决定统计数组的长度，其实并不严谨。比如下面的数列：
95，94，91，98，99，90，99，93，91，92

这个数列的最大值是99，但最小值的整数是90.如果创建长度为100的数组，前面从0到89的空间位置都浪费了。

解决这个问题，很简单，不再以（输入数列的最大值 + 1）作为统计数组的长度，而是以（数列最大值和最小值的差 + 1）作为统计数组的长度。
同时，数列的最小值作为一个偏移量，用于统计数组的对号入座。

以刚才的数列为例，统计数组的长度为 99-90+1 = 10 偏移量等于数列的最小值90.
对于第一个整数95，对应的统计数组下标是 95-90=5

反向填充

另外一方面，朴素版的计数排序只是简单地按照统计数组的下标输出了元素值，并没有真正给原始数列进行排序。
如果只是单纯的给整数排序，这样没有问题，但是如果放在业务代码里，比如给学生的考试分数排序，遇到相同的分数就会分不清谁是谁。

姓名	成绩
小灰	90
大黄	99
小红	95
小白	94
小绿	95

给定一个学生的成绩表，要求按成绩从低到高排序，如果成绩相同，则 遵循原表固有顺序。
那么，当我们填充统计数组以后，我们只知道有两个成绩并列95分的小伙伴，却不知道哪一个是小红，哪一个是小绿：

0	1	2	3	4	5	6	7	8	9
1	0	0	0	1	2	0	0	0	1

变型后：

0	1	2	3	4	5	6	7	8	9
1	1	1	1	2	4	4	4	4	5

这是如何变形的呢？统计数组从第二个元素开始，每一个元素都加上前面所有元素之和。
为什么要相加呢？

这样相加的目的，是让统计数组存储的元素值，等于相应整数的最终排序位置。比如下标是9的元素值为5，代表原始数列的整数9，最终的排序是在第5位。

接下来，我们创建输出数组sortedArray，长度和输入数列一致。然后从后向前遍历输入数列：
第一步，我们遍历成绩表最后一行的小绿：
小绿是95分，我们找到countArray下标是5的元素，值是4，代表小绿的成绩排名位置在第4位。
同时，我们给countArray下标是5的元素值减1，从4变成3,，代表着下次再遇到95分的成绩时，最终排名是第3。

第二步，我们遍历成绩表倒数第二行的小白：
小白是94分，我们找到countArray下标是4的元素，值是2，代表小白的成绩排名位置在第2位。
同时，我们给countArray下标是4的元素值减1，从2变成1,，代表着下次再遇到94分的成绩时（实际上已经遇不到了），最终排名是第1。

第三步，我们遍历成绩表倒数第三行的小红：
小红是95分，我们找到countArray下标是5的元素，值是3（最初是4，减1变成了3），代表小红的成绩排名位置在第3位。
同时，我们给countArray下标是5的元素值减1，从3变成2,，代表着下次再遇到95分的成绩时（实际上已经遇不到了），最终排名是第2。

这样一来，同样是95分的小红和小绿就能够清楚地排出顺序了，也正因此，优化版本的计数排序属于稳定排序。

计数排序代码实现（优化后）

其中关键的地方有两个：
第一，在于理解计算max和min之后，需要使用原数组每一个元素减去min的转换值统计词频，特定情况下能节省存储空间，这样做的另一个好处是可以兼容负数的情况，因为每一个元素减去最小值之后，结果必定是大于等于0；

第二，在于理解为什么采用词频求和的方式 + 倒序遍历原始数组的方式，能保证排序算法的稳定性。

这里必须从后向前遍历，只有这样出现重复的元素，才会保持顺序的把最后面的重复元素，永远放在最右边。从而保证排序的稳定性，如果从前向后排序，重复元素的顺序，刚好相反，所以就不是稳定的算法。

计数排序代码实现（优化后）

public class CountSort {
    public static int[] countSort(int[] arr) {
        // 1. 得到数列的最大值和最小值，并计算出差值d
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        int d = max - min;

        // 2. 创建统计数组并统计对应元素个数
        int[] countArray = new int[d + 1];
        for (int i = 0; i < arr.length; i++) {
            countArray[arr[i] - min]++;
        }
        
        // 3. 统计数组做变型，后面的元素等于前面的元素之和
        int sum = 0;
        for (int i = 0; i < countArray.length; i++) {
            sum += countArray[i];
            countArray[i] = sum;
        }

        // 4. 倒序遍历原始数组，从统计数组找到正确位置，输出到结果数组
        int[] sortedArray = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            /*sortedArray[countArray[arr[i] - min] - 1] = arr[i];
            * countArray[arr[i] - min]--;
            */
            //  arr[i]-min找到这个数在countArray中的位置
            int sumCount = countArray[arr[i] - min];

            //得到实际排序后的位置
            int sortedPos = sumCount - 1;

            //  向最终结果里存放元素
            sortedArray[sortedPos] = arr[i];
            // 针对重复的元素，先放后面，然后减1，下次循环就会放在前面
            countArray[arr[i] - min]--;
        }
        return sortedArray;
    }

    public static void main(String[] args) {
        int[] arr = { 95, 94, 91, 98, 99, 90, 99, 93, 91, 92 };
        int[] sortedArray = countSort(arr);
        System.out.println(Arrays.toString(sortedArray));
    }
}

复杂度分析及稳定性

算法复杂度：
时间复杂度（平均）： O(n+m)
时间复杂度（最坏）： O(n+m)
时间复杂度（最好）： O(n+m)

空间复杂度： O(m)
计数排序是稳定的排序算法。

如果原始数列的规模是N，最大最小整数的差值是M，计数排序的时间复杂度和空间复杂度。
代码第1, 2, 4步都涉及到遍历原数列，运算量都是N，第3步遍历统计数列，运算量是M，所以总体运算量是3N + M，去掉系数，时间复杂度是O(n+m)。

至于空间复杂度，如果不考虑结果数组，只考虑统计数组 countArray 大小的话，空间复杂度是O(m)。

计数排序存在它的局限性：

当数列最大值最小值差距过大时，并不使用计数排序。
比如给定20个随机整数，范围在0到1亿之间，这时候如果使用计数排序，需要创建长度1亿的数组。不但严重浪费空间，而且时间复杂度也随之升高。
当数列元素不是整数，并不适用计数排序。
如果数列中的元素都是小数，比如25.213，或是0.00000001这样子，则无法创建对应的统计数组。这样显然无法进行计数排序。

基于这些局限性，另一种线性时间排序算法对此做出了弥补，这种排序算法叫做 桶排序。