万字长文|十大基本排序，一次搞定！ (6)

这个可以用偏移量解决，找到最大和最小的元素，计算偏移量，例如[9992,9998,9993,9999]，偏移量=9999-9992=7，我们只需要建立一个容量为8的数组就可以了。

解决第二个问题的版本如下：

public class CountSort1 { public void sort(int[] nums) { //查找最大值 int max = findMax(nums); //寻找最小值 int min = findMin(nums); //偏移量 int gap = max - min; //创建统计次数新数组 int[] countNums = new int[gap + 1]; //将nums元素出现次数存入对应下标 for (int i = 0; i < nums.length; i++) { int num = nums[i]; countNums[num - min]++; nums[i] = 0; } //排序 int index = 0; for (int i = 0; i < countNums.length; i++) { while (countNums[i] > 0) { nums[index++] = min + i; countNums[i]--; } } } public int findMax(int[] nums) { int max = nums[0]; for (int i = 0; i < nums.length; i++) { if (nums[i] > max) { max = nums[i]; } } return max; } public int findMin(int[] nums) { int min = nums[0]; for (int i = 0; i < nums.length; i++) { if (nums[i] < min) { min = nums[i]; } } return min; } } 计数排序性能分析

时间复杂度

我们整体运算次数是n+n+n+k=3n+k，所以使劲复杂度是O(n+k)。

空间复杂度

引入了辅助数组，空间复杂度O(n)。

稳定性

我们的实现实际上是不稳定的，但是计数排序是有稳定的实现的，可以查看参考[1]。

同时我们通过实现也发现，计数排序实际上不适合有负数的，元素偏移值过大的数组。

桶排序

桶数组可以看做计数排序的升级版，它把元素分到若干个桶中，每个桶中的元素再单独排序。

桶排序原理

桶排序大概的过程：

设置一个定量的数组当作空桶；

遍历输入数据，并且把元素一个一个放到对应的桶里去；

对每个不是空的桶进行排序；

从不是空的桶里把排好序的数据拼接起来。

桶排序动图如下（动图来源参考[1]）：

我们上面说了，计数排序不适合偏移量过大的数组，我们拿一个偏移量非常大的数组[2066,566,166，66,1066，2566，1566]为例，来看看桶排序的过程。

创建6个桶，分别存储0-500,500-1000,1000-1500,1500-2000,2000-2500,2500-3000的元素

遍历数组，将元素分别分配到对应的桶中

桶中元素排序，这里我们明显只用排序第一个桶

将桶中的元素依次取出，取出的元素就是有序的了

桶排序代码实现

桶排序的实现我们要考虑几个问题：

桶该如何表示？

桶的数量怎么确定？

桶内排序用什么方法？

我们来看一下代码：

public class BucketSort { public void sort(int[] nums) { int len = nums.length; int max = nums[0]; int min = nums[0]; //获取最大值和最小值 for (int i = 1; i < len; i++) { if (nums[i] > max) { max = nums[i]; } if (nums[i] < min) { min = nums[i]; } } //计算步长 int gap = max - min; //使用列表作为桶 List<List<Integer>> buckets = new ArrayList<>(); //初始化桶 for (int i = 0; i < gap; i++) { buckets.add(new ArrayList<>()); } //确定桶的存储区间 int section = gap / len - 1; //数组入桶 for (int i = 0; i < len; i++) { //判断元素应该入哪个桶 int index = nums[i] / section - 1; if (index < 0) { index = 0; } //对应的桶添加元素 buckets.get(index).add(nums[i]); } //对桶内的元素排序 for (int i = 0; i < buckets.size(); i++) { //这个底层调用的是 Arrays.sort // 这个api不同情况下可能使用三种排序：插入排序，快速排序，归并排序，具体看参考[5] Collections.sort(buckets.get(i)); } //将桶内的元素写入原数组 int index = 0; for (List<Integer> bucket : buckets) { for (Integer num : bucket) { nums[index] = num; index++; } } } } 桶排序性能分析

时间复杂度