计数排序（Counting Sort）详解

public class Test {

    public static void main(String[] args) {
        int[] arr = new int[]{5,2,3,1,6,7,1,3};
        countingSort(arr);
    }

    public static void countingSort(int[] arr){
        System.out.println("原始数组："+ Arrays.toString(arr));
        //获取排序数组的长度
        int len=  arr.length;
        //获取数组最大元素
        int max = Arrays.stream(arr).max().getAsInt();
        //获取数组最小元素
        int min = Arrays.stream(arr).min().getAsInt();
        //计算计数数组的长度
        int rang = max-min+1;
        //创建计数数组
        int count[] = new int[rang];
        //创建排序后的目标数组
        int result[] = new int[len];
        //计数:统计每个元素出现的次数
        for(int i = 0; i < len; i++){
            count[arr[i]-min]++;
        }
        System.out.println("计数数组："+ Arrays.toString(count));
        //累计计数:计算每个元素在排序后数组中的位置
        for(int j = 1 ;j < rang; j++){
            count[j]+=count[j-1];
        }
        System.out.println("累计计数数组："+ Arrays.toString(count));
        //排序：根据累计计数数组将元素放置到正确的位置
        for(int k = len -1 ; k >= 0; k--){
            result[count[arr[k] - min] -1] = arr[k];
            count[arr[k] - min]--;
        }
        System.arraycopy(result, 0, arr, 0, len);
        System.out.println("排序完成的数组："+ Arrays.toString(arr));
    }
}

原始数组：[5, 2, 3, 1, 6, 7, 1, 3]
计数数组：[2, 1, 2, 0, 1, 1, 1]
累计计数数组：[2, 3, 5, 5, 6, 7, 8]
排序完成的数组：[1, 1, 2, 3, 3, 5, 6, 7]