[TOC]
## 算法原理
> 桶排序 (Bucket sort)或所謂的**箱排序**的原理是將數組分到有限數量的桶子里，然后對每個桶子再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序），最后將各個桶中的數據有序的合并起來。
排序過程：
1. 假設待排序的一組數統一的分布在一個范圍中，并將這一范圍劃分成幾個子范圍，也就是桶
2. 將待排序的一組數，分檔規入這些子桶，并將桶中的數據進行排序
3. 將各個桶中的數據有序的合并起來
[Data Structure Visualizations](http://www.cs.usfca.edu/~galles/visualization/BucketSort.html)?提供了一個桶排序的分步動畫演示。
## 實例分析
設有數組 array = [29, 25, 3, 49, 9, 37, 21, 43]，那么數組中最大數為 49，先設置 5 個桶，那么每個桶可存放數的范圍為：0~9、10~19、20~29、30~39、40~49，然后分別將這些數放人自己所屬的桶，如下圖：
[](https://box.kancloud.cn/2015-07-26_55b45a1935ab5.png)
然后，分別對每個桶里面的數進行排序，或者在將數放入桶的同時用插入排序進行排序。最后，將各個桶中的數據有序的合并起來，如下圖：
[](https://box.kancloud.cn/2015-07-26_55b45a31327f9.png)
## JavaScript 語言實現
首先用最笨的方法，每一個桶只能放相同的數字，最大桶的數量為數組中的正數最大值加上負數最小值的絕對值。
~~~
function bucketSort(array) {
var bucket = [], // 正數桶
negativeBucket = [], // 負數桶
result = [],
l = array.length,
i,
j,
k,
abs;
// 入桶
for (i = 0; i < l; i++) {
if (array[i] < 0) {
abs = Math.abs(array[i]);
if (!negativeBucket[abs]) {
negativeBucket[abs] = [];
}
negativeBucket[abs].push(array[i]);
} else {
if (!bucket[array[i]]) {
bucket[array[i]] = [];
}
bucket[array[i]].push(array[i]);
}
}
// 出桶
l = negativeBucket.length;
for (i = l - 1; i >= 0; i--) {
if (negativeBucket[i]) {
k = negativeBucket[i].length;
for (j = 0; j < k; j++) {
result.push(negativeBucket[i][j]);
}
}
}
l = bucket.length;
for (i = 0; i < l; i++) {
if (bucket[i]) {
k = bucket[i].length;
for (j = 0; j < k; j++) {
result.push(bucket[i][j]);
}
}
}
return result;
}
~~~
下面這種方式就是文中舉例分析的那樣，每個桶存放一定范圍的數字，用 step 參數來設置該范圍，取 step 為 1 就退化成前一種實現方式。關鍵部位代碼有注釋，慢慢看，邏輯稍微有點復雜。
~~~
/*
* @array 將要排序的數組
*
* @step 劃分桶的步長，比如 step = 5，表示每個桶存放的數字的范圍是 5，像 -4~1、0~5、6~11
*/
function bucketSort(array, step) {
var result = [],
bucket = [],
bucketCount,
l = array.length,
i,
j,
k,
s,
max = array[0],
min = array[0],
temp;
for (i = 1; i < l; i++) {
if (array[i] > max) {
max = array[i]
}
if (array[i] < min) {
min = array[i];
}
}
min = min - 1;
bucketCount = Math.ceil((max - min) / step); // 需要桶的數量
for (i = 0; i < l; i++) {
temp = array[i];
for (j = 0; j < bucketCount; j++) {
if (temp > (min + step * j) && temp <= (min + step * (j + 1))) { // 判斷放入哪個桶
if (!bucket[j]) {
bucket[j] = [];
}
// 通過插入排序將數字插入到桶中的合適位置
s = bucket[j].length;
if (s > 0) {
for (k = s - 1; k >= 0; k--) {
if (bucket[j][k] > temp) {
bucket[j][k + 1] = bucket[j][k];
} else {
break;
}
}
bucket[j][k + 1] = temp;
} else {
bucket[j].push(temp);
}
}
}
}
for (i = 0; i < bucketCount; i++) { // 循環取出桶中數據
if (bucket[i]) {
k = bucket[i].length;
for (j = 0; j < k; j++) {
result.push(bucket[i][j]);
}
}
}
return result;
}
~~~
## 參考文章
* [維基百科，自由的百科全書](http://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F)
* [Programming Contest Central](https://www-927.ibm.com/ibm/cas/hspc/student/algorithms/BucketSort.html)
* [桶排序（Bucket sort）](http://www.roading.org/algorithm/introductiontoalgorithm/%E7%AC%AC%E5%85%AB%E7%AB%A0%EF%BC%884%EF%BC%89-%E6%A1%B6%E6%8E%92%E5%BA%8F%EF%BC%88bucket-sort%EF%BC%89.html)
* [Data Structure Visualizations](http://www.cs.usfca.edu/~galles/visualization/BucketSort.html)
* [箱排序(Bin Sort)](http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.6.1.1.htm)
