`
yaochaosheng
  • 浏览: 52539 次
  • 性别: Icon_minigender_1
  • 来自: guangzhou
文章分类
社区版块
存档分类
最新评论

分配排序 桶排序与基数排序

阅读更多

基本演化顺序是:分配排序——桶排序——基数排序

分配排序是最基本的为所有可能都分配一个存储位置的方法

桶排序是在分配排序的基础上为相同元素或在同一个范围内的元素分配同一个桶,因此每个桶可以看做一个变长的链表

基数排序是将元素分等级从最次级到最高级不断进行递进的排序过程

 

 

桶排序(在这里与分配排序一致:因为不存在重复元素且不划分范围)

这是迄今为止最快的一种排序法,其时间复杂度仅为Ο(n),也就是线性复杂度!但它是有条件的。

举个例子:一年的全国高考考生人数为500万,分数使用标准分,最低100,最高900,没有小数,你把这500万元素的数组排个序。我们抓住了这么个非常特殊的条件,就能在毫秒级内完成这500万的排序,那就是:最低100,最高900,没有小数,那一共可出现的分数可能有多少种呢?一共有900-100+1=801,那么多种,想想看,有没有什么投机取巧的办法?方法就是创建801,从头到尾遍历一次数组,对不同的分数给不同的加料.

比如有个考生考了500分,那么就给500分的那个桶(下标为500-100)加1,完成后遍历一下这个桶数组,按照桶值,填充原数组,100分的有1000人,于是从0填到999,都填1000101分的有1200人,于是从10002019,都填入101.于是经过这次遍历之后所有记录都是有序的了。

很显然,如果分数不是从100900的整数,而是从02亿,那就要分配2亿个桶了,这是不可能的,所以桶排序有其局限性,适合元素值集合并不大的情况。

 

 

 

在上面的基础上就有了基数排序

基数排序是对桶排序的一种改进,这种改进是让桶排序适合于更大的元素值集合的情况,而不是提高性能

我们先看看扑克牌的例子。一张牌有两个关键字组成:花色(桃<心<梅<方)+面值(2<3<4<...<A)。假如一张牌的大小首先被花色决定,同花色的牌有数字决定的话。我们就有两种算法来解决这个问题。

(1) 首先按照花色对所有牌进行稳定排序,这样就可以将所有牌分成4组。然后同组的牌(同花色)再按照面值进行排序。

(2) 首先按照面值对所有牌进行稳定排序,然后按照花色再次对所有牌进行稳定排序。

在这里的第二种方法就是基数排序!————也就是从最次的关键字开始排序,再从第二次的关键字排序,过程中参考第一次排序后元素间的相对顺序,以此类推直到最高关键字参考了次高关键的顺序而排序完成,排序结束。

 

比如字符串“abcd” “aesc” "dwsc" "rews"就可以把每个字符看成一个关键字。另外还有整数 425、321、235、432也可以每个位上的数字为一个关键字。

 

基数排序的思想就是将待排数据中的每组关键字依次进行桶分配。比如下面的待排序列:

                 278、109、063、930、589、184、505、269、008、083

我们将每个数值的个位,十位,百位分成三个关键字: 278 -> k1(个位)=8  ,k2(十位)=7 ,k3=(百位)=2。

然后从最低位个位开始(从最次关键字开始),对所有数据的k1关键字进行桶分配(因为,每个数字都是 0-9的,因此桶大小为10),再依次输出桶中的数据得到下面的序列。

       930、063、083、184、505、278、008、109、589、269(从最次关键字开始排序)

再对上面的序列接着进行针对k2的桶分配,输出序列为:

       505、008、109、930、063、269、278、083、184、589(参考最次关键字来排序第二次关键字)

最后针对k3的桶分配,输出序列为:

       008、063、083、109、184、269、278、505、589、930(参考第二次关键字来排序最高关键字)

 

很明显,基数排序的性能比桶排序要略差。每一次关键字的桶分配都需要O(N)的时间复杂度,而且分配之后得到新的关键字序列又需要O(N)的时间复杂度。假如待排数据可以分为d个关键字,则基数排序的时间复杂度将是O(d*2N) ,当然d要远远小于N,因此基本上还是线性级别的。但是,对比桶排序,基数排序每次需要的桶的数量并不多。而且基数排序几乎不需要任何“比较”操作,而桶排序在桶相对较少的情况下,桶内多个数据必须进行基于比较操作的排序。

分享到:
评论

相关推荐

    java算法——基数排序/桶排序

    基数排序/桶排序 *统计将数组中的数字分配到桶中后,各个桶中的数字个数 *数组中每个数的每一位数根据大小分配到对应大小为0~9的桶 *将各个桶中的数字个数,转化成各个桶中最后一个数字的下标索引

    基于双向链表的基数排序

    基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字拆分成数字位。并且按照数字位的值对数据项进行排序,这种方法不需要进行比较操作。 为了尽可能少的...

    C经典算法之基数排序法

    基数排序法又称「桶子法」(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些「桶」中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),...

    Python数据结构与算法之常见的分配排序法示例【桶排序与基数排序】

    主要介绍了Python数据结构与算法之常见的分配排序法,结合实例形式分析了桶排序与基数排序的相关原理及实现技巧,需要的朋友可以参考下

    c语言实现基数排序解析及代码示例

    基数排序(radixsort)属于“分配式排序”(distributionsort),又称“桶子法”(bucketsort)或binsort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用。 2.基数排序...

    c#基数排序Radix sort的实现方法

    经典排序算法 – 基数排序Radix sort 原理类似桶排序,这里总是需要10个桶,多次使用 首先以个位数的值进行装桶,即个位数为1则放入1号桶,为9则放入9号桶,暂时忽视十位数 例如 待排序数组[62,14,59,88,16]简单点五个...

    数据结构实验报告--多关键字排序.doc

    基数排序又称桶排序,从关键字本身加以分析,充分的利用关键字的特点。在基数排序中,不需要关键字间的比较。基数排序是一个分配,收集的过程,因为此实验关键字被分为十位和个位的二元组,所以需要分配,收集两次。...

    PHP排序算法之基数排序(Radix Sort)实例详解

    又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取...

    14种经典排序算法C程序(强烈推荐)

    分配排序(DistributionSort.h) 1.箱排序(桶排序)BinSort(int *array, int length) 或 BucketSort(int *array, int length) 2.基数排序 RadixSort(int *array, int length) 注意: 1.箱排序没有太大实用价值...

    算法分析与设计

    基数排序也称桶排序,是一种当关键字为整数类型时非常高效的排序方法。 基数排序算法的基本思想是:设待排序的数据元素关键字是m位d进制整数(不满足的关键字在高位补0),设置d个桶,令其编号分别为0,1,2,…,d-...

    Python实现的基数排序算法原理与用法实例分析

    又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取...

    python算法学习之基数排序实例

    基数排序法又称桶子法(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些”桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为...

    PHP实现基数排序的方法详解

    基数排序是根据关键字中各位的值,通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。 不妨通过一个具体的实例来展示一下,基数排序是如何进行的。 设有一个初始序列为: R {50, 123, 543, 187, 49, 30,...

    深入解析Radix Sort基数排序算法思想及C语言实现示例

    然后从最低位个位开始(从最次关键字开始),对所有数据的k1关键字进行桶分配(因为,每个数字都是 0-9的,因此桶大小为10),再依次输出桶中的数据得到下面的序列。 930、063、083、184、505、278、008、109、589、269...

    js-algorithms:各种算法的 JavaScript 实现

    JS算法 各种算法的 JavaScript 实现。 排序 选择 选择排序 堆排序 ...基数排序 快速排序 桶排序 计数排序 杂项 煎饼排序 自适应排序 笔记 将来会添加各种算法。 欢迎对新算法和/或改进提出任何建议。

    数据结构与算法.xmind

    基数(桶)排序 思想 分配,回收(分配到不同的位置上,然后回收)..不断分配..回收来进行排序,直到有序 做法 分配一个[array.length][10列]的二维数组来装我们的元素 最外层for循环...

    CS2110-Course-Work:我在CS2110上所做的工作-数据结构和OOP-在康奈尔大学的暑假期间

    基数排序 堆排序 图表 拓扑排序 Dijkstra的算法 最短路径 树木 作业分配 作业1 问题1 编写一个程序,它将提供两种方法来处理要分析的数据; 数据是数字的集合(双精度)。 “分析”将包括找到数字集合的最大值和...

    Java-assignments:打开

    Java分配4个分配和1个项目分配:作业1:MyBnb启动服务MyBnb希望开发一个处理整个... 将伪代码转换为算法作业3: 基于数组和基于链接的堆栈策略作业4: 队列和双端队列的基于数组和基于链接的策略项目: 桶和基数排序

Global site tag (gtag.js) - Google Analytics