算法-基数排序

cucumber 发布于2019-08-22 16:25 / 1055人阅读

摘要：步骤一以下个位排序，得到。号桶号桶号桶号桶号桶号桶号桶号桶号桶号桶基数排序生成随机数保留整数清空数据插入数据装换为字符串交换位置从低位开始进行排序元素的最高位数第一轮，取个位第二轮，去十位从头开始取个人博客链接

算法思想

1.定义:基数排序按照对位数分组的顺序的不同，LSD（从低位开始）和MSD（从高位开始）基数排序.

2.算法思路（LSD）：

第一：定义长度十位数组(桶)，存放排好序的数组；

第二：个位排序，个位大小对应桶编号，然后取出；

第三：十位排序，十位大小对应桶编号，然后取出；

第四：百位排序，百位大小对应桶编号，然后取出，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号桶 [ ]

步骤二：将以上个位排序好的，然后进行十位排序，得到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
 */

//基数排序
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() {
        //生成随机数
        //floor保留整数 random [0,1)
        for (var i = 0; i < this.elements; ++i) {
            this.dataStore[i] = Math.floor(Math.random() * (this.elements + 1));
        }
    }

    this.clear = function() {
        //清空数据
        for (var i = 0; i < this.dataStore.length; ++i) {
            this.dataStore[i] = 0;
        }
    }

    this.insert = function(element) {
        //插入数据
        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 从低位开始进行排序
        //maxBit 元素的最高位数
        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

个人博客链接

GPU服务器海外云主机基数排序 opencl基数排序基数排序当数据量很大的时候代码最大基数匹配算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/94343.html

JavaScript 数据结构与算法之美 - 桶排序、计数排序、基数排序

摘要：之所以把计数排序桶排序基数排序放在一起比较，是因为它们的平均时间复杂度都为。动画计数排序思想找出待排序的数组中最大和最小的元素。桶排序计数排序能派上用场吗手机号码有位，范围太大，显然不适合用这两种排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言算法为王。想学好前端，先练好内功，只有内功深厚者...

Awbeci 2019-08-26 10:24 评论0 收藏0
前端排序算法总结

摘要：前言排序算法可能是你学编程第一个学习的算法，还记得冒泡吗当然，排序和查找两类算法是面试的热门选项。本篇将会总结一下，在前端的一些排序算法。函数的性能相信对于排序算法性能来说，时间复杂度是至关重要的一个参考因素。前言排序算法可能是你学编程第一个学习的算法，还记得冒泡吗？当然，排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿，面试官在比较你和一个连快排都不会写的人的时...

happen 2019-08-21 16:40 评论0 收藏0
计数排序，桶排序与基数排序

摘要：涉及的算法有计数排序基数排序桶排序，它们被归类为非比较排序。计数排序没有对元素进行比较，只是利用了箱与元素的一一对应关系，根据箱已经排好序的先决条件，解决排序。基数排序，是按照从高位到低位的顺序进行分组排序。内部排序也是用基数排序。一般算法能做到O(logn)，已经非常不错，如果我们排序的对象是纯数字，还可以做到惊人的O(n)。涉及的算法有计数排序、基数排序、桶排序，它们被归类为非比...

GitChat 2019-08-22 13:56 评论0 收藏0
排序算法 JavaScript

摘要：一冒泡排序算法介绍比较相邻的两个元素如果前一个比后一个大，则交换位置。它与冒泡排序的不同之处在于，它会优先比较距离较远的元素。希尔排序的核心在于间隔序列的设定。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。一、冒泡排序算法介绍：比较相邻的两个元素,如果前一个比后一个大，则交换位置。第一轮把最大的元素放到了最后面。由于每次排序最后一个都是最大的，...

Charlie_Jade 2019-08-23 15:18 评论0 收藏0
快速排序js实现

摘要：然后再分别对基数左边和右边的数组进行相同的操作，直到数组中只有一个元素时，返回该数组。快速排序算法今天大概讲下使用js实现快速排序算法：快速排序算法的思想类似于二分法，每次都是在数组中选择一个基数（可以是任意一个位置的数，不过一般选择中间的数字或者最左边的数字），每一轮结束后，比该基数小的数都位于该基数的左边，比该基数大的数都位于该基数的右边。然后再分别对基数左边和右边的数组进行...

zhoutk 2019-08-22 16:22 评论0 收藏0