展开

关键词

(Radix sort)是一种非比较型整算法,其原理是将整按位切割成不同的字,然后按每个位分别比较。比较官方地说,是一种于多关键字的具体过程如下: 将所有待比较值(正整)统一为同样的位长度,位较短的前面补零。 然后,从最低位开始,依次进行一次。这个并非比较大小,而是将对应的字放置在其对应的桶中。 然后,再从十位字开始进行同样的操作,直到最高位。 这样从最低位一直到最高位完成以后, 列就变成一个有列。 下面给出图示,帮助理解的过程。 ? 下面给出示例代码(Java版,适用于正整) /** * @param number 给定一个字 * @param order 指定要获取的位,取值应该大于0(个位用1表示,十位用 // 分为分配过程和收集过程两大步 for (int i = 1; i <= maxOrder; i++) { // 分配过程(列装入桶中)

21920

假设对0~10^6-1的1000个整进行,使用r=10^6的方法相当于直接对使用箱子。 使用r=1000的方法,其过程如下: (1)采用每个的最低3位字进行,令range=1000; (2)对(1)的结果按倒次3位(即倒第4到第6位)字进行。 上述每次都需要3000个执行步,因此总共需要6000步。若使用为r=100的方法,则需要三次箱子,每次针对两位字。 每次箱子需要1200个执行步,总的执行步为3600.如果使用为r=10的方法,则要进行6次箱子,每次针对一位字,总的执行步骤为6*(10+1000+10)=6120.对于本例, 因此,对n个,可以用c次range=n个箱子。因为c是一个常量,所以整个时间为O(cn)=O(n)。

31640
  • 广告
    关闭

    90+款云产品免费体验

    提供包括云服务器,云数据库在内的90+款云计算产品。打造一站式的云产品试用服务,助力开发者和企业零门槛上云。

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    (radix sort)属于“分配式”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要的元素分配至某些 “桶”中,藉以达到的作用,法是属于稳定性的,其时间复杂度为O (nlog(r)m),其中r为所采取的,而m为堆,在某些时候,法的效率高于其它的稳定性法 方法:最高位优先 MSD、最低位优先LSD 思想:最低位优先LSD方案 1、  将待字根据个位上的字进行 2、  将待第一步结果再按照十位上字进行 3、  按照位从低到高依次 示例: $arr '次之后:'; foreach ($temp as $v) { for($j =0 ;$j < count($v); $j++) { echo "\n"; } return $arr; } $arr = radix_sort($arr, 3); print_r($arr); 以上示例有一个问题,如果字是负

    36760

    前言 原理不难理解,但是在算法设计上,个人感觉还是比那些常见的要难的,耐心慢慢一步步理解,还是比较容易看懂的,注意有两种,一种是高位优先,一种是低位优先,在这里我只讲低位优先, 时间复杂度 的时间复杂度为O (nlog(r)m),其中r为所采取的,而m为堆 原理 字为16,21,5,49,33,456,327,56,65,234 这是我测试的实例字,下面有源程 ,最高位有三位(程里max=3),所以要进行三遍(下图只了两次,第三遍也一样啦),第一遍,以个位分桶,个位相同放在一个桶里,然后把桶里的在依次拿出来,第一次拿出,顺为21,33,234,5 c++ 该实例,是按部就班的按照桶来放的,但是由于在过程中用到的桶是二维组,因此造成一定的资源浪费,但二维组前一个字表示桶号,后一个表示放的位置,极大的降低了理解难度,因为每个桶内放的个是用 ];//把桶内好的全都倒给要组,进行下轮 b++; } } }

    42430

    简介 属于非比较算法类,故其时间复杂度不受比较算法时间复杂度下界的限制。关键字的最低位到最高位中的每一位采用其他算法进行时间复杂度可以达到 (这中情况下对每一位采用的算法为计)。其中, 为待列的关键字每一位的最大范围,ddd 是关键字的目。 计要求每一所使用的算法都是稳定的,否则将影响计的正确性。是稳定的,其原址性取决于对每一位所使用的算法的原址性。 2. 而则是将关键字的每一位对应每一个关键字,高位对应高优先级关键字,低位对应低优先级关键字,然后采用自底向上的思想对每一位进行一般采用计对每一位进行一轮,这样时间复杂度就是线性的,为 ;由于计是非原址的,所以如此实现的也是非原址的,且空间复杂度取决于一轮计所需的空间复杂度(故适用性比计广

    6920

    7.5.2

    是一种很特别的方法,它不是于比较进行的,而是采用多关键字思想,借助“分配”和“收集”两种操作对单逻辑关键字进行又分为最高位优先(MSD)和最低位优先(LSD)。 r(r个队列),但以后的中重复使用这些队列,所以的空间复杂度为O(r). 时间效率:需要进行d趟分配和收集,一趟分配需要O(n),一趟收集需要O(r),所以的时间复杂度为O(d(n+r)),它与列的初始状态无关。 稳定性:对于算法而言,很重要一定是按位时必须是稳定的,因此,这也保证了保持稳定性。

    13530

    10.6

    01 1、(Radix Sorting)是和前面几篇文章所述各类方法完全不相同的一种方法。 2、实现主要是通过关键字间的比较和移动记录这两种操作,而实现不需要进行记录关键字间的比较。 3、是一种借助多关键字的思想对单逻辑关键字进行的方法。 4、是借助“分配”和“收集”两种操作对单逻辑关键字进行的一种内部方法。 5、有的逻辑关键字可以看成由若干关键字复合而成。 6、早在计算机出现之前,利用卡片分类机对穿孔卡上的记录进行就是用的链式。 如果您觉得本篇文章对您有作用,请转发给更多的人,点一下好看就是对小编的最大支持!

    1503029

    要点 与本系列前面讲解的七种方法都不同,它不需要比较关键字的大小。 它是根据关键字中各位的值,通过对的N个元素进行若干趟“分配”与“收集”来实现的。 不妨通过一个具体的实例来展示一下,是如何进行的。 设有一个初始列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。 后:     0   2   11  30  49  50  100 123 187 543  算法分析 的性能 [图片] 时间复杂度 通过上文可知,假设在中,r为,d为位的时间复杂度为O(d(n+r))。 我们可以看出,的效率和初始列是否有没有关联。 空间复杂度 在过程中,对于任何位上的进行“装桶”操作时,都需要n+r个临时空间。 算法稳定性 在过程中,每次都是将当前位上相同值的元素统一“装桶”,并不需要交换位置。所以是稳定的算法。

    30190

    (Radix Sort)

    之前,我们先说桶本思想:是将阵列分到有限量的桶子里。每个桶子再个别(有可能再使用别的算法或是以递回方式继续使用桶进行)。桶是鸽巢的一种归纳结果。 对字型或字符型的单关键字,可以看作由多个位或多个字符构成的多关键字,此时可以采用“分配-收集”的方法进行,这一过程称作法,其中每个字或字符可能的取值个称为。 最后的次就是高优先级高的在前,高优先级相同的低优先级高的在前。于分别,分别收集,所以是稳定的。 希尔 (4)线性阶(O(n))   ,此外还有桶、箱。 原表是否有,对简单选择、堆、归并的时间复杂度影响不大。

    1.7K20

    算法渣--

    没有一身好内功,招式再多都是空;算法绝对是防身必备,面试时更是不可或缺;跟着算法渣一起从零学算法 线性 常见的三种以线性时间运行的算法:计和桶; 需要注意的是线性算法是非于比较的算法 它是于元素值的每个位上的字符来的。 对于字而言就是分别于个位,十位, 百位或千位等等字来(Radix sort)是一种非比较型整算法,其原理是将整按位切割成不同的字,然后按每个位分别比较。 ,整个组也就好了 复杂度 时间复杂度 假设在中,r为,d为位。 则的时间复杂度为O(d(n+r))。 空间复杂度 在过程中,对于任何位上的进行“装桶”操作时,都需要n+r个临时空间

    17630

    ——归并

    归并 归并:将两个或两个以上的有表组合成一个新有本思想 初始列看成n个有列,每个子列长度为1 两两合并,得到n/2个长度为2或1的有列 再两两合并,重复直至得到一个长度为 n的有列为止 [在这里插入图片描述] 算法分析 时间效率:O(nlog2n) 空间效率:O(n) 稳定性:稳定 是一种借助“多关键字”的思想来实现“单关键字”的内部算法 十进制比较可以看作是一个多关键字 [在这里插入图片描述] --- 最低位优先LSD法 首先依据最低位码Kd对所有对象进行一趟 再依据次低位码Kd-1对上一趟结果 依次重复,直到依据码 这种方法不需要再分组,而是整个对象组都参加 [在这里插入图片描述] 链式 本思想 先决条件: - 知道各级关键字的主次关系 - 知道各级关键字的取值范围 过程 - 首先对低位关键字 - 按照列对应的值的大小,从各个列中将记录‘收集’,收集后的列按照此位关键字有。 - 在此础上,对前一位关键字进行

    138115

    算法

    算法是据的每一位来也适用于正整。正整每一位都是从0~9, 这个顺是天然的。因此可以利用这种自然的列进行。 在过程中,我们先看个位上的的大小,然后逐渐往高位看。 的关键点: 适用于对正整进行。 需要从低位开始。从高位开始也可以,复杂度会增加。 举例说明一下的过程: 以组61, 71, 14, 30, 18 为例 首先看个位,按顺进行分成(30),(61,71),(14),(18) 四组。 然后再合成一个组为30,61,71,14,18 看十位上的,按顺进行分成(14,18),(30),(61),(71)四组。 再合成一个组为14,18,30,61,71。

    13420

    算法-

    算法- <?php /** * php算法实战. * * 算法- * * 分为两种LSD,MSD * * LSD: * 从个位开始,把当前位的放到0~9对应的桶子中,直到最高位为止 * 适合位较短 * * MSD: * 从最高位开始,不立即合并,再在桶中以下一位建立子桶,直到建立了最低位桶为止 * 适合位较多 */ /** * * * Least Significant Digit first $tmp); unset($v); unset($arr); ++$splice; } return $value; } /** * array $result 存放的新空间 * @return array 组 */ function get_value($value = [], $length

    463140

    算法 ---

    一、思想 是桶的扩展,它将所有待值统一为同样的位长度,位较短的前面补0,然后从最低位开始,依次进行一次。这样从最低为一直到最高位完成后,待列就有了。 桶 第一轮: 将每个元素的个位取出,然后放到对应编号的桶里。比如第一个元素53,个位是3,所以放在下标为3的桶里。一轮下来,情况如下: ? 就是组中最大有多少位,就要进行几轮。通过这些分析大家发现啥没有?每一轮的,就是对0到9,那岂不是很适合用计? 没错,就是这样,所以,中,我们要做的就是每一轮都用计就好了。 二、代码实现 以下代码就是于计实现的,网上的一些教程可能会用二维组来表示桶,这样容易理解,但是非常浪费空间。

    15331

    什么是

    这篇文章用漫画的形式讲解了,通俗易懂。 ? ? ————— 第二天 ————— ? ? ? ? ? ? ? ———————————— ? ? ? ? ? ? 什么是计呢? 第二轮:在第一轮结果的础上,按照第二位字符。 ? 需要注意的是,这里使用的计必须是稳定,这样才能保证第一轮出的先后顺在第二轮还能继续保持。 如此一来,这些字符串的顺好了。 像这样把字符串元素按位拆分,每一位进行一次计的算法,就是(Radix Sort)。 既可以从高位优先进行(Most Significant Digit first,简称MSD),也可以从低位优先进行(Least Significant Digit first,简称LSD 刚才我们所举的例子,就是典型的LSD方式的。 ? ? 什么意思呢?

    40610

    python实现

    python实现 (英语:Radix sort)是一种非比较型整算法,其原理是将整按位切割成不同的字,然后按每个位分别比较。 由于整也可以表达字符串(比如名字或日期)和特定格式的浮点,所以也不是只能使用于整。 所以的原理就是,先元素的最后一位,再第二位,直到所有位完。 这里并不能先第一位,那样最后依然是无。 举个例子: 第一次最低位,上边的列变成了下面的样子 ? 从这个图中也能看出,于桶实现的。 具体代码 这里将列表进行,默认列表中的元素都是正整 def radix_sort(s): """""" i = 0 # 记录当前正在拿一位,最低位为1 max_num 345345], [], [], [], [], [], []] [1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453, 23424, 345345] 总结 不仅仅只能正整

    44130

    Python实现

    /usr/bin/env python #coding=utf-8 #于桶 from random import randint def RadixSort(list,d): for k in xrange(d):#d轮 s=[[] for i in xrange(10)]#因为每一位字都是0~9,故建立10个桶 '''对于组中的元素 ,首先按照最低有效字进行 ,然后由低位向高位进行。''' for i in list: '''对于3个元素的组[977, 87, 960],第一轮首先按照个位字相同的 放在一个桶s[7]=[977] a=RadixSort(a,3)#将组再赋给a!!!!

    17020

    Python实现

    一、简介 (Radix Sort)是一种非比较型的算法,与桶的思想相似,对据进行分桶和合并。 据按位进行分桶,然后将桶中的据合并。 每次分桶只关注其中一位据,其他位的据不管,最大的据有多少位,就进行多少次分桶和合并。除了用于对整进行,也可以用于对浮点、字符串进行。 先按最低位进行分桶,合并,一直到最高位,依次进行分桶和合并,便得到一个有列。 二、原理 的原理如下: 1. 将所有桶中的据全部取出。以个位进行分桶和合并完成,第一轮结束。 ? 9. 第一轮已经对个位进行了,得到了一个新的列表。 当待列表中的最大值有 d 位时,需要进行 d 轮,时间复杂度为 O(d*(n+k)) 。 2. 稳定性 在中,需要将待列表中的据进行分桶和合并。

    16420

    是什么?

    概念 (radix sort)属于“分配式”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要的元素分配至某些 “桶”中,藉以达到的作用,法是属于稳定性的,其时间复杂度为O (nlog®m),其中r为所采取的,而m为堆,在某些时候,法的效率高于其它的稳定性法。 是一种很特别的方法,它不于比较和移动进行,而于关键字各位的大小进行是一种借助多关键字的思想对单逻辑关键字进行的方法。 "某个位"进行(桶) * 参说明: * a -- 组 * n -- 组长度 * exp -- 指。 对组a按照该指进行

    16020

    算法(十):

    也可以称为多关键字,同计类似,也是一种非比较性质的算法。将待集合中的每个元素拆分为多个总容量空间较小的对象,对每个对象执行桶后,则完成过程。 在桶础上做了优化,桶需要选择适当的映射规则,来完成集合中元素到多个桶的映射,也可以称之为值域划分。 而桶又是一种对元素总容量敏感的算法,所以存在使用限制。 过程中也使用了桶操作,不过对于桶面向的对象进行了优化。 所以在过程中,给其中的桶操作选择了容量空间有限的对象。 ;若待元素为字符串,则 ? ,因为的容量空间总是有限的,所以算法的时间复杂度为 ? 。 其实中不一定按照每一位进行,也可能元素中的几位构成了一个组合,按照组合为单位进行

    94110

    相关产品

    • 云服务器

      云服务器

      云端获取和启用云服务器,并实时扩展或缩减云计算资源。云服务器 支持按实际使用的资源计费,可以为您节约计算成本。 腾讯云服务器(CVM)为您提供安全可靠的弹性云计算服务。只需几分钟,您就可以在云端获取和启用云服务器,并实时扩展或缩减云计算资源。云服务器 支持按实际使用的资源计费,可以为您节约计算成本。

    相关资讯

    热门标签

    扫码关注云+社区

    领取腾讯云代金券