计数排序

public class _CountSort {
    public static void SortNum(int [] arr){

        int min=arr[0],max=arr[0];
        int []sortedArr=new int[arr.length];
        //找到待排数据的范围
        for(int i:arr){
            if(i<min)
                min=i;
            else if(i>max)
                max=i;
        }
        int count[]=new int[max-min+1];
        //统计每一个带牌数据出现的次数
        for(int i:arr){
            count[i-min]++;
        }
        //统计每一个数据之前一共出现了多少个数据，就是知道每一个数据的最后一个元素的位置
        for (int i = 1; i < count.length; i++) {
            count[i]=count[i-1]+count[i];
        }
        //从后往前找，为了使得排序结果是稳定的
        for(int i=arr.length-1;i>=0;i--){
            sortedArr[--count[arr[i]-min]]=arr[i];
        }
        System.arraycopy(sortedArr,0,arr,0,arr.length);
    }
}