计数排序的简单实现

计数排序是一种比较特殊的排序，适用于整数排序，同时数组中的最大值和最小值差值不能太大，否则会有空间的浪费，这些都是由它本身的特性决定的。本文作为读了一篇相关文章后的笔记，后面会给出对应的链接，讲的非常详细。
计数排序的思想是通过构建一个统计数组countArray，数组长度为array[max]-array[min]的差值，遍历数组，序号会作为以最小array[min]为基准，来统计数组值分布的情况，依次会按顺序将array[i]中的数写入到统计数组。之后有个操作比较奇特，会重新遍历统计数组，把统计数组的∑i-1赋值给i，这样做的目的是防止两个相同的数导致顺序改变，保证算法的稳定性。这个操作详细来说，在处理统计数组后，其中的值类似[1,1,1,2,2,2,3,3,4,4...],因此在最终生成排序数组的过程中，只有统计数组的值变化了才会赋值，即能保证顺序，又能得到排序结果。
如果有M个数，统计数组即最大值和最小值差值是N，则复杂度计算：遍历一遍获取最大，最小，执行M次；最后遍历获得排序数组，执行M次；中间遍历原始数组加和统计数组，执行M次；以及中间对统计数组遍历，执行N次，结果为3M+N，去掉系数为O(M+N)，空间复杂度是O(N)。

以下是可以执行的代码：

import java.util.Arrays;
 public class CountSortTest {
    public static void main(String[] args) {
        int[] originArray = new int[] { 12, 87, 43, 23, 32, 19, 23, 31, 45, 61 };
        int[] sortedArray = countSort(originArray);
        System.out.println(Arrays.toString(sortedArray));
    }
     public static int[] countSort(int[] array) {
        if (array == null || array.length <= 1) {
            return array;
        }
        int max = array[0], min = array[0];
        for (int i = 0; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
             if (min > array[i]) {
                min = array[i];
            }
        }
         if (max == min) {
            return array;
        }
         int[] countArray = new int[max - min + 1];
        for (int i = 0; i < array.length; i++) {
            countArray[array[i] - min]++;
        }
         //这个有些难以理解,实际是做了标记，统计数组对应位置的值变化后才赋值
        //实际数据为[1,1,1,2,2,3,3,3,3,3,4,4,4,5,5,5 ... ]类似
        int sum = 0;
        for (int i = 0; i < countArray.length; i++) {
            sum += countArray[i];
            countArray[i] = sum;
        }
         int[] sortedArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            sortedArray[countArray[array[i] - min] - 1] = array[i];
            countArray[array[i] - min]--;
        }
         return sortedArray;
    }
}

参考文章：
什么是计数排序