（10）桶排序 (Bucket Sort)

算法原理

桶排序 (Bucket sort)或所謂的箱排序的原理是將數(shù)組分到有限數(shù)量的桶子里，然后對每個(gè)桶子再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序），最后將各個(gè)桶中的數(shù)據(jù)有序的合并起來。

排序過程：

1. 假設(shè)待排序的一組數(shù)統(tǒng)一的分布在一個(gè)范圍中，并將這一范圍劃分成幾個(gè)子范圍，也就是桶
2. 將待排序的一組數(shù)，分檔規(guī)入這些子桶，并將桶中的數(shù)據(jù)進(jìn)行排序
3. 將各個(gè)桶中的數(shù)據(jù)有序的合并起來

Data Structure Visualizations?提供了一個(gè)桶排序的分步動(dòng)畫演示。

實(shí)例分析

設(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ù)有序的合并起來，如下圖：

JavaScript 語言實(shí)現(xiàn)

首先用最笨的方法，每一個(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;
}

參考文章

• 維基百科，自由的百科全書
• Programming Contest Central
• 桶排序（Bucket sort）
• Data Structure Visualizations
• 箱排序(Bin Sort)