桶排序与力扣（LeetCode） -164 最大间距
在我的博客冒泡排序、插入排序、快速排序、堆排序、归并排序总结中介绍了几种经典的排序方法，其中快速排序、堆排序和归并排序的平均时间复杂度都是nlog(n)。下面我将会介绍另一种经典的排序算法，平均时间复杂度可以达到o(n)，但是有几个限制条件，我们来看一下。
桶排序
首先我们来了解一下桶排序的思想。桶排序是体现了分治的思想。原理是创建若干个桶，通过某种映射将待排序的元素放置到桶中，使每个桶中的最大值都小于他后面一个桶的最小值，并且每个桶容纳的元素数量尽可能平均。然后对每个桶中的元素排序。最后将所有桶中的元素依次输出。
下面两副图很好的解释了桶排序的思想。
2018033115584192.gif
20180331155854638.png
有几个关键的因素影响了桶排序的时间复杂度和空间复杂度
1.待排序元素的分布情况
如果我们要对{1，2，3，4，5，90}进行排序，假设桶的个数就是元素的个数，那么会出现第一个桶有5个元素，中间的桶都是空的，最后一个桶有一个元素。这样，时间复杂度就退化成nlog(n)。
2.桶的个数
桶的个数越多，每个桶中的数量就越少，每个桶内进行排序的时间复杂度就约低。当桶的个数满足每个桶只装一个元素时，桶排序所消耗的主要在为每个元素分配桶上面，为o(n)。
桶排序代码实现
public class BucketSort {
public int[] sort(int[] src,int bucketNum) {
if(src==null||src.length<2)
return src;
int myBucketNum = bucketNum > src.length ? src.length : bucketNum; //排除异常桶个数
Bucket[] buckets = new Bucket[myBucketNum]; //创建桶
int max = src[0];
int min = src[0];
for(int i=1;i<src.length;i++) { //寻找最大值和最小值
if(src[i]>max)
max=src[i];
if(src[i]<min)
min=src[i];
}
if(max==min)
return src;
int capacity = (int)Math.ceil((double)(max-min+1)/myBucketNum); //计算每个桶的容量
for(int i=0;i<src.length;i++) { //遍历每个元素，将元素分配到对应桶中
int bucketIndex = getBucketIndex(capacity,min,src[i]);
putNumInBucket(buckets,bucketIndex,src[i]);
}
int[] result = new int[src.length];
int resultIndex=0;
for(int i=0;i<myBucketNum;i++) { //将所有桶中的数据合并
if(buckets[i]!=null) {
Node tempNode=buckets[i].node;
while(tempNode!=null) {
result[resultIndex]=tempNode.value;
tempNode=tempNode.next;
resultIndex++;
}
}
}
return result;
}
/**
* 获得num所分配的桶的index
* @param capacity
* @param min
* @param num
* @return
*/
private int getBucketIndex(int capacity,int min,int num) {
return (num-min)/capacity;
}
/**
* 将num分配到桶中，并使用插入排序对桶内元素进行排序
* @param buckets
* @param index
* @param num
*/
private void putNumInBucket(Bucket[] buckets,int index,int num) {
if(buckets[index]==null) {
buckets[index] = new Bucket();
}
Node pre=null;
Node cur=buckets[index].node;
Node newNode = new Node();
newNode.value = num;
while(cur!=null&&cur.value<num) {
pre=cur;
cur=cur.next;
}
if(pre==null) {
buckets[index].node=newNode;
if(cur!=null)
newNode.next=cur;
}else {
if(cur==null) {
pre.next=newNode;
}else {
pre.next=newNode;
newNode.next=cur;
}
}
}
/**
* 桶
* @author TinyMonster
*
*/
private class Bucket{
Node node;
}
/**
* 链表结点
* @author TinyMonster
*
*/
private class Node{
int value;
Node next;
}
public static void main(String[] args) {
BucketSort bucketSort = new BucketSort();
int[] src = {4,1,7,2,9,3,0,6,5,8,11};
int[] result = bucketSort.sort(src, 3);
for(int i=0;i<result.length;i++) {
System.out.println(result[i]);
}
}
}
时间复杂度分析
在桶排序中，我们首先遍历所有元素，找出来最大值和最小值，这个操作的时间复杂度是o(n)。
然后我们遍历每个元素，将元素分配到对应的桶中，并将桶内元素排序。假设元素总个数是N，桶的个数是M，元素都平均分布（最好情况），使用nlog(n)的排序方法对每个桶内元素进行排序，这个操作时间复杂度是M(N/M)log(N/M)；当M==N是，这个操作的时间复杂度是o(n)。
最后我们遍历所有元素，得到最终结果，时间复杂度是o(n)。
因此最好情况下的时间复杂度是o(n)。
但是当元素分布极不均匀的情况下，时间复杂度退化成nlog(n)。
空间复杂度：
使用了链表来保存中间结果，空间复杂度是o(n)
（LeetCode） -164 最大间距
了解了桶排序的思想，我们来看一下下面一道题，也是用桶排序的思想来解决的。
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
示例 1:
输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:
输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。
说明:
你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
解题思路
题目要求在线性时间复杂度和空间复杂度的前提下找到相邻元素的最大差。
我们可以先对元素进行排序，为了达到线性时间复杂度，我们采用桶排序（也可以使用计数排序，不过使用桶排序在该题中空间复杂度更小）。
我们可以很巧妙地设置每个桶的大小：假设所有元素的最大值为max,最小值为min，元素个数是n，则最大间距将不小于Math.ceil((max-min)/(n-1))。因此，我们设置桶的容量是Math.ceil((max-min)/(n-1))，则桶内的元素的间距肯定不是最大间距，我们只需要查看桶间的间距（前一个桶的最大值和后一个桶的最小值的差）的最大值即可。
此外，在桶内并不需要保存每个元素，只需要保存该桶的最大值和最小值即可。
有了上面的思路，我们可以写出来下面的代码
class Solution {
public int maximumGap(int[] nums) {
if(nums==null||nums.length<2)
return 0;
double min=nums[0];
double max=nums[0];
for(int i=0;i<nums.length;i++){ //遍历所有元素，找到最大值和最小值
min = nums[i]<min ? nums[i]:min;
max = nums[i]>max ? nums[i]:max;
}
if(min==max)
return 0;
Bucket[] buckets=new Bucket[nums.length];
int gap=(int)Math.ceil((max-min)/(nums.length-1)); //计算桶的容量
for(int i=0;i<nums.length;i++){ //遍历每个元素，计算该元素应该放置的桶的位置，将元素放入桶中，更新桶的最大值和最小值
int index=getBucketIndex((int)min,nums[i],gap);
putInBucket(buckets,nums[i],index);
}
int maxGap=buckets[0].max-buckets[0].min;
int pre=buckets[0].max;
for(int i=1;i<buckets.length;i++){ //遍历所有桶，计算最大间距（桶间间距）
if(buckets[i]!=null){
if((buckets[i].min-pre)>maxGap){
maxGap=buckets[i].min-pre;
}
pre=buckets[i].max;
}
}
return maxGap;
}
//内部类 桶
class Bucket{
int max=0;
int min=0;
boolean hasNum=false;
}
//根据元素的数值计算该元素应该在哪个桶中
public int getBucketIndex(int min,int num,int gap){
return (int)(num-min)/gap;
}
//将元素放入桶种，更新桶的最大值和最小值
public void putInBucket(Bucket[] buckets,int num,int index){
if(buckets[index]==null){
buckets[index]=new Bucket();
buckets[index].hasNum=true;
buckets[index].max=num;
buckets[index].min=num;
}
if(num>buckets[index].max)
buckets[index].max=num;
if(num<buckets[index].min)
buckets[index].min=num;
}
}
