計數排序，桶排序與基數排序

一般算法能做到O(logn)，已經非常不錯，如果我們排序的對象是純數字，還可以做到驚人的O(n)。涉及的算法有計數排序、基數排序、桶排序，它們被歸類為非比較排序。

非比較排序只要確定每個元素之前的已有的元素個數即可，遍歷一次就能求解。算法時間復雜度O(n)。

非比較排序時間復雜度低，但由于非比較排序需要占用空間來確定唯一位置。所以對數據規模和數據分布有一定的要求。

計數排序

計數排序需要占用大量空間，它僅適用于數據比較集中的情況。比如 [0~100]，[10000~19999] 這樣的數據。

我們看一下計數排序是怎么運作，假設我們有[1,2,3,1,0,4]這六個數，這里面最大的值為4，那么我們創建一個長度為4的數組，每個元素默認為0。這相當于選舉排序，一共有6個投票箱，1就投1號箱，0就投入0號箱。注意，這些箱本來就是已經排好序，并且箱的編號就是代表原數組的元素。當全部投完時，0號箱有1個，1號箱有2個，2號箱有1個，3號箱有1，4號箱有1個。然后我們從這些箱的所有數依次出來，放到新數組，就神奇地排好序了。

計數排序沒有對元素進行比較，只是利用了箱與元素的一一對應關系，根據箱已經排好序的先決條件，解決排序。

//by 司徒正美
function countSort(arr){
   var max = Math.max.apply(0, arr);
   var buckets = []
   for(var i = 0; i < n; i++){
      var el = arr[i]
      if(buckets[el]){//子桶里不實際存在
         buckets[el]++ 
      }else{
         buckets[el] = 1
      }
   }
   var index = 0
   for(var i = 0; i < n; i++){
       var m = buckets[i].length;
       while(m){
          arr[index] = i;
          index++
          m--
       }
   }
   return arr
}

但數組有一個問題就是它的索引值是從0開始，但我們的元素也要大于或等于0。我們可以通過一個數學技巧讓它支持負數。

//by 司徒正美
function countSort(arr){
   var max = arr[0]
   var min = arr[0]
   for(var i = 0; i < n; i++){
      if(arr[i] > max){
         max = arr[i]
      }
      if(arr[i] < min){
         max = arr[i]
      }
   }

   var buckets = new Array(max-min+1).fill(0);
   for(var i = 0; i < n; i++){
      buckets[ arr[i]-min ]++     //減去最小值，確保索引大于負數
   }
   var index = 0, bucketCount = max-min+1
   for(var i = 0; i < bucketCount; i++){
       var m = buckets[i].length;
       while(m){
        //將桶的編號加上最小值，變回原來的元素
        arr[index] = i+min;
        index++
        m--
       }
   }
   return arr
}

桶排序

桶排序與計數排序很相似，不過現在的桶不單計數，是實實在在地放入元素。舉個例子，學校要對所有老師按年齡進行排序，這么多老師很難操作，那么先讓他們按年齡段進行分組，20－30歲的一組，30－40歲一組，50－60歲一組，然后組內再排序。這樣效率就大大提高了。桶排序也是于這種思想。

操作步驟：

1. 確認范圍，亦即求取原數組的最大值與最小值。
2. 確認需要多少個桶（這個通常作為參數傳入，不能大于原數組長度），然后最大值減最小值，除以桶的數量，但得每個桶最多能放多個元素，我們稱這個數為桶的最大容量。
3. 遍歷原數組的所有元素，除以這個最大容量，就能得到它要放入的桶的編號了。在放入時可以使用插入排序，也可以在合并時才使用快速排序。
4. 對所有桶進行遍歷，如果桶內的元素已經排好序，直接一個個取出來，放到結果數組就行了。

//by 司徒正美
var arr = [2,5,3,0,2,8,0,3,4,3]
   function bucketSort(array, num){
    if(array.length <= 1){
      return array
    }
    var n = array.length;
    var min = Math.min.apply(0, array)
    var max = Math.max.apply(0, array)
    if(max === min){
       return array
    }
    var capacity = (max - min + 1) /num;
    var buckets = new Array(max - min + 1)
    for(var i = 0; i < n; i++){
      var el = array[i];//el可能是負數
      var index = Math.floor((el - min) / capacity)
      var bucket = buckets[index]
      if(bucket){
         var jn = bucket.length;
         if(el >= bucket[jn-1]){
            bucket[jn] = el
         }else{
            insertSort: 
            for(var j = 0; j < jn; j++){
                if(bucket[j] > el){
                    while(jn > j){ //全部向后挪一位
                        bucket[jn] = bucket[jn-1]
                        jn--
                    }
                    bucket[j] = el //讓el占據bucket[j]的位置
                    break insertSort;
                }
            }
         }
      }else{
         buckets[index] = [el]
      }
    }
    var index = 0
    for(var i = 0; i < num; i++){
        var bucket = buckets[i]
        for(var k = 0, kn = bucket.length; k < kn; k++){
            array[index++] = bucket[k]
        }
    }
    return array;
 }
 console.log(  bucketSort(arr,4) )
 //[ 0, 0, 2, 2, 3, 3, 3, 4, 5, 8 ]

基數排序

基數排序是一種非比較型的整數排序算法。其基本原理是，按照整數的每個位數分組。在分組過程中，對于不足位的數據用0補位。

基數排序按照對位數分組的順序的不同，可以分為LSD（Least significant digit）基數排序和MSD（Most significant digit）基數排序。

LSD基數排序，是按照從低位到高位的順序進行分組排序。MSD基數排序，是按照從高位到低位的順序進行分組排序。上述兩種方式不僅僅是對位數分組順序不同，其實現原理也是不同的。

LSD基數排序

對于序列中的每個整數的每一位都可以看成是一個桶，而該位上的數字就可以認為是這個桶的鍵值。比如下面數組

[170, 45, 75, 90, 802, 2, 24, 66]

首先我們要確認最大值，一個for循環得最大數，因為最大數的位數最長。

然后，建立10個桶，亦即10個數組。

然后再遍歷所有元素，取其個位數，個位數是什么就放進對應編號的數組，1放進1號桶。

0號桶： 170，90
 1號桶： 無
 2號桶： 802，2
 3號桶： 無
 4號桶： 24
 5號桶： 45， 75
 6號桶： 66
 7－9號桶： 無

然后再依次將元素從桶里最出來，覆蓋原數組，或放到一個新數組，我們把這個經過第一次排序的數組叫sorted。

sorted = [170,90,802,2,24,45,75,66]

然后我們再一次遍歷sorted數組的元素，這次取十位的值。這時要注意，2不存在十位，那么默認為0

0號桶： 2，802
 1號桶： 無
 2號桶： 24
 3號桶： 無
 4號桶： 45
 5號桶： 無
 6號桶： 66
 7號桶： 170， 75
 8號桶： 無
 9號桶： 90

再全部取出來

sorted = [2，802,24，45，66，170，75，90]

開始百位上的入桶操作，沒有百位就默認為0：

0號桶： 2，24，45，66，75，90
 1號桶： 170
 2－7號桶：無
 8號桶： 802
 9號桶： 無

再全部取出來

sorted = [2，24，45，66，75，90，170，802]

沒有千位數，那么循環結束，返回結果桶sorted

從程序描述如下：

//by 司徒正美
function radixSort(array) {
    var max = Math.max.apply(0, array);
    var times = getLoopTimes(max),
        len = array.length;
    var buckets = [];
    for (let i = 0; i < 10; i++) {
        buckets[i] = []; //初始化10個桶
    }
    for (var radix = 1; radix <= times; radix++) {
        //個位，十位，百位，千位這樣循環
        lsdRadixSort(array, buckets, len, radix);
    }
    return array;
}
// 根據數字某個位數上的值得到桶的編號
function getBucketNumer(num, d) {
    return (num + "").reverse()[d];
}
//或者這個
function getBucketNumer(num, i) {
    return Math.floor((num / Math.pow(10, i)) % 10);
}
//獲取數字的位數
function getLoopTimes(num) {
    var digits = 0;
    do {
        if (num > 1) {
            digits++;
        } else {
            break;
        }
    } while ((num = num / 10));
    return digits;
}
function lsdRadixSort(array, buckets, len, radix) {
    //入桶
    for (let i = 0; i < len; i++) {
        let el = array[i];
        let index = getBucketNumer(el, radix);
        buckets[index].push(el);
    }
    var k = 0;
    //重寫原桶
    for (let i = 0; i < 10; i++) {
        let bucket = buckets[i];
        for (let j = 0; j < bucket.length; j++) {
            array[k++] = bucket[j];
        }
        bucket.length = 0;
    }
}
// test
var arr = [278, 109, 63, 930, 589, 184, 505, 269, 8, 83];
console.log(radixSort(arr));

MSD基數排序

接下來講MSD基數排序.

最開始時也是遍歷所有元素，取最大值，得到最大位數，建立10個桶。這時從百位取起。不足三位，對應位置為0.

0號桶： 45, 75, 90, 2, 24, 66
 1號桶： 107
 2-7號桶： 無
 8號桶： 802
 9號桶： 無

接下來就與LSD不一樣。我們對每個長度大于1的桶進行內部排序。內部排序也是用基數排序。我們需要建立另10個桶，對0號桶的元素進行入桶操作，這時比原來少一位，亦即十位。

0號桶： 2
 1號桶： 無
 2號桶： 24
 3號桶： 無
 4號桶： 45
 5號桶： 無
 6號桶： 66
 7號桶： 75
 8號桶： 無
 9號桶： 90

然后繼續遞歸上一步，因此每個桶的長度，都沒有超過1，于是開始0號桶的收集工作：

0號桶： 2，24，45，66，75，90
 1號桶： 107
 2-7號桶： 無
 8號桶： 802
 9號桶： 無

將這步驟應用其他桶，最后就排序完畢。

//by 司徒正美
function radixSort(array) {
    var max = Math.max.apply(0, array),
        times = getLoopTimes(max),
        len = array.length;
    msdRadixSort(array, len, times);
    return array;
}

//或者這個
function getBucketNumer(num, i) {
    return Math.floor((num / Math.pow(10, i)) % 10);
}
//獲取數字的位數
function getLoopTimes(num) {
    var digits = 0;
    do {
        if (num > 1) {
            digits++;
        } else {
            break;
        }
    } while ((num = num / 10));
    return digits;
}
function msdRadixSort(array, len, radix) {
    var buckets = [[], [], [], [], [], [], [], [], [], []];
    //入桶
    for (let i = 0; i < len; i++) {
        let el = array[i];
        let index = getBucketNumer(el, radix);
        buckets[index].push(el);
    }
    //遞歸子桶
    for (let i = 0; i < 10; i++) {
        let el = buckets[i];
        if (el.length > 1 && radix - 1) {
            msdRadixSort(el, el.length, radix - 1);
        }
    }
    var k = 0;
    //重寫原桶
    for (let i = 0; i < 10; i++) {
        let bucket = buckets[i];
        for (let j = 0; j < bucket.length; j++) {
            array[k++] = bucket[j];
        }
        bucket.length = 0;
    }
}
var arr = radixSort([170, 45, 75, 90, 802, 2, 24, 66]);
console.log(arr);

字符串使用基數排序實現字典排序

此外，基數排序不局限于數字，可以稍作變換，就能應用于字符串的字典排序中。我們先來一個簡單的例子，只對都是小寫字母的字符串數組進行排序。

小寫字母一共26個，考慮到長度不一樣的情況，我們需要對夠短的字 符串進行補充，這時補上什么好呢？我們不直接被0，然后補空白。然后根據字母與數字的對應關系，弄27個桶，空字符串對應0，a對應1，b對應2.... 字典排序是從左邊開始比較， 因此我們需要用到MST基數排序。

//by 司徒正美
var character = {};
"abcdefghijklmnopqrstuvwxyz".split("").forEach(function(el, i) {
    character[el] = i + 1;
});
function toNum(c, length) {
    var arr = [];
    arr.c = c;
    for (var i = 0; i < length; i++) {
        arr[i] = character[c[i]] || 0;
    }
    return arr;
}
function getBucketNumer(arr, i) {
    return arr[i];
}

function radixSort(array) {
    var len = array.length;
    var loopTimes = 0;

    //求出最長的字符串，并得它的長度，那也是最高位
    for (let i = 0; i < len; i++) {
        let el = array[i];
        var charLen = el.length;
        if (charLen > loopTimes) {
            loopTimes = charLen;
        }
    }

    //將字符串轉換為數字數組
    var nums = [];
    for (let i = 0; i < len; i++) {
        nums.push(toNum(array[i], loopTimes));
    }
    //開始多關鍵字排序
    msdRadixSort(nums, len, 0, loopTimes);
    //變回字符串
    for (let i = 0; i < len; i++) {
        array[i] = nums[i].c;
    }
    return array;
}

function msdRadixSort(array, len, radix, radixs) {
    var buckets = [];
    for (var i = 0; i <= 26; i++) {
        buckets[i] = [];
    }
    //入桶
    for (let i = 0; i < len; i++) {
        let el = array[i];
        let index = getBucketNumer(el, radix);
        buckets[index].push(el);
    }
    //遞歸子桶
    for (let i = 0; i <= 26; i++) {
        let el = buckets[i];
        //el.c是用來識別是桶還是我們臨時創建的數字字符串
        if (el.length > 1 && !el.c && radix < radixs) {
            msdRadixSort(el, el.length, radix + 1, radixs);
        }
    }
    var k = 0;
    //重寫原桶
    for (let i = 0; i <= 26; i++) {
        let bucket = buckets[i];
        for (let j = 0; j < bucket.length; j++) {
            array[k++] = bucket[j];
        }
        bucket.length = 0;
    }
}
var array = ["ac", "ee", "ef", "b", "z", "f", "ep", "gaaa", "azh", "az", "r"];

var a = radixSort(array);
console.log(a);

參考鏈接

• https://wenku.baidu.com/view/... (PPT)
• https://www.cnblogs.com/kkun/...
• http://blog.csdn.net/ltyqljhw...

 

來自：https://segmentfault.com/a/1190000012923917