资讯专栏INFORMATION COLUMN

桶排序和基数排序

xiaochao / 3339人阅读

摘要:桶排序方法一每个桶只放相同的数字入桶过程把正数和存入正数桶,把负数存入负数桶把数组中的每项作为正数桶或负数桶的下标存入到对应的里出桶过程先遍历正数桶或负数桶,因为桶里每项都是数组,在遍历每项正数桶负数桶最终结果负数的绝对值存储正数桶或负数桶

桶排序:

方法一:每个桶只放相同的数字
入桶过程:
1、 把正数和0存入正数桶,把负数存入负数桶;
2、 把数组中的每项作为正数桶或负数桶的下标存入到对应的key里;

出桶过程:
先遍历正数桶或负数桶,因为桶里每项都是数组,在遍历每项

function bucketSort(array){
    var bucket = [],    //正数桶
          negativeBucket = [],    //负数桶
          result = [],    //最终结果
          abs,    //负数的绝对值
        k    //存储正数桶或负数桶每项的length
    
    //入桶
    for(var i = 0; i < array.length; i++){
        if(array[i] < 0){
            abs = Math.abs(array[i])          
            if(!negativeBucket[abs]){
                negativeBucket[abs] = []
            }
            negativeBucket[abs].push(array[i])
        }else{
              if(!bucket[array[i]]){
                bucket[array[i]] = []
              }
              bucket[array[i]].push(array[i])
        }
    }
    
    //出桶
    var l = negativeBucket.length
    for(var i = l - 1; i >= 0; i --){    //遍历负数桶,和正数桶正好相反
        if(negativeBucket[i]){
            k = negativeBucket[i].length
            for(var j = 0; j < k; j++){
                result.push(negativeBucket[i][j])
            }
        }
    }

    for(var i = 0; i < bucket.length; i++){ //遍历正数桶
        if(bucket[i]){
            k = bucket[i].length
            for(var j = 0; j < k; j++){
                result.push(bucket[i][j])
            }
        }
    }
    return result
}
var a = [1,23,5,6,7,-6,-9,-11,0,-1,-55,-4,7,4,1,222,3,7]
bucketSort(a)

方法二:每个桶放一个范围的数

    function bucketSort(array, step) {
        var result = [],    //存储最终结果
            bucket = [],    //要用到的桶的数组
            bucketCount,    //桶的数量
            l = array.length,
            i,
            j,
            k,
            s,
            max = array[0],//最大数
            min = array[0],//最小数
            temp;

        //找出 array 中最大数和最小数
        for (i = 1; i < l; i++) {
            if (array[i] > max) {
                max = array[i]
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
        min = min - 1;  //如果 array 中有 4 个数,定义每个桶放 2 个数,那只要 2 个桶就够了,最后结果会少一个数,最小数上 -1,需要的桶就会变成 3 个
        bucketCount = Math.ceil((max - min) / step); // 需要桶的数量,和 bucket.length相等
        console.log(bucketCount)

        for (i = 0; i < l; i++) {
            temp = array[i];
            for (j = 0; j < bucketCount; j++) {

                if (temp > (min + step * j) && temp <= (min + step * (j + 1))) { // 判断放入哪个桶
               
                /*
                | j | min + step * j | min + step * (j + 1) |
                | 0 |       -2       |          0           |
                | 1 |        0       |          2           |
                | 2 |        2       |          4           |
                temp 取值 3,-1,0
                j 取值 0,1,2
                当 i = 0 时,temp = 3,只有 j = 2 能进来;
                当 i = 1 时,temp = -1,只有 j = 0 能进来;
                当 i = 2 时,temp = 0,只有 j = 0 能进来
                */

                    //bucket 是桶的数组,把每个桶变成数组
                    //这里 j 的取值顺序是 2、1、0,取到的值是 2、0、0
                    if (!bucket[j]) {
                        bucket[j] = [];
                    }
                    
                    // 通过插入排序将数字插入到桶中的合适位置
                    s = bucket[j].length;   //前两次 s 是 0,第三次 s 为 1

                    if (s > 0) {    //第三次走这边
                        for (k = s - 1; k >= 0; k--) {
                            if (bucket[j][k] > temp) {
                                bucket[j][k + 1] = bucket[j][k];
                            } else {
                                break;
                            }
                        }
                        bucket[j][k + 1] = temp;    //这里 j 取值 0,也就是说放入第一个桶,k + 1 往后放
                    }else if(s <= 0) {    //前两次走这边 bucket 中 key 为 0,2有值了
                        bucket[j].push(temp);
                    }
                }
            }
        }
        for (i = 0; i < bucketCount; i++) { // 循环取出桶中数据
            if (bucket[i]) {
                k = bucket[i].length;
                for (j = 0; j < k; j++) {
                    result.push(bucket[i][j]);
                }
            }
        }
        return result;
    }

    var a = [-3,-1,0]
    bucketSort(a)
基数排序

排序过程:准备 0-9 号十个桶
第一次循环:
入桶:按个位数排序,依次放入0-9号桶内
出桶:从 0 号桶依次开始,按先入先出的方式出桶
第二次循环
入桶:按十位数排序,依次放入0-9号桶内,位数不够的补 0
出桶:从 0 号桶依次开始,按先入先出的方式出桶
第三次按百位排序... 第四次按千位排序...
直到全部排完

function radixSort(array){
    var bucket = [],
        i,
        max = array[0];

    for(i = 1; i < array.length; i++){
        if(array[i] > max){
            max = array[i]
        }
    }

    for(i = 0; i < 10; i++){
        bucket[i] = []
    }

    var loop = (max + "").length
    for(i = 0; i < loop; i++){
        for(j = 0; j < array.length;j++){
            var str = array[j] + ""
            if(str.length >= i + 1){
                var k = str[str.length - i - 1] //找出对应位数,比如 345 这个数,第1次找出个位 5,第2次找出十位数 4,第3次找出百位数 3
                bucket[k].push(array[j])
            }else{
                bucket[0].push(array[j])
            }
        }
        array.splice(0,array.length)    //清空数组
        for(j = 0; j < 10; j++){
            var t = bucket[j].length
            for(var g = 0; g < t; g++){
                array.push(bucket[j][g])
            }
            bucket[j] = []      //清空桶
        }
    }
    return array
}
a=[22,3,33,2,1,777]
radixSort(a)

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

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

相关文章

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

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

    Awbeci 评论0 收藏0
  • 计数排序排序基数排序

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

    GitChat 评论0 收藏0
  • 基数排序就这么简单

    摘要:一基数排序桶排序介绍来源百科基数排序属于分配式排序,又称桶子法或,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些桶中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为,其中为所采取的基数,而为堆数,在某些时候,基 一、基数排序(桶排序)介绍 来源360百科: 基数排序(radix sort)属于分配式排序(distribution sort),又称桶子法(b...

    plokmju88 评论0 收藏0
  • 用JS写计数排序基数排序

    摘要:计数排序计数排序就是简单的桶排序,一个桶代表数组中一个数出现的个数,所以需要一个和数组数字范围一样大的辅助数组,一般用在范围小于的排序,时间复杂度为,空间复杂度为数组的数字范围。 计数排序 计数排序就是简单的桶排序,一个桶代表数组中一个数出现的个数,所以需要一个和数组数字范围一样大的辅助数组,一般用在范围小于100的排序,时间复杂度为O(n),空间复杂度为数组的数字范围。 /** *...

    tulayang 评论0 收藏0
  • 排序算法 JavaScript

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

    Charlie_Jade 评论0 收藏0

发表评论

0条评论

xiaochao

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<