计数排序

计数排序

Description

实现计数排序，通过多次遍历数组，统计比每一个元素小的其它元素个数，根据该统计量对数据进行排序。

Input

输入的每一行表示一个元素为正整数的数组，所有值用空格隔开，第一个值为数值长度，其余为数组元素值。

Output

输出的每一行为排序结果，用空格隔开，末尾不要空格。

Solution

public class CountSort {

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int len = in.nextInt();
            int[] arr = new int[len];
            for(int i = 0; i < len; i++){
                arr[i] = in.nextInt();
            }
            countSort(arr);
        }
    }

    public static void countSort(int[] arr){
        int min = arr[0];
        int max = arr[0];
        for(int i = 1; i < arr.length; i++){
            if(arr[i] > max){
                max = arr[i];
            }
            if(arr[i] < min){
                min = arr[i];
            }
        }

        int[] count = new int[max - min + 1];
        int[] res = new int[arr.length];
        for(int i = 0; i < arr.length; i++){
            int pos = arr[i] - min;
            count[pos] += 1;
        }
        for(int i = 1; i < count.length; i++){
            count[i] += count[i - 1];
        }
        for(int i = arr.length - 1; i >= 0; i--){
            int pos = arr[i] - min;
            res[count[pos] - 1] = arr[i];
            count[pos]--;
        }

        System.out.print(res[0]);
        for(int i = 1; i < res.length; i++){
            System.out.print(" " + res[i]);
        }
        System.out.println();
    }
}