国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

計數排序,桶排序與基數排序

GitChat / 3325人閱讀

摘要:涉及的算法有計數排序基數排序桶排序,它們被歸類為非比較排序。計數排序沒有對元素進行比較,只是利用了箱與元素的一一對應關系,根據箱已經排好序的先決條件,解決排序?;鶖蹬判颍前凑諒母呶坏降臀坏捻樞蜻M行分組排序。內部排序也是用基數排序。

一般算法能做到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歲一組,然后組內再排序。這樣效率就大大提高了。桶排序也是于這種思想。

操作步驟:

確認范圍,亦即求取原數組的最大值與最小值。

確認需要多少個桶(這個通常作為參數傳入,不能大于原數組長度),然后最大值減最小值,除以桶的數量,但得每個桶最多能放多個元素,我們稱這個數為桶的最大容量。

遍歷原數組的所有元素,除以這個最大容量,就能得到它要放入的桶的編號了。在放入時可以使用插入排序,也可以在合并時才使用快速排序。

對所有桶進行遍歷,如果桶內的元素已經排好序,直接一個個取出來,放到結果數組就行了。

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

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/92652.html

相關文章

  • JavaScript 數據結構算法之美 - 排序、計數排序、基數排序

    摘要:之所以把計數排序桶排序基數排序放在一起比較,是因為它們的平均時間復雜度都為。動畫計數排序思想找出待排序的數組中最大和最小的元素。桶排序計數排序能派上用場嗎手機號碼有位,范圍太大,顯然不適合用這兩種排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言 算法為王。 想學好前端,先練好內功,只有內功深厚者...

    Awbeci 評論0 收藏0
  • 用JS寫計數排序、基數排序

    摘要:計數排序計數排序就是簡單的桶排序,一個桶代表數組中一個數出現的個數,所以需要一個和數組數字范圍一樣大的輔助數組,一般用在范圍小于的排序,時間復雜度為,空間復雜度為數組的數字范圍。 計數排序 計數排序就是簡單的桶排序,一個桶代表數組中一個數出現的個數,所以需要一個和數組數字范圍一樣大的輔助數組,一般用在范圍小于100的排序,時間復雜度為O(n),空間復雜度為數組的數字范圍。 /** *...

    tulayang 評論0 收藏0
  • JavaScript 數據結構算法之美 - 十大經典排序算法匯總

    摘要:筆者寫的數據結構與算法之美系列用的語言是,旨在入門數據結構與算法和方便以后復習。這應該是目前較為簡單的十大經典排序算法的文章講解了吧。比如原本在的前面,而,排序之后,在的后面十大經典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數據。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法為王。想學好前端,先練好內功,內功不行,就...

    zsy888 評論0 收藏0
  • 排序算法 JavaScript

    摘要:一冒泡排序算法介紹比較相鄰的兩個元素如果前一個比后一個大,則交換位置。它與冒泡排序的不同之處在于,它會優先比較距離較遠的元素。希爾排序的核心在于間隔序列的設定。作為一種線性時間復雜度的排序,計數排序要求輸入的數據必須是有確定范圍的整數。 一、冒泡排序 算法介紹: 比較相鄰的兩個元素,如果前一個比后一個大,則交換位置。 第一輪把最大的元素放到了最后面。 由于每次排序最后一個都是最大的,...

    Charlie_Jade 評論0 收藏0
  • 數據結構以及相關排序

    摘要:桶排序與計數排序的區別桶排序中一個桶可以放一個范圍內的多個數據,在各個桶中又可以用其他方法排序,其快速之處在于只用對比同一個桶內的數字而無需與其他桶的數字作對比。與計數排序相比,桶排序需要作二次對比,但可省略桶的個數。 哈希表(Hash Table) 所有符合鍵值對即key-value的結構就是哈希。數組其實也是一種哈希。 計數排序(復雜度(n+max))無法統計負數和小數,需要一個...

    Brenner 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<