上手难度：★★★

算法复杂度：Ο(n+k)

（其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序）

jishu.gif

排序思想：

先通过遍历获取到数组arr中的最大值，然后再new一个尺寸比最大值大1的数组bucket，用于将arr里所有的值对应到bucket的索引中，对应上的就自增1，这样bucket数组中没有对应到arr值的索引的位置上的值就为0，然后再循环遍历bucket，将有值的索引值挨个填入arr里，自然完成了排序工作

代码实现：

public class CountingSort {

    public static int[] sort(int[] arr){

        int maxValue = getMaxValue(arr);

        return countingSort(arr, maxValue);
    }

    private static int[] countingSort(int[] arr, int maxValue) {
        int bucketLen = maxValue + 1;
        //new一个最大值加+1数量的数组，目的是把arr里所有的值作为索引都能放入这个bucket数组中
        int[] bucket = new int[bucketLen];

        //将数组每一个值都放置bucket中作为索引自增
        for (int value : arr) {
            bucket[value]++;
        }

        int sortedIndex = 0;
        //循环这个bucket数组
        for (int j = 0; j < bucketLen; j++) {
            //当索引对应的值大于0时，又将索引值转而赋给arr，并且将sortedIndex自增，同时bucket索引对应的值自减，这样重复的元素也考虑到了
            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;
    }

    public static void main(String[] args) {

        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        sort(arr);

        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }

    }
}

优点：

巧妙的利用了新的数组的索引对应上了就自增，没对应上就默认为0的思路，自然将有值的索引按顺序挑选了出来