排序：计数排序

原理

计数排序要求要排序的数据必须是介于一定范围的整数。

假设要排的数介于0~k之间，且保存在数组A中，排序结果保存在数组Z中。可以建立一个临时数组T[k+1],将数组A中值为i的元素用T的下标i表示，而T[i]的值就是A中小于等于i的个数。然后通过T将A中的数一一映射到Z中。

举例

假设A={0,4,2,2,3},由于A中的数据范围介于0~4之间，故建立T[5]并初始化为0。

其中小于等于0的数只有它本身一个，故T[0]=1；小于等于2的有3个，故T[2]=3；小于等于3的有4个，故T[3]=4；小于等于4的有5个，故T[4]=5。

接下来就是将A中的数通过T映射到Z中。我们可以从A[0]遍历到A[4]:

1.A[0]=0,由T[0]=0知道小于等于它的只有它本身一个，那他肯定是最小的那个，所以我们可以将它排在Z中的第一位即Z[0]中，然后T[0]自减；

2.A[1]=4,由T[4]=5知道它应该排在Z[4]的位置，然后T[4]自减；

3.A[2]=2,由T[2]=3知道它应该排在Z[2]的位置，然后T[2]自减，为什么要自减？因为如果不自减的话下次再排2的时候又会排在Z[2]的位置上，实际上前面已经排了一次了，所以现在小于等于它的数肯定少了一个。故要自减；

4.A[3]=2,由于前面T[2]自减了一次，所以T[2]=2，现在的2应该排在Z[1]的位置。

5.A[4]=3,T[3]=4,故3排在Z[3]位置。

遍历完成，Z[0]到Z[4]依次为0，2，2，3，4。完成排序。

明白原理后写代码就很简单了。。