计数排序

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 [1] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序）

第一步：找出原数组中元素值最大的，记为max。

第二步：创建一个新数组count，其长度是max加1，其元素默认值都为0。

第三步：遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。

第四步：创建结果数组result，起始索引index。

第五步：遍历count数组，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到result数组中去，每处理一次，count中的该元素值减1，直到该元素值不大于0，依次处理count中剩下的元素。

第六步：返回结果数组result。

public int[] countSort(int[] A) {
    // 找出数组A中的最大值
    int max = Integer.MIN_VALUE;
    for (int num : A) {
        max = Math.max(max, num);
    }
    // 初始化计数数组count
    int[] count = new int[max+1];
    // 对计数数组各元素赋值
    for (int num : A) {
        count[num]++;
    }
    // 创建结果数组
    int[] result = new int[A.length];
    // 创建结果数组的起始索引
    int index = 0;
    // 遍历计数数组，将计数数组的索引填充到结果数组中
    for (int i=0; i<count.length; i++) {
        while (count[i]>0) {
            result[index++] = i;
            count[i]--;
        }
    }
    // 返回结果数组
    return result;
}

桶排序

当数列取值范围过大，或者不是整数时，不能使用计数排序，但是可以使用桶排序。
那么，桶排序当中所谓的“桶”，又是什么概念呢？
每一个桶（bucket）代表一个区间范围，里面可以承载一个或多个元素。

桶排序的第一步，就是创建这些桶，确定每一个桶的区间范围：

具体建立多少个桶，如何确定桶的区间范围，有很多不同的方式。我们这里创建的桶数量等于原始数列的元素数量，除了最后一个桶只包含数列最大值，前面各个桶的区间按照比例确定。
区间跨度 = （最大值-最小值）/ （桶的数量 - 1）

第二步，遍历原始数列，把元素对号入座放入各个桶中：

第三步，每个桶内部的元素分别排序（显然，只有第一个桶需要排序）：

第四步，遍历所有的桶，输出所有元素：

0.5，0.84，2.18，3.25，4.5

到此为止，排序结束。

代码中，所有的桶保存在ArrayList集合当中，每一个桶被定义成一个链表（LinkedList），这样便于在尾部插入元素。

定位元素属于第几个桶，是按照比例来定位：

(array[i] - min) * (bucketNum-1) / d

同时，代码使用了JDK的集合工具类Collections.sort来为桶内部的元素进行排序。Collections.sort底层采用的是归并排序或Timsort，小伙伴们可以简单地把它们当做是一种时间复杂度 O（nlogn）的排序。

第一步求数列最大最小值，运算量为n。

第二步创建空桶，运算量为m。

第三步遍历原始数列，运算量为n。

第四步在每个桶内部做排序，由于使用了O（nlogn）的排序算法，所以运算量为 n/m * log(n/m ) * m。

第五步输出排序数列，运算量为n。加起来，总的运算量为 3n+m+ n/m * log(n/m ) * m = 3n+m+n(logn-logm) 。去掉系数

import java.util.*;
import java.util.concurrent.Executors;

import static sun.misc.Version.println;

public class test{
     public static void main(String[] args) {
        double[] m=new double[5];
         Scanner sc=new Scanner(System.in);
         for (int j = 0; j < 5; j++) {
             m[j]=sc.nextDouble();
         }
         for(double temp:bucketSort(m)){
             System.out.println(temp);
         }
    }
    public static double[] bucketSort(double[] array){
        //得到数列的最大值和最小值，并计算出差值d
        double max=array[0];
        double min=array[0];
        for (int i=1;i<array.length;i++){
            if (array[i]>max){
                max=array[i];
            }
            if (array[i]<min){
                min=array[i];
            }
        }
        double d=max-min;
        //初始化桶
        int bucketNum=array.length;
        ArrayList<LinkedList<Double>> bucketList=new ArrayList<LinkedList<Double>>(bucketNum);
        for (int i=0;i<bucketNum;i++){
            bucketList.add(new LinkedList<Double>());
        }

        //遍历原始数组将每个元素放入桶中
        for (int i=0;i<array.length;i++){
            int num=(int)((array[i]-min)*(bucketNum-1)/d);
            bucketList.get(num).add(array[i]);
        }

        //对每个桶内部进行排序
        for(int i=0;i<bucketList.size();i++){
            // 使用Collections.sort，其底层实现基于归并排序或归并排序的优化版本
            Collections.sort(bucketList.get(i));
        }

        //输出全部元素
        double[] sortedArray=new double[array.length];
        int index=0;
        for (LinkedList<Double> list:bucketList) {
            for (double element:list){
                sortedArray[index]=element;
                index++;
            }
        }
        return sortedArray;
    }

}

时间复杂度为：
O(n+m+n(logn-logm)）
至于空间复杂度就很明显了：
空桶占用的空间 + 数列在桶中占用的空间 = O（m+n）。
桶排序性能不是绝对稳定的，当桶中元素分布均匀，当n=m时，时间复杂度为O(n),当极端情况下第一个桶中由n-1个元素，最后一个桶中有一个元素，时间复杂度将退化为O(nlogn)，而且拜拜浪费空桶