桶排序概述與實(shí)現(xiàn)思路
桶排序的思想近乎徹底的分治思想。假設(shè)現(xiàn)在需要對(duì)一百萬(wàn)個(gè)數(shù)進(jìn)行排序。我們可以將其等長(zhǎng)地分到100個(gè)虛擬的“桶”里面，這樣，平均每個(gè)桶只有10000個(gè)數(shù)。如果每個(gè)桶都有序了，則只需要依次輸出為有序序列即可。具體思路是這樣的：
1.將待排數(shù)據(jù)按一個(gè)映射函數(shù)f(x)分為連續(xù)的若干段。理論上最佳的分段方法應(yīng)該使數(shù)據(jù)平均分布；實(shí)際上，通常采用的方法都做不到這一點(diǎn)。顯然，對(duì)于一個(gè)已知輸入范圍在【0，10000】的數(shù)組，最簡(jiǎn)單的分段方法莫過(guò)于x/m這種方法，例如，f(x)=x/100。
“連續(xù)的”這個(gè)條件非常重要，它是后面數(shù)據(jù)按順序輸出的理論保證。
2.分配足夠的桶，按照f(shuō)(x)從數(shù)組起始處向后掃描，并把數(shù)據(jù)放到合適的桶中。對(duì)于上面的例子，如果數(shù)據(jù)有10000個(gè)，則我們需要分配101個(gè)桶（因?yàn)橐紤]邊界條件：f(x)=x/100會(huì)產(chǎn)生【0，100】共101種情況），理想情況下，每個(gè)桶有大約100個(gè)數(shù)據(jù)。
3.對(duì)每個(gè)桶進(jìn)行內(nèi)部排序，例如，使用快速排序。注意，如果數(shù)據(jù)足夠大，這里可以繼續(xù)遞歸使用桶排序，直到數(shù)據(jù)大小降到合適的范圍。
4.按順序從每個(gè)桶輸出數(shù)據(jù)。例如，1號(hào)桶【112，123，145，189】，2號(hào)桶【234，235，250，250】，3號(hào)桶【361】，則輸出序列為【112，123，145，189，234，235，250，250，361】。
代碼實(shí)現(xiàn)：
public void bucketSort(int[] arr) {
// 1.求數(shù)組元素最大值與最小值。利用兩者的差值進(jìn)行分桶
int max = arr[0], min = arr[0];
for (int i = 0; i < arr.length; i++) {
max = (arr[0] > max) ? arr[0] : max;
min = (arr[0] < min) ? arr[0] : min;
}
int bucketNum = (max - min) / arr.length + 1;
// 2.定義一個(gè)存放桶的二維數(shù)組大桶存儲(chǔ)桶的索引值小桶存儲(chǔ)元素
Integer[][] bucketArray = new Integer[bucketNum][arr.length];// Integer初始為null,以與數(shù)字0區(qū)別。
for (int i = 0; i < arr.length; i++) {
int quotient = arr[i] / bucketNum;
for (int j = 0; j < arr.length; j++) {
if (bucketArray[quotient][j] == null) {
bucketArray[quotient][j] = arr[j];
break;
}
}
}
// 小桶排序（可以定義一個(gè)臨界值，當(dāng)小于這臨界值用插入排序，大于用快速排序）
for (int i = 0; i < bucketArray.length; i++) {
// insertion sort
for (int j = 0; j < bucketArray[i].length; j++) {
if (bucketArray[i][j] == null) {
break;
}
int value = bucketArray[i][j];
int position = j;
while (position > 0 && bucketArray[i][position - 1] > value) {
bucketArray[i][position] = bucketArray[i][position - 1];
position--;
}
bucketArray[i][position] = value;
}
}
// 輸出
int index = 0;
for (int i = 0; i < bucketArray.length; i++) {
for (int j = 0; j < bucketArray.length; j++) {
if (bucketArray[i][j] != null) {
arr[index] = bucketArray[i][j];
index++;
} else {
break;
}
}
}
}
實(shí)現(xiàn)難點(diǎn)
上面的代碼并不長(zhǎng)，但是卻不好寫。我在實(shí)現(xiàn)過(guò)程中主要遇到了以下問(wèn)題：
1.最重要的問(wèn)題：如何得知每個(gè)小桶需要多大？
顯然，N個(gè)數(shù)平均分到M個(gè)桶，每個(gè)桶的容量應(yīng)該是N/M，但實(shí)際數(shù)據(jù)不可能這么平均。解決辦法無(wú)非是增加桶的容量。那么，我們應(yīng)該增加到多少？
方案一：設(shè)定一個(gè)固定比例，例如使用10倍于平均的容量。這在很多時(shí)候能夠解決問(wèn)題，但遇到極端數(shù)據(jù)的時(shí)候容易出現(xiàn)問(wèn)題。
方案二：極端增加空間大小，使得每個(gè)桶固定裝一個(gè)數(shù)，這需要限制輸入數(shù)據(jù)不重復(fù)。但是，如果輸入數(shù)據(jù)沒(méi)有范圍限制，我們必須申請(qǐng)Integer.MAX_VALUE字節(jié)數(shù)據(jù)，而這必然會(huì)導(dǎo)致內(nèi)存過(guò)大，引發(fā)Requested array size exceeds VM limit異常。但如果我們知道其數(shù)據(jù)范圍，例如[1,100000]，則是可以接受的方案。并且這樣可以省去排序的步驟，可以達(dá)到線性復(fù)雜度，效率很高。
方案三：也就是示例中的代碼，實(shí)際上性能并不好。它是把每個(gè)小桶都做到和原始數(shù)組一樣大，以犧牲很多空間來(lái)?yè)Q取算法在極限情況下的健壯性。
2.如何克服Java數(shù)組的初始值？
如果是數(shù)值型數(shù)組，在分桶的時(shí)候容易由于創(chuàng)建數(shù)組時(shí)系統(tǒng)賦予的0值而給排序造成混亂，干擾結(jié)果。這里有兩種情況：
A：如果輸入數(shù)據(jù)明確不為零，則所受影響不大。只需要在輸出和排序時(shí)注意判斷，排除0值就行了。
B：如果數(shù)據(jù)可能為零，例如上述代碼，這里的解決辦法是申請(qǐng)Integer數(shù)組。由于系統(tǒng)初始值為null，我們可以更明確地繞開(kāi)0值。
算法性能/復(fù)雜度
桶排序的時(shí)間復(fù)雜度可以從每一步分開(kāi)分析。
1.分桶的過(guò)程，遍歷每個(gè)元素、計(jì)算f(x)，將x放到桶中，共3n次計(jì)算，顯然是O(n)復(fù)雜度；
2.最后輸出也是O(n)復(fù)雜度；
3.關(guān)鍵是小桶內(nèi)排序的過(guò)程：即使使用先進(jìn)的比較排序算法，也不可繞開(kāi)O(n㏒n)的下限。因此，每個(gè)小桶的內(nèi)部復(fù)雜度為n(k㏒k)，總得復(fù)雜度為∑(ki*㏒ki)[i=1...m]，其中m為桶的個(gè)數(shù)，ki為每個(gè)桶的元素?cái)?shù)。盡量減少桶內(nèi)數(shù)據(jù)的數(shù)量是提高效率的唯一辦法(因?yàn)榛诒容^排序的最好平均時(shí)間復(fù)雜度只能達(dá)到O(N*logN)了)。因此，有兩種方法：
1）使用更為平均的劃分，使得不至于某個(gè)小桶的數(shù)據(jù)極多；
2）使用更多的桶，以減少每個(gè)桶數(shù)據(jù)的數(shù)量。極限狀況下，每個(gè)桶只有一個(gè)數(shù)據(jù)，這樣就完全沒(méi)有比較操作。但是，在數(shù)據(jù)極多的情況下，這樣是非常不現(xiàn)實(shí)的，會(huì)造成嚴(yán)重的空間消耗。這時(shí)候就需要權(quán)衡時(shí)空間復(fù)雜度了。
總結(jié)起來(lái)，設(shè)數(shù)據(jù)共有N個(gè)，桶有M個(gè)，則桶排序平均復(fù)雜度為：
O(N)+O(N)+O((N/M)*㏒(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)
最優(yōu)情形下，桶排序的時(shí)間復(fù)雜度為O(n)。
桶排序的空間復(fù)雜度通常是比較高的，額外開(kāi)銷為O(N+M)（因?yàn)橐S護(hù)M個(gè)數(shù)組的引用）。
算法穩(wěn)定性
可以看出，在分桶和從桶依次輸出的過(guò)程是穩(wěn)定的。但是，由于我們?cè)诘?步使用了其他算法，所以，桶排序的穩(wěn)定性依賴于這一步。如果我們使用了快排，顯然，算法是不穩(wěn)定的。
算法適用場(chǎng)景
桶排序在數(shù)據(jù)量非常大，而空間相對(duì)充裕的時(shí)候是很實(shí)用的，可以大大降低算法的運(yùn)算數(shù)量級(jí)。此外，在解決一些特殊問(wèn)題的時(shí)候，桶排序可能會(huì)起到意想不到的結(jié)果
