计数排序的前提是长度为n数组里面的元素为整数并且元素值的范围为0~k,时间复杂度为O(n+k),当k=O(n)时，排序的时间复杂度为O(n)，并且是一种稳定的排序
Counting Sort 的思想是使用一个辅助数组记录元素应该被放置的位置。比如以数组{2, 5, 3, 0, 2, 3, 0, 3}为例，比5小的元素有七个，那么排序之后5应该位于第八个元素的位置
java 实现
import java.util.Arrays;
public class CountingSort {
public static int[] countingSort(int[] A, int k) {
int[] B = new int[A.length];
int[] C = new int[k + 1];
//C数组表示A数据中元素的个数
for (int i = 0; i < A.length; i++) {
C[A[i]] += 1;
}
//C数组表示A中元素放的位置
for (int i = 1; i <= k; i++) {
C[i] = C[i] + C[i - 1];
}
for (int i = A.length - 1; i >= 0; i--) {
B[C[A[i]] - 1] = A[i];//把元素放到对应的位置，-1是因为数组下标从0开始
C[A[i]] -= 1;//可能有相同的元素
}
return B;
}
public static void main(String[] args) {
int[] A = {2, 5, 3, 0, 2, 3, 0, 3};
System.out.println(Arrays.toString(countingSort(A, 5)));
}
}
