在我的博客冒泡排序稿黄、插入排序喊衫、快速排序、堆排序杆怕、歸并排序總結(jié)中介紹了幾種經(jīng)典的排序方法族购，其中快速排序、堆排序和歸并排序的平均時間復(fù)雜度都是nlog(n)陵珍。下面我將會介紹另一種經(jīng)典的排序算法寝杖，平均時間復(fù)雜度可以達到o(n)，但是有幾個限制條件互纯，我們來看一下瑟幕。
桶排序
首先我們來了解一下桶排序的思想。桶排序是體現(xiàn)了分治的思想留潦。原理是創(chuàng)建若干個桶只盹，通過某種映射將待排序的元素放置到桶中，使每個桶中的最大值都小于他后面一個桶的最小值兔院，并且每個桶容納的元素數(shù)量盡可能平均殖卑。然后對每個桶中的元素排序。最后將所有桶中的元素依次輸出坊萝。
下面兩副圖很好的解釋了桶排序的思想孵稽。
有幾個關(guān)鍵的因素影響了桶排序的時間復(fù)雜度和空間復(fù)雜度
1.待排序元素的分布情況
如果我們要對{1，2屹堰，3肛冶，4，5扯键，90}進行排序睦袖，假設(shè)桶的個數(shù)就是元素的個數(shù)，那么會出現(xiàn)第一個桶有5個元素荣刑，中間的桶都是空的馅笙，最后一個桶有一個元素。這樣厉亏，時間復(fù)雜度就退化成nlog(n)董习。
2.桶的個數(shù)
桶的個數(shù)越多，每個桶中的數(shù)量就越少爱只，每個桶內(nèi)進行排序的時間復(fù)雜度就約低皿淋。當(dāng)桶的個數(shù)滿足每個桶只裝一個元素時，桶排序所消耗的主要在為每個元素分配桶上面，為o(n)窝趣。
桶排序代碼實現(xià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; //排除異常桶個數(shù)
Bucket[] buckets = new Bucket[myBucketNum]; //創(chuàng)建桶
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++) { //遍歷每個元素疯暑，將元素分配到對應(yīng)桶中
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++) { //將所有桶中的數(shù)據(jù)合并
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分配到桶中，并使用插入排序?qū)ν皟?nèi)元素進行排序
* @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;
}
/**
* 鏈表結(jié)點
* @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]);
}
}
}
時間復(fù)雜度分析
在桶排序中哑舒，我們首先遍歷所有元素妇拯，找出來最大值和最小值，這個操作的時間復(fù)雜度是o(n)洗鸵。
然后我們遍歷每個元素越锈，將元素分配到對應(yīng)的桶中，并將桶內(nèi)元素排序膘滨。假設(shè)元素總個數(shù)是N甘凭，桶的個數(shù)是M，元素都平均分布（最好情況）吏祸，使用nlog(n)的排序方法對每個桶內(nèi)元素進行排序对蒲，這個操作時間復(fù)雜度是M(N/M)log(N/M)；當(dāng)M==N是贡翘，這個操作的時間復(fù)雜度是o(n)蹈矮。
最后我們遍歷所有元素，得到最終結(jié)果鸣驱，時間復(fù)雜度是o(n)泛鸟。
因此最好情況下的時間復(fù)雜度是o(n)。
但是當(dāng)元素分布極不均勻的情況下踊东，時間復(fù)雜度退化成nlog(n)北滥。
空間復(fù)雜度：
使用了鏈表來保存中間結(jié)果，空間復(fù)雜度是o(n)
（LeetCode） -164 最大間距
了解了桶排序的思想闸翅，我們來看一下下面一道題再芋，也是用桶排序的思想來解決的。
給定一個無序的數(shù)組坚冀，找出數(shù)組在排序之后济赎，相鄰元素之間最大的差值。
如果數(shù)組元素個數(shù)小于 2记某，則返回 0司训。
示例 1:
輸入: [3,6,9,1]
輸出: 3
解釋: 排序后的數(shù)組是 [1,3,6,9], 其中相鄰元素 (3,6) 和 (6,9) 之間都存在最大差值 3。
示例 2:
輸入: [10]
輸出: 0
解釋: 數(shù)組元素個數(shù)小于 2液南，因此返回 0壳猜。
說明:
你可以假設(shè)數(shù)組中所有元素都是非負整數(shù)，且數(shù)值在 32 位有符號整數(shù)范圍內(nèi)滑凉。
請嘗試在線性時間復(fù)雜度和空間復(fù)雜度的條件下解決此問題统扳。
解題思路
題目要求在線性時間復(fù)雜度和空間復(fù)雜度的前提下找到相鄰元素的最大差喘帚。
我們可以先對元素進行排序，為了達到線性時間復(fù)雜度闪幽，我們采用桶排序（也可以使用計數(shù)排序啥辨，不過使用桶排序在該題中空間復(fù)雜度更小）盯腌。
我們可以很巧妙地設(shè)置每個桶的大小：假設(shè)所有元素的最大值為max,最小值為min陨瘩，元素個數(shù)是n腕够，則最大間距將不小于Math.ceil((max-min)/(n-1))。因此舌劳，我們設(shè)置桶的容量是Math.ceil((max-min)/(n-1))帚湘，則桶內(nèi)的元素的間距肯定不是最大間距，我們只需要查看桶間的間距（前一個桶的最大值和后一個桶的最小值的差）的最大值即可甚淡。
此外大诸，在桶內(nèi)并不需要保存每個元素，只需要保存該桶的最大值和最小值即可贯卦。
有了上面的思路资柔，我們可以寫出來下面的代碼
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++){ //遍歷每個元素撵割，計算該元素應(yīng)該放置的桶的位置贿堰，將元素放入桶中，更新桶的最大值和最小值
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;
}
//內(nèi)部類 桶
class Bucket{
int max=0;
int min=0;
boolean hasNum=false;
}
//根據(jù)元素的數(shù)值計算該元素應(yīng)該在哪個桶中
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;
}
}
