桶排序 (Bucket sort)或所謂的箱排序的原理是將數(shù)組分到有限數(shù)量的桶子里,然后對每個(gè)桶子再分別排序(有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序),最后將各個(gè)桶中的數(shù)據(jù)有序的合并起來。
排序過程:
Data Structure Visualizations?提供了一個(gè)桶排序的分步動(dòng)畫演示。
設(shè)有數(shù)組 array = [29, 25, 3, 49, 9, 37, 21, 43],那么數(shù)組中最大數(shù)為 49,先設(shè)置 5 個(gè)桶,那么每個(gè)桶可存放數(shù)的范圍為:0~9、10~19、20~29、30~39、40~49,然后分別將這些數(shù)放人自己所屬的桶,如下圖:
然后,分別對每個(gè)桶里面的數(shù)進(jìn)行排序,或者在將數(shù)放入桶的同時(shí)用插入排序進(jìn)行排序。最后,將各個(gè)桶中的數(shù)據(jù)有序的合并起來,如下圖:
首先用最笨的方法,每一個(gè)桶只能放相同的數(shù)字,最大桶的數(shù)量為數(shù)組中的正數(shù)最大值加上負(fù)數(shù)最小值的絕對值。
function bucketSort(array) {
var bucket = [], // 正數(shù)桶
negativeBucket = [], // 負(fù)數(shù)桶
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;
}
下面這種方式就是文中舉例分析的那樣,每個(gè)桶存放一定范圍的數(shù)字,用 step 參數(shù)來設(shè)置該范圍,取 step 為 1 就退化成前一種實(shí)現(xiàn)方式。關(guān)鍵部位代碼有注釋,慢慢看,邏輯稍微有點(diǎn)復(fù)雜。
/*
* @array 將要排序的數(shù)組
*
* @step 劃分桶的步長,比如 step = 5,表示每個(gè)桶存放的數(shù)字的范圍是 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); // 需要桶的數(shù)量
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))) { // 判斷放入哪個(gè)桶
if (!bucket[j]) {
bucket[j] = [];
}
// 通過插入排序?qū)?shù)字插入到桶中的合適位置
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++) { // 循環(huán)取出桶中數(shù)據(jù)
if (bucket[i]) {
k = bucket[i].length;
for (j = 0; j < k; j++) {
result.push(bucket[i][j]);
}
}
}
return result;
}
更多建議: