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

这道题就可以用计数排序来解，这种排序算法不是基于元素比较，而是利用数组下标来确定元素的正确位置

在刚才的题目里，随即整数的取值范围是从0到10，那么这些整数的值肯定是在0到10这11个数里面。于是我们可以建立一个长度为11的数组，数组下标从0到10，元素初始值全为 0，如下所示：

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

加入现在给出一个20个随机数，取值范围为从0到10：

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

遍历数组，依次将数字出现的次数的次数填入上面的长度为11的数组，最终结果如下：

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

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

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

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

说白了，还是用空间换时间。

给出一个数组arr，其取值范围为0-n

设计一个函数对它进行排序

Java实现如下：

java">public class Solution6 {
    public static void main(String[] args) {
      	//测试用例
        int[] a = {1,2,1,3,2,4,5,6,7};
        int[] b = {1};
        int[] c = {0,0,0,0};
        int[] d = {1,1,1,1};
     	int[] e = {0,2,1,3,2,4,0,6,7};
        int[] res = countSort(d,1);
        for(int each:res) System.out.println(each);
    }

    public static int[] countSort(int[] arr, int n){
        int len = arr.length;
        if(null == arr || arr.length == 0) return null;

        int[] nArray = new int[n+1];
        Arrays.fill(nArray,-1);
        for(int i=0; i<len; i++){
            if(nArray[arr[i]] == -1) nArray[arr[i]] = 1;
            else nArray[arr[i]]++;
        }
        
        int index = 0;
        for(int i=0; i<n+1; i++){
            if(nArray[i] == -1) continue;
            for(int j=0; j<nArray[i]; j++){
                arr[index] = i;
                index++;
            }
        }
        return arr;
    }
}

虽然是两个for循环嵌套，但是遍历的次数只是遍历arr的长度

时间复杂度：O(n)，跟arr的长度有关

空间复杂度：O(n)，跟取值范围n有关