桶排序 订阅
桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。 展开全文
桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
信息
领    域
计算机算法
要    求
数据的长度必须完全一样
公    式
Data=rand()/10000+10000
原    理
桶排序利用函数的映射关系
中文名
桶排序
性    质
平均情况下桶排序以线性时间运行
数据结构设计
链表可以采用很多种方式实现
桶排序定义
假定:输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间(桶),每桶大小1/n:[0, 1/n), [1/n, 2/n), [2/n, 3/n),…,[k/n, (k+1)/n ),…将n个输入元素分配到这些桶中,对桶中元素进行排序,然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组,指向桶(链表)。
收起全文
精华内容
下载资源
问答
  • 桶排序的利用的是数组的下标可以自动排序 var arr = []; //arr[乱序下标] = 随意数组 arr[5] = 1; arr[2] = 1; arr[3] = 1; arr[9] = 1; arr[10] = 1; //无论放入的顺序是什么,数组的排序都是不会乱的 console.log...
  • 主要介绍了C语言实现桶排序的方法,简单描述了桶排序的概念、原理并结合实例形式分析了C语言实现桶排序算法的具体操作技巧,需要的朋友可以参考下
  • 一、桶排序: 排序一个数组[5,3,6,1,2,7,5,10] 值都在1-10之间,建立10个桶: [0 0 0 0 0 0 0 0 0 0] 桶 [1 2 3 4 5 6 7 8 9 10] 桶代表的值 遍历数组,第一个数字5,第五个桶加1 [0 0 0 0 1 0 0 0 0 0] 第二个数字...
  • 桶排序 桶排序(Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一...
  • 博客《数据结构与算法 —— 排序算法(3)》中的桶排序的时间复杂度计算公式推到过程。
  • 桶排序(Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种...
  • 桶排序C语言实现

    2017-06-03 21:58:42
    用C语言实现桶排序,已测试运行。
  • 数组应用之桶排序课件,用于信息学奥赛基础算法上课应用。课件内容讲解了桶排序的基本思想,问题应用,知识扩展及多维桶等。
  • 本文实例讲述了JS桶排序的简单理解与实现方法。分享给大家供大家参考,具体如下: 桶排序,利用编号分组存储数字,再利用编号合并分组的一种算法排序。 举个易于理解的例子: 一组数字,9,3,4,0,2,8,5,1,7,6,11,10,...
  • 本文实例讲述了Python实现桶排序与快速排序算法结合应用的方法。分享给大家供大家参考,具体如下: #-*- coding: UTF-8 -*- import numpy as np from QuickSort import QuickSort def BucketSort(a, n): barrel = ...
  • PHP实现桶排序算法

    2020-10-18 19:58:59
    主要为大家详细介绍了PHP实现桶排序算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • Erlang 百万级用户排行榜桶排序,在百万级用户中,高效精确查找当前人物所在排名。
  • 主要介绍了Python实现的桶排序算法,简单说明了桶排序的概念、原理及优缺点,并结合实例形式演示了Python实现桶排序的方法,需要的朋友可以参考下
  • 主要介绍了java 实现计数排序和桶排序实例代码的相关资料,需要的朋友可以参考下
  • 在排序元素很多的情况下,其实桶排序的性能并不是太高,这里我们配合单链表的直接插入排序,来看下一大数据情况下桶排序算法的运用与C++代码实现示例:
  • 桶排序算法顾名思义,就是把要排序的元素分桶排序后合并结果,这里我们就来看一下桶排序算法的理解及C语言版代码示例:
  • 基数排序/桶排序 *统计将数组中的数字分配到桶中后,各个桶中的数字个数 *数组中每个数的每一位数根据大小分配到对应大小为0~9的桶 *将各个桶中的数字个数,转化成各个桶中最后一个数字的下标索引
  • 桶排序

    千次阅读 2019-09-14 20:28:16
    桶排序是计数排序的扩展版本,计数排序可以看成每个桶只存储相同元素,而桶排序每个桶存储一定范围的元素,通过映射函数,将待排序数组中的元素映射到各个对应的桶中,对每个桶中的元素进行排序,最后将非空桶中的...

    一、思想
    一句话总结:划分多个范围相同的区间,每个自区间自排序,最后合并。

    桶排序是计数排序的扩展版本,计数排序可以看成每个桶只存储相同元素,而桶排序每个桶存储一定范围的元素,通过映射函数,将待排序数组中的元素映射到各个对应的桶中,对每个桶中的元素进行排序,最后将非空桶中的元素逐个放入原序列中。

    桶排序需要尽量保证元素分散均匀,否则当所有数据集中在同一个桶中时,桶排序失效。

    二、图解过程

    三、核心代码 

    public static void bucketSort(int[] arr){
        
        // 计算最大值与最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length; i++){
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        
        // 计算桶的数量
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i = 0; i < bucketNum; i++){
            bucketArr.add(new ArrayList<Integer>());
        }
        
        // 将每个元素放入桶
        for(int i = 0; i < arr.length; i++){
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }
        
        // 对每个桶进行排序
        for(int i = 0; i < bucketArr.size(); i++){
            Collections.sort(bucketArr.get(i));
        }
        
        // 将桶中的元素赋值到原序列
    	int index = 0;
    	for(int i = 0; i < bucketArr.size(); i++){
    		for(int j = 0; j < bucketArr.get(i).size(); j++){
    			arr[index++] = bucketArr.get(i).get(j);
    		}
    	}  
    }
    

     

    四、复杂度分析


    1. 时间复杂度:O(N + C)
    对于待排序序列大小为 N,共分为 M 个桶,主要步骤有:

    N 次循环,将每个元素装入对应的桶中
    M 次循环,对每个桶中的数据进行排序(平均每个桶有 N/M 个元素)
    一般使用较为快速的排序算法,时间复杂度为 O(NlogN) O(NlogN)O(NlogN),实际的桶排序过程是以链表形式插入的。

    整个桶排序的时间复杂度为:

    O(N)+O(M∗(N/M∗log(N/M)))=O(N∗(log(N/M)+1)) O(N)+O(M*(N/M*log(N/M)))=O(N*(log(N/M)+1))O(N)+O(M∗(N/M∗log(N/M)))=O(N∗(log(N/M)+1))

    当 N = M 时,复杂度为 O(N) O(N)O(N)

    2. 额外空间复杂度:O(N + M)


    五、稳定性分析


    桶排序的稳定性取决于桶内排序使用的算法。
     

     

    展开全文
  • Go语言桶排序算法

    2018-01-20 15:25:33
    go桶排序,比较简单地用Go语言完成桶排序,算法都是很基本的,所以就不必赘述了,希望大家对go感兴趣,也希望我的文档对大家有帮助!
  • c++简单代码桶排序

    2020-08-26 15:30:14
    c++桶排序的代码,当初我学排序的时候也用了一些时间才想通,所以,如果一时想不通的话也别放弃,要一直坚持下去。
  • 桶排序是将要排序的算法按桶分组排序之后再遍历汇总的一种线性排序算法,下面就让我们来通过小例子简单掌握桶排序算法及C++版的代码实现^^
  • 桶排序Radix Sort算法利用分治思想将元素分入各桶中排序后汇总,以下我们就来深入解析桶排序算法及Node.js上JavaScript的代码实现,需要的朋友可以参考下
  • 利用Pthread多线程工具 实现桶排序的并行化,并在linux下调试通过。
  • 这是桶排序可视化原理。以具体的例子来说明。希望能够更直观的了解什么叫桶排序。视频中描述得很简单,可能也不是很直观。有不懂的可以相互交流、学习。
  • 【排序算法】图解桶排序

    千次阅读 多人点赞 2020-07-29 11:13:08
    前言 在数据结构与算法的排序中,我们很多人可能更多的...可能对堆排序、桶排序、计数排数等比较生疏,其实这个也没啥复杂的,桶排序是所有排序中最简单的排序之一。 没毛病老铁,就是最简单的之一。 桶排序思想 ...

    前言

    在数据结构与算法的排序中,我们很多人可能更多的熟悉冒泡排序、快速排序、归并排序。可能对堆排序、桶排序、计数排数等比较生疏,其实这个也没啥复杂的,桶排序是所有排序中最简单的排序之一。 没毛病老铁,就是最简单的之一。 并且桶排序和计数排序基数排序有很多相似和渊源之处。后面会进行对比分析记得先关注!
    在这里插入图片描述

    桶排序思想

    其实桶排序重要的是它的思想,而不是具体实现,桶排序从字面的意思上看:

    • 桶:若干个桶,说明此类排序将数据放入若干个桶中。
    • 桶:每个桶有容量,桶是有一定容积的容器,所以每个桶中可能有多个元素。
    • 桶:从整体来看,整个排序更希望桶能够更匀称,即既不溢出(太多)又不太少。
      在这里插入图片描述

    但是这些桶跟排序又有什么关系呢?
    首先先说下桶排序的思想,百度百科是这么说的

    工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。

    用通俗易懂的话来理解:

    • 将待排序的序列分到若干个桶中,每个桶内的元素再进行个别排序。
    • 时间复杂度最好可能是线性O(n),桶排序不是基于比较的排序

    当然,桶排序是一种用空间换取时间的排序。

    既然是排序,那么最终的结果肯定是从小到大的,桶排序借助桶的位置完成一次初步的排序——将待排序元素分别放至各个桶内。

    而我们通常根据待排序元素整除的方法将其较为均匀的放至桶中,如8 5 22 15 28 9 45 42 39 19 27 47 12这个待排序序列,假设放入桶编号的规则为:n/10。这样首先各个元素就可以直接通过整除的方法放至对应桶中。而右侧所有桶内数据都比左侧的要大!

    在这里插入图片描述

    在刚刚放入桶中的时候,各个桶的大小相对可以确定,右侧都比左侧大,但桶内还是无序的,对各个桶内分别进行排序,再依次按照桶的顺序、桶内序列顺序得到一个最终排序的序列。
    在这里插入图片描述

    以上就是桶排序在算法上的思想了。如果使用java具体实现的话思路也很简单:用List[]类型的集合数组表示桶,每个List代表一个桶,将数据根据整除得到的值直接放到对应编号的集合里面去,再依次进行排序就可以了。

    桶排序算法分析

    上面讲了桶排序的具体思想,但是你是不是总觉得心理没那么踏实呢,这就完了?总觉得怪怪的是吧?

    在这里插入图片描述
    桶排序确实有很多不一样的地方,无论是算法时间复杂度还是整个算法的流程,都不如啥快排啦、归并啦这些传统排序来的实在。

    时间复杂度分析

    桶排序的时间复杂度到底是多少?

    我们假设有n个待排序数字。分到m个桶中,如果分配均匀这样平均每个桶有n/m个元素。首先在这里我郑重说明一下桶排序的算法时间复杂度有两部分组成:

    • 1.遍历处理每个元素,O(n)级别的普通遍历
    • 2.每个桶内再次排序的时间复杂度总和

    对于第一个部分,我想大家都应该理解最后排好序的取值遍历一趟的O(n);而第二部分咱们可以进行这样的分析:

    • 如果桶内元素分配较为均匀假设每个桶内部使用的排序算法为快速排序,那么每个桶内的时间复杂度为(n/m) log(n/m)。有m个桶,那么时间复杂度为m * (n/m)log(n/m)=n (log n-log m).
      在这里插入图片描述
      所以最终桶排序的时间复杂度为:O(n)+O(n*(log n- log m))=O(n+n*(log n -log m)) 其中m为桶的个数。我们有时也会写成O(n+c),其中c=n*(log n -log m);

    在这里如果到达极限情况n=m时。就能确保避免桶内排序,将数值放到桶中不需要再排序达到O(n)的排序效果,当然这种情况属于计数排序,后面再详解计数排序记得再回顾。
    在这里插入图片描述

    桶排序适用情况

    桶排序并且像常规排序那样没有限制,桶排序有相当的限制。因为桶的个数和大小都是我们人为设置的。而每个桶又要避免空桶的情况。所以我们在使用桶排序的时候即需要对待排序数列要求偏均匀,又要要求桶的设计兼顾效率和空间。

    待排序序列要求均匀?我要不均匀又会怎么样呢?
    会这样:
    在这里插入图片描述
    这样其实相当于只用了有效的很少个数桶,而再看桶排序的时间复杂度:O(n+n*(log n -log m))m取向1,log m去向0.整个复杂度变成O(n+nlogn)从级别来看就是O(nlogn),你瞅瞅你瞅瞅,这种情况就跟没用桶一样,就是快排(或其他排序)的时间复杂度。

    那,那不能我搞100000个桶嘛?
    不可以,真的不可以,如果100000个桶,你看看会造成什么情况:
    在这里插入图片描述
    这才短短不到100个数,你为了一一映射用100000个空间,空间内容浪费不说,你遍历虽然O(n)也是100000次也比100个的O(nlogn)大上很多啊,真是折了夫人又折兵。

    所以现在明白前面说的话了吧:数要相对均匀分布,桶的个数也要合理设计。总之桶排序是一种用空间换取时间的排序。在设计桶排序,你需要知道输入数据的上界和下界,看看数据的分布情况,再考虑是否用桶排序,当然如果能用好桶排序,效率还是很高的!

    实现一个桶排序

    在这里用java给大家实现一个桶排序。假设序列为:1 8 7 44 42 46 38 34 33 17 15 16 27 28 24;我们选用5个桶进行桶排序。

    import java.util.ArrayList;
    import java.util.List;
    //微信公众号:bigsai
    public class test3 {
    	public static void main(String[] args) {
    		int a[]= {1,8,7,44,42,46,38,34,33,17,15,16,27,28,24};
    		List[] buckets=new ArrayList[5];
    		for(int i=0;i<buckets.length;i++)//初始化
    		{
    			buckets[i]=new ArrayList<Integer>();
    		}
    		for(int i=0;i<a.length;i++)//将待排序序列放入对应桶中
    		{
    			int index=a[i]/10;//对应的桶号
    			buckets[index].add(a[i]);
    		}
    		for(int i=0;i<buckets.length;i++)//每个桶内进行排序(使用系统自带快排)
    		{
    			buckets[i].sort(null);
    			for(int j=0;j<buckets[i].size();j++)//顺便打印输出
    			{
    				System.out.print(buckets[i].get(j)+" ");
    			}
    		}	
    	}
    }
    

    打印结果为:
    在这里插入图片描述

    结语

    至此,桶排序就讲完了,当然本文可能有地方讲的不好或者拥有纰漏之处还请大佬指出,后面还会讲解计数排序、基数排序并且将三者进行归纳总结!

    笔者微信公众号:bigsai 一个有趣的小伙子,时常会通过公众号和大家做一些有趣的项目和活动,欢迎关注,您的关注是我源源不断的动力。
    在这里插入图片描述

    展开全文
  • 桶排序(二维数组)

    2014-07-11 15:36:00
    桶排序(Bucket Sort)是对基数排序的一个变种。在排序过程中没有用到计数数组,而是用不同的桶来暂时存储关键字。使用二维数组模拟桶。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 76,312
精华内容 30,524
关键字:

桶排序