import java.util.*;

public class CountingSort {

    public int[] countingSort(int[] A, int n) {

        countingSort(A);

        return A;

    }

    public void countingSort(int[] arr) {

        int[] tempArr = new int[arr.length];// 临时数组

        int[] timesArr;// 统计每个元素出现的次数，放入到对应的桶中

        int range;// 统计这一组的范围，得出需要多少个桶

        int max = arr[0];

        int min = arr[0];

        for (int a : arr) {

            if (a > max)

                max = a;

            if (a < min)

                min = a;

        }

        range = max - min + 1;// 得出极值差，为了减小临时数组(统计各元素出现的次数)的长度

        timesArr = new int[range];

        for (int i = 0; i < arr.length; i++) {

            timesArr[arr[i] - min]++;

        }

        for (int i = 1; i < timesArr.length; i++) {// 得到所有元素的大小上的总体顺序

            timesArr[i] += timesArr[i - 1];

        }

        for (int i = 0; i < arr.length; i++) {// 将arr中元素的位置顺序对应到临时数组中

            int position = timesArr[arr[i] - min];// 得到arr[i]这个元素在整体上的位置

            tempArr[--position] = arr[i];// 根据上面的位置，将该元素放入到临时数组中

            timesArr[arr[i] - min]--;

        }

        for (int i = 0; i < arr.length; i++) {

            arr[i] = tempArr[i];

        }

    }

}