成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

算法-基數(shù)排序

cucumber / 1196人閱讀

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

算法思想

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

2.算法思路（LSD）：

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


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


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


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

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

0號(hào)桶 [ 0 ]
1號(hào)桶 [ 11 ]
2號(hào)桶 [ 12, 12, 12, 12, 12 ]
3號(hào)桶 [ 3, 13 ]
4號(hào)桶 [ 4 ]
5號(hào)桶 [ ]
6號(hào)桶 [ 6 ]
7號(hào)桶 [ 7 ]
8號(hào)桶 [ 8, 8 ]
9號(hào)桶 [ ]

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

0號(hào)桶 [ 0, 3, 4, 6, 7, 8, 8 ]
1號(hào)桶 [ 11, 12, 12, 12, 12, 12, 13 ]
2號(hào)桶 [ ]
3號(hào)桶 [ ]
4號(hào)桶 [ ]
5號(hào)桶 [ ]
6號(hào)桶 [ ]
7號(hào)桶 [ ]
8號(hào)桶 [ ]
9號(hào)桶 [ ]

/*
 * @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 取個(gè)位
            //第二輪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

個(gè)人博客鏈接

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/94343.html

相關(guān)文章

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

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

    Awbeci 評(píng)論0 收藏0

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

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

    happen 評(píng)論0 收藏0

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

    摘要：涉及的算法有計(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ù)排序、桶排序，它們被歸類為非比...

    GitChat 評(píng)論0 收藏0

  • 排序算法 JavaScript

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

    Charlie_Jade 評(píng)論0 收藏0

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

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

    zhoutk 評(píng)論0 收藏0

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

0條評(píng)論

閱讀需要支付1元查看
<