import java.util.Arrays;

public class CountingSort{

    public static void main(String[] args) throws Exception {
        int[] scores = {9, 3, 4, 9, 1, 2, 7, 8,1,3, 3, 4, 0, 10, 9, 7, 9};
        for (int n : sort(scores)) {
            System.out.println(n);
        }
    }

    public static int[] sort(int[] sourceArray) throws Exception {
        // 對 arr 進行拷貝，不改變參數(shù)內容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
                //
        int maxValue = getMaxValue(arr);

        return countingSort(arr, maxValue);
    }

    private static int[] countingSort(int[] arr, int maxValue) {
        int bucketLen = maxValue + 1;
        int[] bucket = new int[bucketLen];

        for (int value : arr) {
            bucket[value]++;
        }

        int sortedIndex = 0;
        for (int j = 0; j < bucketLen; j++) {
            while (bucket[j] > 0) {
                arr[sortedIndex++] = j;
                bucket[j]--;
            }
        }
        return arr;
    }

    private static int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }
}