排序专题（四）计数排序、桶排序
计数排序是一种稳定的排序算法，但是需要额外的空间消耗。计数排序的核心思想就是统计序列中的值出现的次数放在额外的数组C中，根据数组C将序列中的元素进行正确的排序。接下来我们来看具体的步骤：
找出序列中的最大(max)最小值(min)。
创建一个长度为(max-min+1)的数组C。
统计序列中的每个元素(val)出现的次数，放在数组C中第val个位置处。
循环数组C，并循环出现的次数，输出新数组。
public int[] countSort(int[] A) {//一：求取最大值和最小值，计算中间数组的长度：// 中间数组是用来记录原始数据中每个值出现的频率int max = A[0], min = A[0];for (int i : A) {if (i > max) {max = i;}if (i < min) {min = i;}}//二：有了最大值和最小值能够确定中间数组的长度//存储5-0+1 = 6int[] pxA = new int[max - min + 1];//三.循环遍历旧数组计数排序: 就是统计原始数组值出现的频率到中间数组B中for (int i : A) {pxA[i - min] += 1;//数的位置 上+1}//四.遍历输出//创建最终数组，就是返回的数组，和原始数组长度相等，但是排序完成的int[] result = new int[A.length];int index = 0;//记录最终数组的下标//先循环每一个元素 在计数排序器的下标中for (int i = 0; i < pxA.length; i++) {//循环出现的次数for (int j = 0; j < pxA[i]; j++) {//pxA[i]:这个数出现的频率result[index++] = i + min;//以为原来减少了min现在加上min，值就变成了原来的值}}return result;}
复杂度分析
时间复杂度：T(n) = O(n+k)。当给定n个0~k之间的整数。
空间复杂度：T(n) = O(n+k)。
平均情况：T(n) = O(n+k)。
💁额外说明：
计数排序只能应用于输入的序列是有确定范围的整数，而且如果输入的序列跨度很大，最小值很小，最大值很大，这就使得需要的额外空间会很大。
桶排序算是计数排序的升级版，所以这儿我们也放在一起来说。
桶排序是稳定的；
桶排序是常见排序算法中最快的一种，大多数情况下比快排和归并排序还要快。
桶排序非常快但是也非常消耗空间，典型的以空间换时间，基本上是最耗内存的一种排序算法。
桶排序的核心思想就是对序列中的数取模然后对应到每个桶里，每个桶里可放多个数。
代码：
public double[] bucketSort(double[] arr){//1.计算出最大值和最小值，求出两者的差值double min = arr[0];double max = arr[0];for (int i = 1; i < arr.length; i++) {if (max < arr[i]){max = arr[i];}if (arr[i] < min){min = arr[i];}}double d = max - min;//2.初始化桶int bucketNum = arr.length;List<LinkedList<Double>> bucketList = new ArrayList<>(bucketNum);for (int i = 0; i < bucketNum; i++) {bucketList.add(new LinkedList<>());}//3.遍历数组中的元素，把所有元素都放入对应的桶当中for (int i = 0; i < arr.length; i++) {//计算当前元素应该放在哪个桶里面double t= (d / (bucketNum - 1));double x = (arr[i] - min);int num = (int)( x/ t );bucketList.get(num).add(arr[i]);}//4.对每个桶里面的元素进行排序for (int i = 0; i < bucketNum; i++) {Collections.sort(bucketList.get(i));}//5.输出全部元素int k = 0;for(LinkedList<Double> doubles : bucketList){for (Double aDouble : doubles) {arr[k] = aDouble;k++;}}return arr;}
时间复杂度：T(n) = O(n+k)。当给定n个0~k之间的整数。
空间复杂度：T(n) = O(n+k)。
平均情况：T(n) = O(n+k)。
不积跬步，无以至千里。
文章有帮助的话，点个转发、在看呗
。
谢谢支持哟 (*^__^*)
END
👇