計(jì)數(shù)排序，桶排序與基數(shù)排序

GitChat 發(fā)布于2019-08-22 13:56 / 3332人閱讀

摘要：涉及的算法有計(jì)數(shù)排序基數(shù)排序桶排序，它們被歸類為非比較排序。計(jì)數(shù)排序沒(méi)有對(duì)元素進(jìn)行比較，只是利用了箱與元素的一一對(duì)應(yīng)關(guān)系，根據(jù)箱已經(jīng)排好序的先決條件，解決排序。基數(shù)排序，是按照從高位到低位的順序進(jìn)行分組排序。內(nèi)部排序也是用基數(shù)排序。

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

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

非比較排序時(shí)間復(fù)雜度低，但由于非比較排序需要占用空間來(lái)確定唯一位置。所以對(duì)數(shù)據(jù)規(guī)模和數(shù)據(jù)分布有一定的要求。

計(jì)數(shù)排序

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

我們看一下計(jì)數(shù)排序是怎么運(yùn)作，假設(shè)我們有[1,2,3,1,0,4]這六個(gè)數(shù)，這里面最大的值為4，那么我們創(chuàng)建一個(gè)長(zhǎng)度為4的數(shù)組，每個(gè)元素默認(rèn)為0。這相當(dāng)于選舉排序，一共有6個(gè)投票箱，1就投1號(hào)箱，0就投入0號(hào)箱。注意，這些箱本來(lái)就是已經(jīng)排好序，并且箱的編號(hào)就是代表原數(shù)組的元素。當(dāng)全部投完時(shí)，0號(hào)箱有1個(gè)，1號(hào)箱有2個(gè)，2號(hào)箱有1個(gè)，3號(hào)箱有1，4號(hào)箱有1個(gè)。然后我們從這些箱的所有數(shù)依次出來(lái)，放到新數(shù)組，就神奇地排好序了。

計(jì)數(shù)排序沒(méi)有對(duì)元素進(jìn)行比較，只是利用了箱與元素的一一對(duì)應(yīng)關(guān)系，根據(jù)箱已經(jīng)排好序的先決條件，解決排序。

//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]){//子桶里不實(shí)際存在
         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
}

但數(shù)組有一個(gè)問(wèn)題就是它的索引值是從0開(kāi)始，但我們的元素也要大于或等于0。我們可以通過(guò)一個(gè)數(shù)學(xué)技巧讓它支持負(fù)數(shù)。

//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 ]++     //減去最小值，確保索引大于負(fù)數(shù)
   }
   var index = 0, bucketCount = max-min+1
   for(var i = 0; i < bucketCount; i++){
       var m = buckets[i].length;
       while(m){
        //將桶的編號(hào)加上最小值，變回原來(lái)的元素
        arr[index] = i+min;
        index++
        m--
       }
   }
   return arr
}

桶排序

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

操作步驟：

確認(rèn)范圍，亦即求取原數(shù)組的最大值與最小值。

確認(rèn)需要多少個(gè)桶（這個(gè)通常作為參數(shù)傳入，不能大于原數(shù)組長(zhǎng)度），然后最大值減最小值，除以桶的數(shù)量，但得每個(gè)桶最多能放多個(gè)元素，我們稱這個(gè)數(shù)為桶的最大容量。

遍歷原數(shù)組的所有元素，除以這個(gè)最大容量，就能得到它要放入的桶的編號(hào)了。在放入時(shí)可以使用插入排序，也可以在合并時(shí)才使用快速排序。

對(duì)所有桶進(jìn)行遍歷，如果桶內(nèi)的元素已經(jīng)排好序，直接一個(gè)個(gè)取出來(lái)，放到結(jié)果數(shù)組就行了。

//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可能是負(fù)數(shù)
      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占據(jù)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 ]

基數(shù)排序

基數(shù)排序是一種非比較型的整數(shù)排序算法。其基本原理是，按照整數(shù)的每個(gè)位數(shù)分組。在分組過(guò)程中，對(duì)于不足位的數(shù)據(jù)用0補(bǔ)位。

基數(shù)排序按照對(duì)位數(shù)分組的順序的不同，可以分為L(zhǎng)SD（Least significant digit）基數(shù)排序和MSD（Most significant digit）基數(shù)排序。

LSD基數(shù)排序，是按照從低位到高位的順序進(jìn)行分組排序。MSD基數(shù)排序，是按照從高位到低位的順序進(jìn)行分組排序。上述兩種方式不僅僅是對(duì)位數(shù)分組順序不同，其實(shí)現(xiàn)原理也是不同的。

LSD基數(shù)排序

對(duì)于序列中的每個(gè)整數(shù)的每一位都可以看成是一個(gè)桶，而該位上的數(shù)字就可以認(rèn)為是這個(gè)桶的鍵值。比如下面數(shù)組

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

首先我們要確認(rèn)最大值，一個(gè)for循環(huán)得最大數(shù)，因?yàn)樽畲髷?shù)的位數(shù)最長(zhǎng)。

然后，建立10個(gè)桶，亦即10個(gè)數(shù)組。

然后再遍歷所有元素，取其個(gè)位數(shù)，個(gè)位數(shù)是什么就放進(jìn)對(duì)應(yīng)編號(hào)的數(shù)組，1放進(jìn)1號(hào)桶。

 0號(hào)桶： 170，90
 1號(hào)桶： 無(wú)
 2號(hào)桶： 802，2
 3號(hào)桶： 無(wú)
 4號(hào)桶： 24
 5號(hào)桶： 45， 75
 6號(hào)桶： 66
 7－9號(hào)桶： 無(wú)

然后再依次將元素從桶里最出來(lái)，覆蓋原數(shù)組，或放到一個(gè)新數(shù)組，我們把這個(gè)經(jīng)過(guò)第一次排序的數(shù)組叫sorted。

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

然后我們?cè)僖淮伪闅vsorted數(shù)組的元素，這次取十位的值。這時(shí)要注意，2不存在十位，那么默認(rèn)為0

 0號(hào)桶： 2，802
 1號(hào)桶： 無(wú)
 2號(hào)桶： 24
 3號(hào)桶： 無(wú)
 4號(hào)桶： 45
 5號(hào)桶： 無(wú)
 6號(hào)桶： 66
 7號(hào)桶： 170， 75
 8號(hào)桶： 無(wú)
 9號(hào)桶： 90

再全部取出來(lái)

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

開(kāi)始百位上的入桶操作，沒(méi)有百位就默認(rèn)為0：

 0號(hào)桶： 2，24，45，66，75，90
 1號(hào)桶： 170
 2－7號(hào)桶：無(wú)
 8號(hào)桶： 802
 9號(hào)桶： 無(wú)

再全部取出來(lái)

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

沒(méi)有千位數(shù)，那么循環(huán)結(jié)束，返回結(jié)果桶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個(gè)桶
    }
    for (var radix = 1; radix <= times; radix++) {
        //個(gè)位，十位，百位，千位這樣循環(huán)
        lsdRadixSort(array, buckets, len, radix);
    }
    return array;
}
// 根據(jù)數(shù)字某個(gè)位數(shù)上的值得到桶的編號(hào)
function getBucketNumer(num, d) {
    return (num + "").reverse()[d];
}
//或者這個(gè)
function getBucketNumer(num, i) {
    return Math.floor((num / Math.pow(10, i)) % 10);
}
//獲取數(shù)字的位數(shù)
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;
    //重寫(xiě)原桶
    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基數(shù)排序

接下來(lái)講MSD基數(shù)排序.

最開(kāi)始時(shí)也是遍歷所有元素，取最大值，得到最大位數(shù)，建立10個(gè)桶。這時(shí)從百位取起。不足三位，對(duì)應(yīng)位置為0.

 0號(hào)桶： 45, 75, 90, 2, 24, 66
 1號(hào)桶： 107
 2-7號(hào)桶： 無(wú)
 8號(hào)桶： 802
 9號(hào)桶： 無(wú)

接下來(lái)就與LSD不一樣。我們對(duì)每個(gè)長(zhǎng)度大于1的桶進(jìn)行內(nèi)部排序。內(nèi)部排序也是用基數(shù)排序。我們需要建立另10個(gè)桶，對(duì)0號(hào)桶的元素進(jìn)行入桶操作，這時(shí)比原來(lái)少一位，亦即十位。

 0號(hào)桶： 2
 1號(hào)桶： 無(wú)
 2號(hào)桶： 24
 3號(hào)桶： 無(wú)
 4號(hào)桶： 45
 5號(hào)桶： 無(wú)
 6號(hào)桶： 66
 7號(hào)桶： 75
 8號(hào)桶： 無(wú)
 9號(hào)桶： 90

然后繼續(xù)遞歸上一步，因此每個(gè)桶的長(zhǎng)度，都沒(méi)有超過(guò)1，于是開(kāi)始0號(hào)桶的收集工作：

 0號(hào)桶： 2，24，45，66，75，90
 1號(hào)桶： 107
 2-7號(hào)桶： 無(wú)
 8號(hào)桶： 802
 9號(hào)桶： 無(wú)

將這步驟應(yīng)用其他桶，最后就排序完畢。

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

//或者這個(gè)
function getBucketNumer(num, i) {
    return Math.floor((num / Math.pow(10, i)) % 10);
}
//獲取數(shù)字的位數(shù)
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;
    //重寫(xiě)原桶
    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);

字符串使用基數(shù)排序?qū)崿F(xiàn)字典排序

此外，基數(shù)排序不局限于數(shù)字，可以稍作變換，就能應(yīng)用于字符串的字典排序中。我們先來(lái)一個(gè)簡(jiǎn)單的例子，只對(duì)都是小寫(xiě)字母的字符串?dāng)?shù)組進(jìn)行排序。

小寫(xiě)字母一共26個(gè)，考慮到長(zhǎng)度不一樣的情況，我們需要對(duì)夠短的字符串進(jìn)行補(bǔ)充，這時(shí)補(bǔ)上什么好呢？我們不能直接上0，而是補(bǔ)空白。然后根據(jù)字母與數(shù)字的對(duì)應(yīng)關(guān)系，弄27個(gè)桶，空字符串對(duì)應(yīng)0，a對(duì)應(yīng)1，b對(duì)應(yīng)2.... 字典排序是從左邊開(kāi)始比較，因此我們需要用到MST基數(shù)排序。

//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;

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

    //將字符串轉(zhuǎn)換為數(shù)字?jǐn)?shù)組
    var nums = [];
    for (let i = 0; i < len; i++) {
        nums.push(toNum(array[i], loopTimes));
    }
    //開(kāi)始多關(guān)鍵字排序
    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是用來(lái)識(shí)別是桶還是我們臨時(shí)創(chuàng)建的數(shù)字字符串
        if (el.length > 1 && !el.c && radix < radixs) {
            msdRadixSort(el, el.length, radix + 1, radixs);
        }
    }
    var k = 0;
    //重寫(xiě)原桶
    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...

云服務(wù)器 GPU云服務(wù)器基數(shù)排序桶排序 opencl基數(shù)排序桶排序算法

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/92652.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

GitChat

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

tensorflow庫(kù)

閱讀 2714·2023-04-25 14:59
#黑五# contabo：NVMe VPS終身5折，適用于VPS/VDS/獨(dú)服，此外免&#8

閱讀 909·2021-11-22 11:59
【算法】插入排序——希爾排序+直接插入排序

閱讀 649·2021-11-17 09:33
基于Springboot實(shí)現(xiàn)疫情社區(qū)人口管理系統(tǒng)

閱讀 2478·2021-09-27 13:34
全球知名ssl證書(shū)品牌推薦：Symantec、DigiCert、Comodo、GeoTrust、Th

閱讀 3914·2021-09-09 11:55
vue動(dòng)畫(huà)筆記

閱讀 2333·2019-08-30 15:44
[翻譯]CSS變量讓你輕松制作響應(yīng)式網(wǎng)頁(yè)

閱讀 1136·2019-08-30 14:06
圖解一下啥是CSS堆疊上下文，啥是CSS堆疊層疊順序，讓你對(duì)css的疑惑少一點(diǎn)?

閱讀 1935·2019-08-29 16:55

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

計(jì)數(shù)排序，桶排序與基數(shù)排序

相關(guān)文章

**JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 桶排序、計(jì)數(shù)排序、基數(shù)排序**

**用JS寫(xiě)計(jì)數(shù)排序、基數(shù)排序**

JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 十大經(jīng)典排序算法匯總

排序算法 JavaScript

數(shù)據(jù)結(jié)構(gòu)以及相關(guān)排序

發(fā)表評(píng)論

0條評(píng)論

GitChat

男|高級(jí)講師

TA的文章

tensorflow庫(kù)

#黑五# contabo：NVMe VPS終身5折，適用于VPS/VDS/獨(dú)服，此外免&#8

【算法】插入排序——希爾排序+直接插入排序

基于Springboot實(shí)現(xiàn)疫情社區(qū)人口管理系統(tǒng)

全球知名ssl證書(shū)品牌推薦：Symantec、DigiCert、Comodo、GeoTrust、Th

vue動(dòng)畫(huà)筆記

[翻譯]CSS變量讓你輕松制作響應(yīng)式網(wǎng)頁(yè)

圖解一下啥是CSS堆疊上下文，啥是CSS堆疊層疊順序，讓你對(duì)css的疑惑少一點(diǎn)?

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

計(jì)數(shù)排序，桶排序與基數(shù)排序

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

計(jì)數(shù)排序，桶排序與基數(shù)排序