package 基础算法;

/**
 * @author rd-yyx
 * @version 1.0
 * @date 2020/5/20 10:57 上午
 */
public class CountingSort {
    public static void countingSort(int[] a,int n){
        if(n <= 1) return;

        int max = a[0];
        for(int i = 1; i < n ;i++){
            if(a[i] > max) {
                max = a[i];
            }
        }

        int[] c = new int[max+1];
        for(int i = 0; i < n ;i++){
            c[a[i]]++;
        }

        for(int i = 1; i < max+1 ;i++){
            c[i]  = c[i] + c[i - 1];
        }

        int[] r = new int[n];
        for(int i = n-1;i >= 0; --i){
            int index = c[a[i]]-1;
            r[index] = a[i];
            c[a[i]]--;
        }

        for(int i = 0; i < n ; i++){
            a[i] = r[i];
        }
    }

    public static void main(String[] args) {
        int[] a = {2, 5, 3, 0, 2, 3, 0, 3};
        countingSort(a,8);
        for (int i : a) {
            System.out.println(i);
        }
    }
}