一、桶排序简介

          前面我们介绍的所有排序，选择排序、冒泡排序、插入排序、归并排序、快速排序、堆排序等，都是基于比较的排序，而桶排序是基于容器的排序，主要分为：计数排序和基数排序，时间复杂度都是O(N)，额外空间复杂度O(M),但是应用范围有限，需要样本的数据状况满足桶的划分。

二、计数排序

计数排序，不是基于元素比较，而是利用数组下标确定元素的正确位置。
1：找出原数组中元素值最大的，记为max。
2：创建一个新数组count，其长度是max加1，其元素默认值都为0。
3：遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。
4：创建结果数组result，起始索引index。
5：遍历count数组，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到result数组中去，每处理一次，count中的该元素值减1，直到该元素值不大于0，依次处理count中剩下的元素。
6：返回结果数组result。

    private static int[] countSort(int[] arr){
        if(arr==null||arr.length==1){
            return arr;
        }
        // 找出原数组中元素值最大的，记为max
        int max =0;
        for(int i=0;i<arr.length;i++){
            max=Math.max(arr[i],max);
        }
        // 创建一个新数组count，其长度是max加1，其元素默认值都为0。
        int[] bucket = new int[max+1];
        // 遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。
        for(int i=0;i<arr.length;i++){
            bucket[arr[i]]++;
        }
        // 创建结果数组result，起始索引index。这里简化下，直接复用原数组arr
        int index = 0;
        // 遍历count数组，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到result数组中去，每处理一次，count中的该元素值减1，直到该元素值不大于0，依次处理count中剩下的元素
        for(int i=0;i<bucket.length;i++){
            while(bucket[i]>0){
                arr[index++]=i;
                bucket[i]--;
            }
        }
        return arr;
    }

三、基数排序

基数排序的原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。即：将所有待排序的数统一为相同的数位长度，数位较短的数前面补零，然后从低位到高位按位比较，位数字小的排在前面，大的排在后面，这样当比较第N位时前N-1位都是有序的，如此循环的比较，直到最高位比较完成，整个序列就是有序的了。

编程中，我们进行了优化，使用一个0到9的数组代替了桶，也是基数排序的经典实现，代码如下：

    private static int[] radixSort(int[] arr){
        if(arr==null||arr.length==1){
            return arr;
        }
        // 表示基于10进制
        final int radix = 10;
        // 查询数组中的最大值
        int max =0;
        int i=0,j=0;
        for(;i<arr.length;i++){
            max=Math.max(arr[i],max);
        }
        // 最大值的位数
        int digit = (max+"").length();
        // 创建一个新数组
        int[] help = new int[arr.length];
        // 开始排序，最大值有几位，循环处理几次
        for(int d=1;d<=digit;d++){
            // 创建一个新数组
            int[] count = new int[radix];
            // 遍历原数组，分别取出其对应位置上的数字，先从个位数开始，每次取到一次，count数组对应的索引位置+1
            for(i=0;i<arr.length;i++){
                // 取出对应位置上的数字
                j = getDigit(arr[i],d);
                count[j]++;
            }
            // 将数组转换
            for(i=1;i<count.length;i++){
                count[i]=count[i]+count[i-1];
            }
            // 原数组倒序遍历
            for(i=arr.length-1;i>=0;i--){
                // 取出对应位置上的数字
                j = getDigit(arr[i],d);
                help[count[j]-1]=arr[i];
                count[j]--;
            }
            // 把help中的数据拷贝到arr中
            for(i=0,j=0;i<arr.length;i++,j++){
                arr[i] = help[j];
            }
        }
        return help;

    }

    private static int getDigit(int x, int d) {
        return ((x/((int)Math.pow(10,d-1)))%10);
    }

四、排序算法的稳定性

五、排序算法总结