算法渣-排序-计数排序

没有一身好内功，招式再多都是空;算法绝对是防身必备，面试时更是不可或缺；跟着算法渣一起从零学算法

线性排序

常见的三种以线性时间运行的算法：计数排序、基数排序和桶排序

需要注意的是线性排序算法是非基于比较的排序算法，都有使用限制才能达到线性排序的效果

线性排序是个神奇的算法，比基数排序及桶排序神奇得多

定义

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法

算法

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

首先需要三个数组，第一个数组记录A要排序的数列大小为n，第二个数组B要记录比某个数小的其他数字的个数所以第二个数组的大小应当为K（数列中最大数的大小），第三个数组C为记录排序好了的数列的数组，大小应当为n。

接着需要确定数组最大值并确定B数组的大小。并对每个数由小到大的记录数列中每个数的出现次数。因为是有小到大通过出现次数可以通过前面的所有数的出现次数来确定比这个数小的数的个数，从而确定其位置

假定20个随机整数的值，也就是第一个数组A：

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

数组A中最大数为10，数组B需要0~10索引

比如第一个整数是9，那么数组下标为9的元素加1：

第二个整数是3，那么数组下标为3的元素加1：

最终，数列遍历完毕时，数组的状态如下：

数组每一个下标位置的值，代表了数列中对应整数出现的次数。

有了这个“统计结果”，排序就很简单了。直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次：

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

实现

/**
 * 计数排序
 * @param array
 */
public static void countSort(int []array){
    //最大最小数
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for ( int a:array) {
        if(min > a) {
            min = a;
        }
        if(max < a) {
            max = a;
        }
    }

    //数组索引数量,统计数组计数
    // max-min 主要是考虑到像[90,99,93,95]不是从很小数开始的数组排序，减小空间消耗
    int indexCount = max - min + 1;
    System.err.println("统计数组长度"+indexCount);
    int []countArray = new int[indexCount];

    for (int i=0;i<array.length;i++){
        System.err.println(array[i]-min);
        countArray[array[i]-min]++;
    }
    System.err.println("countArray:"+Arrays.toString(countArray));

    //排好序的数组
    int [] sortArray = new int[array.length];
    int index = 0;
    for (int i=0;i<indexCount;i++) {
        for (int j=0;j<countArray[i];j++){
            sortArray[index++] = min + i;
        }
    }
    //输出就是有序
    System.err.println(Arrays.toString(sortArray));
}

改进

上面的实现为什么要改进，主要是当两个元素相同时，算法的稳定性问题

改进之前，数组B存放的是元素出现的次数

改进之后，会引入一个新数组(也可以共用数组B)，存放的是元素的位置号(这个纯粹是个人理解，之前数组B是存放元素出现的次数，新数组存放每一个元素都加上前面所有元素出现次数之和，当找到对应排序数组元素时，新数组元素就是位置号)

语言比较空洞，直接来个示例(转自小灰程序员)

将数组arr中的数据当作是学生的成绩，要求不但要按照顺序从低到高排序，成绩相同时，按原有顺序显示：

统计数组从第二个元素开始，每一个元素都加上前面所有元素之和

第一步，我们遍历成绩表最后一行的小绿：

小绿是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分的小红和小绿就能够清楚地排出顺序了，也正因此，优化版本的计数排序属于稳定排序。

/**
 * 稳定计数排序
 * @param array
 */
public static void countSort1(int []array) {
    //最大最小数
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for ( int a:array) {
        if(min > a) {
            min = a;
        }
        if(max < a) {
            max = a;
        }
    }

    //数组索引数量,统计数组计数
    // max-min 主要是考虑到像[90,99,93,95]不是从很小数开始的数组排序，减小空间消耗
    int indexCount = max - min + 1;
    System.err.println("统计数组长度"+indexCount);
    int []countArray = new int[indexCount];

    for (int i=0;i<array.length;i++){
        System.err.println(array[i]-min);
        countArray[array[i]-min]++;
    }
    System.err.println("countArray:"+Arrays.toString(countArray));
    //位置数组
    int []pointArray = new int[indexCount];

    int sum =0;
    for (int i = 0;i<indexCount;i++){
        sum += countArray[i];
        pointArray[i] = sum;
    }
    System.err.println("pointArray:"+Arrays.toString(pointArray));
    System.err.println("aaaaaArray:"+Arrays.toString(array));
    //排好序的数组
    int [] sortArray = new int[array.length];
    for (int i=array.length-1;i>=0;i--) {
            sortArray[pointArray[array[i]-min] -1 ] = array[i];
            pointArray[array[i]-min]--;
    }
    //输出就是有序
    System.err.println(Arrays.toString(sortArray));
}

总结

复杂度

假设array元素有N个，取值范围是M。

时间复杂度：3N(计算最大最小数、计数、排好序的数组) + M(位置数组)，去掉系数，时间复杂度是O(N+M)

空间复杂度：只考虑统计数组，那就是M

局限性

1.当数列最大最小值差距过大时，并不适用计数排序。

比如给定20个随机整数，范围在0到1亿之间，这时候如果使用计数排序，需要创建长度1亿的数组。不但严重浪费空间，而且时间复杂度也随之升高。

2.当数列元素不是整数，并不适用计数排序。

如果数列中的元素都是小数，比如25.213，或是0.00000001这样子，则无法创建对应的统计数组。这样显然无法进行计数排序。

引申阅读

算法渣-排序-基数排序

算法渣-排序-桶排序

参考资料

漫画：什么是计数排序