计数排序（Counting Sort）

计数排序的前提是长度为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)));
    }
}