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

資訊專欄INFORMATION COLUMN

算法-基數(shù)排序

cucumber / 1157人閱讀

摘要：步驟一以下個位排序，得到。號桶號桶號桶號桶號桶號桶號桶號桶號桶號桶基數(shù)排序生成隨機(jī)數(shù)保留整數(shù)清空數(shù)據(jù)插入數(shù)據(jù)裝換為字符串交換位置從低位開始進(jìn)行排序元素的最高位數(shù)第一輪，取個位第二輪，去十位從頭開始取個人博客鏈接

算法思想

1.定義:基數(shù)排序按照對位數(shù)分組的順序的不同，LSD（從低位開始）和MSD（從高位開始）基數(shù)排序.

2.算法思路（LSD）：

第一：定義長度十位數(shù)組(桶)，存放排好序的數(shù)組；
第二：個位排序，個位大小對應(yīng)桶編號，然后取出；


第三：十位排序，十位大小對應(yīng)桶編號，然后取出；


第四：百位排序，百位大小對應(yīng)桶編號，然后取出，0-1000的排序完成；


3.例子：比較3 0 6 12 12 7 8 12 13 12 8 11 12 4。

步驟一：以下個位排序，得到0 11 12 12 12 12 12 3 13 4 6 7 8 8。

0號桶 [ 0 ]
1號桶 [ 11 ]
2號桶 [ 12, 12, 12, 12, 12 ]
3號桶 [ 3, 13 ]
4號桶 [ 4 ]
5號桶 [ ]
6號桶 [ 6 ]
7號桶 [ 7 ]
8號桶 [ 8, 8 ]
9號桶 [ ]

步驟二：將以上個位排序好的，然后進(jìn)行十位排序，得到0 3 4 6 7 8 8 11 12 12 12 12 12 13。

0號桶 [ 0, 3, 4, 6, 7, 8, 8 ]
1號桶 [ 11, 12, 12, 12, 12, 12, 13 ]
2號桶 [ ]
3號桶 [ ]
4號桶 [ ]
5號桶 [ ]
6號桶 [ ]
7號桶 [ ]
8號桶 [ ]
9號桶 [ ]

/*
 * @Author: yt.gan 
 * @Date: 2018-04-17 09:53:22 
 * @Last Modified by: yt.gan
 * @Last Modified time: 2018-04-17 10:57:14
 */

//基數(shù)排序
function CArray(elements) {
    this.dataStore = [];
    this.pos = 0;
    this.elements = elements;
    for (var i = 0; i < this.elements; ++i) {
        this.dataStore[i] = i;
    }
    this.setData = function() {
        //生成隨機(jī)數(shù)
        //floor保留整數(shù) random [0,1)
        for (var i = 0; i < this.elements; ++i) {
            this.dataStore[i] = Math.floor(Math.random() * (this.elements + 1));
        }
    }

    this.clear = function() {
        //清空數(shù)據(jù)
        for (var i = 0; i < this.dataStore.length; ++i) {
            this.dataStore[i] = 0;
        }
    }

    this.insert = function(element) {
        //插入數(shù)據(jù)
        this.dataStore[this.pos++] = element;
    }

    this.show = function() {
        //裝換為字符串
        var reStr = "";
        for (var i = 0; i < this.dataStore.length; ++i) {
            reStr += this.dataStore[i] + " ";
            if (i > 0 & i % 10 == 0) {
                reStr += "
";
            }
        }
        console.log(reStr);
    }

    this.swap = function(arr, index1, index2) {
        //交換位置
        var temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    this.radix = function(arr, maxBit) {
        //LSD 從低位開始進(jìn)行排序
        //maxBit 元素的最高位數(shù)
        var mod = 10;
        var dev = 1;
        var temp = [];
        for (var i = 0; i < maxBit; i++, dev *= 10, mod *= 10) {
            //第一輪mod=10，dev=1 取個位
            //第二輪mod=100，dev=10 去十位
            for (var j = 0; j < arr.length; j++) {
                var bucket = parseInt((arr[j] % mod) / dev);
                if (temp[bucket] == null) {
                    temp[bucket] = [];
                }
                temp[bucket].push(arr[j]);
            }
            console.log(temp);
            var pos = 0;
            for (var j = 0; j < temp.length; j++) {
                var value = null;
                if (temp[j] != null) {
                    //從頭開始取
                    while ((value = temp[j].shift()) != null) {
                        arr[pos++] = value;
                    }
                }
            }
        }
    }
}

var myNums = new CArray(14);
myNums.setData();
myNums.show();
myNums.radix(myNums.dataStore, 2);
myNums.show();

// 3 0 6 12 12 7 8 12 13 12 8 11 12 4

// [ [ 0 ],
//   [ 11 ],
//   [ 12, 12, 12, 12, 12 ],
//   [ 3, 13 ],
//   [ 4 ],
//   ,
//   [ 6 ],
//   [ 7 ],
//   [ 8, 8 ] ]

// [ [ 0, 3, 4, 6, 7, 8, 8 ],
//   [ 11, 12, 12, 12, 12, 12, 13 ],
//   [],
//   [],
//   [],
//   ,
//   [],
//   [],
//   [] ]

// 0 3 4 6 7 8 8 11 12 12 12 12 12 13

個人博客鏈接

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

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

相關(guān)文章

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

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

    Awbeci 評論0 收藏0

  • 前端 排序算法總結(jié)

    摘要：前言排序算法可能是你學(xué)編程第一個學(xué)習(xí)的算法，還記得冒泡嗎當(dāng)然，排序和查找兩類算法是面試的熱門選項。本篇將會總結(jié)一下，在前端的一些排序算法。函數(shù)的性能相信對于排序算法性能來說，時間復(fù)雜度是至關(guān)重要的一個參考因素。 前言 排序算法可能是你學(xué)編程第一個學(xué)習(xí)的算法，還記得冒泡嗎？ 當(dāng)然，排序和查找兩類算法是面試的熱門選項。如果你是一個會寫快排的程序猿，面試官在比較你和一個連快排都不會寫的人的時...

    happen 評論0 收藏0

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

    摘要：涉及的算法有計數(shù)排序基數(shù)排序桶排序，它們被歸類為非比較排序。計數(shù)排序沒有對元素進(jìn)行比較，只是利用了箱與元素的一一對應(yīng)關(guān)系，根據(jù)箱已經(jīng)排好序的先決條件，解決排序。基數(shù)排序，是按照從高位到低位的順序進(jìn)行分組排序。內(nèi)部排序也是用基數(shù)排序。 一般算法能做到O(logn)，已經(jīng)非常不錯，如果我們排序的對象是純數(shù)字，還可以做到驚人的O(n)。涉及的算法有計數(shù)排序、基數(shù)排序、桶排序，它們被歸類為非比...

    GitChat 評論0 收藏0

  • 排序算法 JavaScript

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

    Charlie_Jade 評論0 收藏0

  • 快速排序js實現(xiàn)

    摘要：然后再分別對基數(shù)左邊和右邊的數(shù)組進(jìn)行相同的操作，直到數(shù)組中只有一個元素時，返回該數(shù)組。 快速排序算法 今天大概講下使用js實現(xiàn)快速排序算法： 快速排序算法的思想類似于二分法，每次都是在數(shù)組中選擇一個基數(shù)（可以是任意一個位置的數(shù)，不過一般選擇中間的數(shù)字或者最左邊的數(shù)字），每一輪結(jié)束后，比該基數(shù)小的數(shù)都位于該基數(shù)的左邊，比該基數(shù)大的數(shù)都位于該基數(shù)的右邊。然后再分別對基數(shù)左邊和右邊的數(shù)組進(jìn)行...

    zhoutk 評論0 收藏0

發(fā)表評論

0條評論

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