计数排序

计数排序是一种特殊的桶排序，桶数为1。

注意：实际计数排序的选数过程不是图中所描述的这样

时间复杂度为O(n + m)其中n为输入规模，m为元素范围
空间复杂度为O(n + m)其中n为目标数组，m为计数数组

适用于待排元素很多，但元素的范围远远小于元素的个数的情况！
统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的第i位！

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n], b = new int[n], c = new int[100];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            c[a[i]]++;
        }
        for (int i = 1; i < 100; i++) {
            c[i] += c[i - 1];
        }
        //for从大往小遍历是为了有序
        for (int i = n - 1; i >= 0; i--) {
            b[c[a[i]] - 1] = a[i];
            c[a[i]]--;
        }
        for (int i = 0; i < n; i++) {
            System.out.print(b[i] + " ");
        }
    }
}

像这种代码元素范围只能是[0, 99]

优化：举个例子，如果所有待排元素范围是[1000, 10000]，就没有必要开辟[0, 10000]的辅助数组
可以用一个偏移量min。