算法-计数排序

计数排序流程

数组A，参与排序的值需要大于0
一： 计算出当前数组的最大值(K)。
二：创建一个最大值长度的数组©。
三：计算数组中，每个元素出现的次数。存放在C数组上，以值作为C的索引，次数作为值。这步操作之后C索引的顺序即为A数组中值的顺序。
四： 循环C数组，C[i] = C[i] + C[i-1]。这步计算出A每个元素，排序后的位置。
五：创建数组B，长度和A一致。
五：循环A数组，获取到A数组中的值(v)，以v为索引从数组C中获取值(index)。以index作为B数组的索引设置值V。c[v]= c[v] -1。
c[v]= c[v] -1:特别说明在C中如果有相同值(v)，则相同值索引的位置v前一个索引+相同值的次数。即相同值可以索引的最大值，所以使用的时候索引需要-1，

Java代码实现

import java.util.Arrays;

/**
 * 计数排序：假设有n个元素，每个元素的值都在0到k之间的一个整数，
 */
public class CountSort {

    public static void main(String... args){
        int[] arr = {6,1,10,3,3,4,4};
        countSort(arr);
    }
    private static void countSort(int[] arr){
        System.out.println("A的数组："+Arrays.toString(arr));
        int[] b = new int[arr.length];
        int k = findMax(arr);
        int[] c = new int[k];
        //计算每一个值，有几个
        //并按照值的顺序排列好对应的个数
        for(int i = 0; i < arr.length; i++){
            //获取i的值，因数组的索引是从0开始计数的，作为数组索引需要减1
            int v = arr[i]-1;
            //计算相同值的个数，c[v]默认为0
            c[v] = c[v] + 1;
        }
        System.out.println("C1的数组："+ Arrays.toString(c));
        //计算出A数组排序后每个元素所在位置
        //相同值下标索引会跳跃，索引位置在前一个值+相同值次数
        for(int i = 1; i < k; i++){
            c[i] = c[i] + c[i-1];
        }
        //
        System.out.println("C2的数组："+ Arrays.toString(c));
        for(int i = 0; i < arr.length; i++){
            //获取到数组的
            int av = arr[i] - 1;
            //在C的索引中，找到排序后的位置
            b[c[av]-1] = arr[i];
            //避免相同值全部放在一个位置，相同值每次都需要减1.
            //减1操作的次数，和计算相同值的个数对应
            c[av] = c[av] - 1;
        }
        System.out.println("C3的数组："+ Arrays.toString(c));
        System.out.println("B的数组："+ Arrays.toString(b));
    }
    private static int findMax(int[] arr){
        int max = arr[0];
        for(int i = 1; i < arr.length; i++){
            if(max < arr[i]){
                max = arr[i];
            }
        }
        return max;
    }
}

小结

c[av] = c[av] - 1，这个步骤是解决相同值的问题