摘要：桶排序方法一每個桶只放相同的數(shù)字入桶過程把正數(shù)和存入正數(shù)桶，把負(fù)數(shù)存入負(fù)數(shù)桶把數(shù)組中的每項(xiàng)作為正數(shù)桶或負(fù)數(shù)桶的下標(biāo)存入到對應(yīng)的里出桶過程先遍歷正數(shù)桶或負(fù)數(shù)桶，因?yàn)橥袄锩宽?xiàng)都是數(shù)組，在遍歷每項(xiàng)正數(shù)桶負(fù)數(shù)桶最終結(jié)果負(fù)數(shù)的絕對值存儲正數(shù)桶或負(fù)數(shù)桶

方法一：每個桶只放相同的數(shù)字
入桶過程：
1、 把正數(shù)和0存入正數(shù)桶，把負(fù)數(shù)存入負(fù)數(shù)桶；
2、 把數(shù)組中的每項(xiàng)作為正數(shù)桶或負(fù)數(shù)桶的下標(biāo)存入到對應(yīng)的key里；

出桶過程：
先遍歷正數(shù)桶或負(fù)數(shù)桶，因?yàn)橥袄锩宽?xiàng)都是數(shù)組，在遍歷每項(xiàng)

function bucketSort(array){
    var bucket = [],    //正數(shù)桶
          negativeBucket = [],    //負(fù)數(shù)桶
          result = [],    //最終結(jié)果
          abs,    //負(fù)數(shù)的絕對值
        k    //存儲正數(shù)桶或負(fù)數(shù)桶每項(xiàng)的length
    
    //入桶
    for(var i = 0; i < array.length; 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])
        }
    }
    
    //出桶
    var l = negativeBucket.length
    for(var i = l - 1; i >= 0; i --){    //遍歷負(fù)數(shù)桶，和正數(shù)桶正好相反
        if(negativeBucket[i]){
            k = negativeBucket[i].length
            for(var j = 0; j < k; j++){
                result.push(negativeBucket[i][j])
            }
        }
    }

    for(var i = 0; i < bucket.length; i++){ //遍歷正數(shù)桶
        if(bucket[i]){
            k = bucket[i].length
            for(var j = 0; j < k; j++){
                result.push(bucket[i][j])
            }
        }
    }
    return result
}
var a = [1,23,5,6,7,-6,-9,-11,0,-1,-55,-4,7,4,1,222,3,7]
bucketSort(a)

方法二：每個桶放一個范圍的數(shù)

    function bucketSort(array, step) {
        var result = [],    //存儲最終結(jié)果
            bucket = [],    //要用到的桶的數(shù)組
            bucketCount,    //桶的數(shù)量
            l = array.length,
            i,
            j,
            k,
            s,
            max = array[0],//最大數(shù)
            min = array[0],//最小數(shù)
            temp;

        //找出 array 中最大數(shù)和最小數(shù)
        for (i = 1; i < l; i++) {
            if (array[i] > max) {
                max = array[i]
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
        min = min - 1;  //如果 array 中有 4 個數(shù)，定義每個桶放 2 個數(shù)，那只要 2 個桶就夠了，最后結(jié)果會少一個數(shù)，最小數(shù)上 -1，需要的桶就會變成 3 個
        bucketCount = Math.ceil((max - min) / step); // 需要桶的數(shù)量，和 bucket.length相等
        console.log(bucketCount)

        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))) { // 判斷放入哪個桶
               
                /*
                | j | min + step * j | min + step * (j + 1) |
                | 0 |       -2       |          0           |
                | 1 |        0       |          2           |
                | 2 |        2       |          4           |
                temp 取值 3,-1,0
                j 取值 0,1,2
                當(dāng) i = 0 時,temp = 3,只有 j = 2 能進(jìn)來;
                當(dāng) i = 1 時,temp = -1,只有 j = 0 能進(jìn)來;
                當(dāng) i = 2 時,temp = 0,只有 j = 0 能進(jìn)來
                */

                    //bucket 是桶的數(shù)組，把每個桶變成數(shù)組
                    //這里 j 的取值順序是 2、1、0，取到的值是 2、0、0
                    if (!bucket[j]) {
                        bucket[j] = [];
                    }
                    
                    // 通過插入排序?qū)?shù)字插入到桶中的合適位置
                    s = bucket[j].length;   //前兩次 s 是 0，第三次 s 為 1

                    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;    //這里 j 取值 0，也就是說放入第一個桶，k + 1 往后放
                    }else if(s <= 0) {    //前兩次走這邊 bucket 中 key 為 0,2有值了
                        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;
    }

    var a = [-3,-1,0]
    bucketSort(a)

排序過程：準(zhǔn)備 0-9 號十個桶
第一次循環(huán)：
入桶：按個位數(shù)排序，依次放入0-9號桶內(nèi)
出桶：從 0 號桶依次開始，按先入先出的方式出桶
第二次循環(huán)
入桶：按十位數(shù)排序，依次放入0-9號桶內(nèi)，位數(shù)不夠的補(bǔ) 0
出桶：從 0 號桶依次開始，按先入先出的方式出桶
第三次按百位排序... 第四次按千位排序...
直到全部排完

function radixSort(array){
    var bucket = [],
        i,
        max = array[0];

    for(i = 1; i < array.length; i++){
        if(array[i] > max){
            max = array[i]
        }
    }

    for(i = 0; i < 10; i++){
        bucket[i] = []
    }

    var loop = (max + "").length
    for(i = 0; i < loop; i++){
        for(j = 0; j < array.length;j++){
            var str = array[j] + ""
            if(str.length >= i + 1){
                var k = str[str.length - i - 1] //找出對應(yīng)位數(shù)，比如 345 這個數(shù)，第1次找出個位 5，第2次找出十位數(shù) 4，第3次找出百位數(shù) 3
                bucket[k].push(array[j])
            }else{
                bucket[0].push(array[j])
            }
        }
        array.splice(0,array.length)    //清空數(shù)組
        for(j = 0; j < 10; j++){
            var t = bucket[j].length
            for(var g = 0; g < t; g++){
                array.push(bucket[j][g])
            }
            bucket[j] = []      //清空桶
        }
    }
    return array
}
a=[22,3,33,2,1,777]
radixSort(a)