计数排序和桶排序

比快排更快的算法，在理想情况下，甚至可以做到线性时间的复杂度

以前学过的排序都是基于 元素之间的比较 来进行排序的，但是有一些特殊的排序并不基于元素比较，
如：计数排序，桶排序，基数排序，

• 以计数排序来说，这种算法是利用数组下标来确定元素的位置
• 基数排序是将多位数分成个位数进行计数排序
• 桶排序是每一个桶代表一个区间范围

计数排序

思路

1. 创建一个统计数组，数组长度为 数列的最大值 - 数列的最小值 + 1，
2. 同时数列的最小值作为一个偏移量，用于计算整数在统计数组的下标
3. 遍历无序数列，将元素填入统计数组 元素值 - 偏移量 的位置
4. 对统计数组进行变形，每一个元素都加上前面所有元素之和。

   为什么相加呢？是让统计数组储存的元素值，等于相应整数的最终排序位置的序号。
   例如：下标为9的元素值为5，那么代表原始数列的整数9，最终排序在第5位

5. 倒序遍历数组，从统计数组找到正确的位置，输出到结果数组

   为什么倒序？为了不改变原有顺序，使之稳定

代码实现

public static int[] countSort(int[] array){
     int max = array[0];
     int min = array[0];
     for(int i = 0; i < array.length; i++){
         if (array[i] > max) max = array[i];
         if (array[i] < min) min = array[i];
     }
     int d = max -min;

     //填写统计数组
     int[] countArray = new int [d+1];
     for(int i = 0; i < array.length; i++)
         countArray[array[i] - min]++;

     //统计数组变形
     for(int i = 1; i < countArray.length; i++)
         countArray[i] += countArray[i-1];

     //倒序遍历原始数组
     int[] sortedArray = new int[array.length];
     for(int  i = array.length - 1; i >= 0; i--){
         sortedArray[countArray[array [i] - min] - 1] = array[i];
         countArray[array [i] - min]--;
     }

     return sortedArray;
}

优缺点

优点

• 时间复杂度仅为O(n+m)
• 空间复杂度为O(m)

缺点

1. 当数列最大和最小值差距过大时，空间浪费，时间复杂度增加
2. 必须为整数

桶排序

桶排序同样是一种线性时间的排序算法。类似于计数排序所创建的统计数组，桶排序需要创建若干个桶来协助排序。

• 每一个桶(bucket)代表一个区间范围，里面可以承载一个或多个元素

思路

1. 创建若干个桶，并确定每一个桶的区间范围

   创建几个桶，确定区间范围，有很多种不同的方式。我们这里创建的桶数量等于原始数列的元素数量，除了最后一个桶只包含数列最大值外，前面各个桶的区间按照比例来确定

2. 遍历原始数列，把元素对号入座放入各个桶中
3. 对每个桶内部的元素分别进行排序
4. 遍历所有的桶，输出所有元素

代码实现

public static double[] bucketSort(double[] array){
     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 = 9;
     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++)
         //JDK底层采用了归并排序或归并的优化版本
         Collections.sort(bucketList.get(i));

     double[] sortedArray = new double[array.length];
     int index = 0;
     //增强版的for只能遍历，不能修改值
     for(LinkedList<Double> list : bucketList) {
         for (double element : list) {
             sortedArray[index++] = element;
         }
     }
     return sortedArray;
}

优缺点

优点

• 时间复杂度仅为O(n)
• 空间复杂度为O(m)

缺点

不稳定，第一个桶有n-1个元素，最后一个桶只有一个，此时时间复杂度退化为O(nlogn)，而且白白的创建了许多空桶