桶排序思想下的排序算法—

桶排序的思想就是把数据放入到多个桶里面，在对桶里面的数据进行排序。

之前学过的排序（冒泡、选择、快排、堆排、归并）都是基于比较之间的排序，而桶排序不是基于比较的排序。

比如计数排序，顾名思义就是统计一个数字出现的次数，用一个桶来记录每一个数字出现的次数，最后再将桶由指定的顺序将数字取出。

计数排序时间复杂度：O(N)。

计数排序的使用条件：数据状况处于一个有限的范围内，这个范围要尽量的小。

public static void countSort(int[] arr){
        if (arr==null || arr.length <2){
            return;
        }
        //找数组中的最大值，用来为辅助数组设置空间
        int max = Integer.MIN_VALUE;
        for (int i = 0;i<arr.length;i++){
            max = Math.max(max,arr[i]);
        }
        int[] bucket = new int[max + 1];
        for (int i = 0;i<arr.length;i++){
            bucket[arr[i]]++;
        }
        int i = 0;
        for (int j = 0;j<bucket.length;j++){
            while (bucket[j]-- > 0){
                arr[i++] = j;
            }
        }
    }

桶排序思想下的排序算法——计数排序

推荐阅读