精华内容
下载资源
问答
  • 关键字基数排序思想

    千次阅读 2015-05-19 17:56:21
    基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。 1.多关键字排序 举个例子:要比较三个家族哪个更厉害,你决定通过官职来比较三代来确定. 赵家爷爷:县长(3)爸爸:村长(2)儿子:省长...

    基数排序是一种借助多关键字排序的思想来实现单关键字排序的内部排序算法。


    1.多关键字排序

    举个例子:要比较三个家族哪个更厉害,你决定通过官职来比较三代来确定.

    赵家 爷爷:县长(3)爸爸:村长(2)儿子:省长(5)

    孙家 爷爷:市长(4)爸爸:镇长(2)儿子:主席(6)

    田家 爷爷:省长(5)爸爸:市长(4)儿子:村长(1)


    要比较厉害,最先看的就是当代,爷爷再厉害也退休了,只是以前当的官,爸爸厉害上升的空间也很小了.而儿子潜力大空间大.所以相比之下儿子比爸爸的影响力大,爸爸比爷爷的影响力大.换个高端的词就是:权重.

    在这个例子中:

    儿子是:主关键字(K0)爸爸是:次关键字(K1)爷爷是:最次关键字(K2)

    儿子的权重>爸爸的权重>爷爷的权重


    1.最高位优先MSD(本例中:从儿子开始比,到爷爷结束)

    先对K0进行排序,并按K0的不同值将记录序列分成若干子序列之后,分别对K1进行排序,......,依次类推,直至最后对最次位关键字排序完成为止。

    2.最低位优先LSD(本例中:从爷爷开始比,到儿子结束)

    先对Kd-1进行排序,然后对Kd-2进行排序,依次类推,直至对最主位关键字K0排序完成为止。

    2.基数排序

    基数排序又称为桶子法,它是根据排列元素的关键字,将元素分配至对应的,藉此达到排序的目的.

    就比如说:

    当当网现有一堆书籍快递需要我们帮他排出它们的派送时间排行.假设我们根据收货地点距发货地址距离将依次将省,,区划分为0-9十个级别,级别越高路程越远,到货时间越长.例如:陕西省(9)西安市(9)长安区(9),则这件快递所有当中路途最远,到货最慢的.

    快递级别如下:

    AAA654,BBB789,CCC091,DDD432,EEE567,FFF674,GGG093,HHH509

    LSD(见上文)排序为例:

    LSD的基数排序适用于位数较小的数列排序,如果位数多的话,使用MSD效率会比较好.接下来我们再来看看LSD

    同样背景以下述数据为例:

    快递级别如下:

    AAA6()5()4(),BBB789,CCC091,DDD432,EEE569,FFF674,GGG093,HHH509,III568

    MSD排序(以省级别为5为例):



    MSD基数排序是通过”桶中建桶”的方式实现自前向后的”收集,排序”,先利用权重高的关键字(省级别)将排序元素放置大桶中(第一次),再在各个桶中放入小桶(第二次),再利用次关键字进行元素”入桶”,如此往复.最后再从最深桶中依次取出,元素便已排好次序.


    展开全文
  • 排序9.6 基数排序9.6.1 多关键字排序9.6.2 链式基数排序 9.6 基数排序 基数排序又被称为桶排序。与前面介绍的几种排序方法相比较,基数排序和它们有明显的不同。前面所介绍的排序方法都是建立在对数据元素关键字进行...

    9.6 基数排序

    基数排序又被称为桶排序。与前面介绍的几种排序方法相比较,基数排序和它们有明显的不同。前面所介绍的排序方法都是建立在对数据元素关键字进行比较的基础上,所以可以称为基于比较的排排序;而基数排序首先将待排序数据元素依次“分配”到不同的桶里,然后再把各桶中的数据元素“收集”到一起。通过使用对多关键字进行排序的这种**“分配”和“收集”的方法,基数排序实现对单关键字**进行排序。

    9.6.1 多关键字排序

    1. 一般情况下,假定数据表中有n个数据元素(elem[0],elem[l],…… elem[n-1])。每个数据元素elem[i] (0<=i<=n-1)含有d个关键字(k1i,k2i,…,kdi)。如果对于序列中任意两个数据元素 elem[j]和 elem[i] (0<=j<i<=n-1)都满足:
      (k1i,k2i,…,kdi)<(k1j,k2j,…,kdj)
      则称数据元素序列以关键字(k1,k2,…,kd)有序。在此,k1称为最高位关键字,kd称为最低位关键字。
    2. 实现多关键字排序有两种常用的方法:
      (1)最高位优先法 MSD (Most Significant Digit first)
      最高位优先法通常是一个递归的过程:
    • 首先根据最高位关键字k1进行排序,按k1值的不同,将整个数据表分成若干个子表,每个子表中的数据元素具有相同的关键字k1
    • 然后分别对每一个每个子表中的数据元素根据关键字(k2,…,kd)用最高位优先法进行排序。
    • 如此递归,直到对关键字kd完成排序为止。
      (2)最低位优先法LSD (Last Significant Digit first)
      最低位优先法是:
    • 首先依据最低位关键字kd对数据表中所有数据元素进行一趟排序;
    • 然后依据次低位关键字kd-1对上一趟排序的结果再排序。
    • 依次重复,直到按关键字k1完成最后一趟排序。
    1. 两种方法对比:
    • LSD排序方式由关键字的最右边位(低位)开始,先按关键字的最低位把所有元素分配到不同的“子桶”,然后依次把每个“子桶”中元素全部回收,完成一趟“分配”和“回收”:第2趟再按关键字的次低位把所有元素分配到不同的“子桶”,然后依次把每个“子桶”中元素全部回收……如此反复,在最后一趟“分配”“收集”完成后,所有数据元素就按其关键字的值从小到大排序好了。
    • 而 MSD 则相反,由关键字的最左边位(高位)开始,是由高位开始进行“分配”,但在“分配”之后并不把所有元素立即“收集”到一起,而是把每个“子桶”中的元素按照下一高位的值分配到“子子桶”中如此不断“分配”,在完成最低位数的“分配”后,再把所有元素依次“收集”到一起。
      由此可见,最高位优先分配法的实现要比最低位优先分配法复杂

    使用LSD排序方法时,每一趟排序都是对整个数据表操作,且需采用稳定的排序方法。下面将介绍基于LSD方法的基数排序方法。

    9.6.2 链式基数排序

    1. LSD排序方法是一种典型的基数排序,它利用“分配”和“收集”这两种运算实现多关键字排序。在这种方法中,把关键字k看成是一个d元组:(k1,k2,…,kd)。其中的每一个分量可以看成是一个单关键字,假设分量kj(1<=j<=d)有radix种取值,则称radix 为基数。
    • 例如,关键字984可以看成是一个三元组(9,8,4),位数d=3,每一位可以取0,1.…, 9,这10种值,所以其基数radix=10
    1. 用LSD方法排序对d元组中的每一个分量kj,①把数据表中的所有数据元素按kj的取值先“分配”到radix个队列(桶)中去,
      ②然后再按各队列的顺序,依把数据元素从队列中“收集”起来,这样所有数据元素按kj取值排序完成。
      ③如果对数据表中所有数据元素按关键字k(k1,k2,…,kd),依次对各分量kj (j=d,d-1,…,1)分别用这种“分配”、“收集"的运算逐趟进行排序,在最后一趟“分配”、“收集”完成后,所有数据元素就按其关键字的值从小到大排序好了。
    2. 在上述基数排序中,各个队列可以考虑采用链表存储结构,分配到同一队列的关键字通过指针链接起来。
      一共有 radix个队列,每一个队列设置两个队列指针
    • 一个指示队头,记为f[ i ](0<=i<radix);
    • 另一个指向队尾,记为e[ i ](0<=i<radix)。
    • 同时为了有效地存储和重排,数据以静态链表作为它的存储结构。
      在这里插入图片描述
    1. 代码实现
    template<class ElemType> void RaxidSort(Node<ElemType> elem[],const int d,const int radix)
    {
        int e[radix],f[radix],p,i,j,k,power;
        for(i=0; i<d; i++) //做d趟分配、收集
        {
            for(j=0; j<radix; j++)
                f[j]=0;//初始化各队列分配
            power=(int)pow((double)radix,i);
            p=elem[0].next;//初始化链表搜索指针
            while(p!=-1)//逐个元素分配
            {
                k=(elem[p].data/power)%radix;//取当前数据元素关键字的第i位
                if(f[k]==0)
                    f[k]=p;//原链表为空时,数据元素入队首
                else//原链表非空时,数据元素入队尾
                    elem[e[k]].next=p;
                e[k]=p;//修改链尾指针
                p=elem[p].next;//取链表中下一个节点
            }
            j=0;//开始数据收集
            while(f[j]==0)//跳过空队列
                j++;
            elem[0].next=f[j];
            p=e[j];
            for(k=j+1; k<radix; k++)
                if(f[k]!=0)//回收每个非空队列链入
                {
                    elem[p].next=f[k];
                    p=e[k];
                }
            elem[p].next=-1;
        }
    }
    
    1. 对于有n个数据元索的链表,若每个关键字有d位,算法需要重复执行d趟“分配”与“收集”
      ①每趟进行**“分配”的循环需要执行n次**,把n个数据元素分配到radix个队列中去;进行**“收集”的循环需要执行radix次**,把radix 个队列中的数据元素收集起来按顺序链接。所以总的时间复杂度为 O(d(n+radix)
      ②算法所需要的附加存储空间是为每个是数据元素结点增设的链接指针,及为每一个队列设置的队头和队尾指针,总共为n+2*radix
      ③在基数排序中不需要移动数据元素,并且它是一种稳定的排序方法。
    展开全文
  • 我们发现也经过证实,交换式的排序的算法的时间复杂度的下界是O(n*lgn),但是这真的就是我们的排序算法的极限了吗,事实并不是这样的,我们的多关键字的分配式排序--本文的基数排序就是如此却是打破了这样的瓶颈 ...

    1.引入:

    我们发现也经过证实,交换式的排序的算法的时间复杂度的下界是O(n*lgn),但是这真的就是我们的排序算法的极限了吗,事实并不是这样的,我们的多关键字的分配式排序--本文的基数排序就是如此却是打破了这样的瓶颈
    分配式的Radix-Sorting算法成功的将我们的算法的复杂度优化到无限接近线性阶的完美的O(n),下面,我们就来一一道来

    2.前身:

    桶式排序:
    我们先假定排序这样的一个数组
    1,9,4,8,2,7,5,6,3,10
    很显然,你们都会说出什么快排啊,归并排序,插入排序啊,堆排序啊什么的,但是我们就题目本身来看的话,可不可以这么来考虑
    我们现在假设这里有10个桶,每个桶用来存放权值是相应的标号的数字的个数
    那么很显然初始的状态应该是
    0 0 0 0 0 0 0 0 0 0
    按照题目来看的话,我们扫描一遍,将相应的数组入桶,结果为
    1 1 1 1 1 1 1 1 1 1
    最后我们从桶1开始一直输出到桶10
    很明显就会得到
    1 2 3 4 5 6 7 8 9 10
    很显然,这样的算法我们的时间耗费完全只是在扫描和输出上了,完全接近我们的O(n)的线性阶时间复杂度

    但是我们需要明确一点,这里的桶式排序有一些明显的缺陷
    1.无法排序负数
    2.需要消耗大量的额外空间,对于极限情况1,2000来说,显然会造成力不从心的情况

    于是,这里就引出了我们的基数排序

    3.基数排序概念

    基数排序的专业说法应该是:对单逻辑关键字的多关键字排序,也就是说,我们将待排对象分类城多种关键字,我们对不同的关键字都进行一趟桶式排序,然后我们对结果进行收集(这里的描述有一些偏向LSD,但是会方便我们的理解,这里我们不要过深究就这一点)
    定义:
    对有n个关键字的记录序列
    {r1,r2,r3,r4,r5...rn}
    每个记录中都含有d个关键字{k0,k1,k2,k3,k4,...kd}
    我们的基数排序要求对于任意的两个r之间我们都要满足前者的k关键字必须全部大于或者小于后者的全部关键字

    4.思路分类:

    对于基数排序,我们这里存在着两种不同的排序思路

    1.LSD(最低位优先)

    这里的最低位优先的意思是,我们从最次为的关键字进行开始,每一次进行一趟基数排序然后收集,当所有的关键字全部都匹配完全之后,我们得到的就是有序的序列
    这里的限制的终止情况是,我们必须要对所有的关键字全部都进行匹配,但是一旦在出现数字(待排对象)之间的位数差距比较大的情况,我们有可能做大量的无用功

    2.MSD(最高位优先)

    这里的MSD法参透了一些递归的思想,在这里,我们首先从高位开始匹配,每一次入桶之后,我们对每一个桶的序列也分别进行一次MSD递归调用,直到最后最后我们发现每个子桶中的元素的个数都只是<=1的情况的话,很明显,这时候我们就该强行终止了递归调用,返回我们的有序序列
    MSD对于上述的位数差距比较大的情况来看的话,可以大幅度减少我们的排序次数

    5.复杂度的优化想法思路

    1.参照网上的大神的描述,在整数排序的额时候,我们可以将基数设置的大一些
    2.在对证书进行基数排序的时候,那面会出现pow函数的调用,这时候我们的时间耗费就会出现一些提升,在这里,我们的优化思路是采用位运算的想法,将基数设定成2的幂,那么我们在进行反馈映射的过程的时候,利用位运算可以大幅度降低我们pow函数和我们的触发造成的恐怖的时间耗费,毕竟计算机还是一个二进制机器
    3.如果我们只是单纯地对数组进行基数排序的话
    我们的时间耗费大致是O(d*(3*n+radix)),空间耗费是n+radix
    但是如果我们在这里利用链表的话
    时间复杂度大致是O(d*(n+radix)),空间耗费是radix
    为什么呢
    ps:以下的思路是LSD

    1.数组法

    我们的工具:bucket桶数组,count记录每个桶的数目
    我们先来看简单的数组的操作过程
    1.初始化count
    2.扫描一遍数组O(n),将count更新维护
    5.扫描一遍count,确定每个桶的右边界,方便我们的插入操作
    4.扫描一遍数组O(n),建立映射,数组元素入桶
    5.将bucket中的元素返还(倒进)原数组中,O(n)
    以上是一趟桶式排序,对于我们的数字的范围d(如果用十进制的例子来看的话,那就是d是位数)

    2.链式基数排序(在这里,我们用链表还是静态量表的实现原理都是一样的,我们这里随便举个例子,用静态链表来描述好了)

    我们的工具radix个<head,tail>链队列的头尾指针O(2*radix)的空间复杂度
    1.扫描一遍,根据映射我们将链的节点插入相应的链队列O(n)
    2.遍历所有的radix链队列,将链队列的头尾指针相互串接,构成新的链O(radix)
    3.重复d次
    时间复杂度是O(d*(n+radix)),空间复杂度是O(2*radix+n),n是链节点的指针域

    通过上述比较,我们来看一下

      空间复杂度 时间复杂度
    数组法 O(n+ra) O(d*(3*n+ra))
    链表法 O(n+2*ra) O(d*(n+ra))
    显然从上述表格来看,我们的链式的结构更具有优越性
    当然,我所有的情况都会用代码示例一遍

    6.优缺点限制以及特殊情况的处理

    优点:排序稳定性:
    无论是从上面的链式还是数组的方式,我们都可以清楚地的看到,通过特殊的处理(链队列,数组count的利用)都是的我们的基数排序是稳定的

    1.从上面的情况,我们已经看到了,桶式排序不能处理负数,不能处理浮点数,也不能处理字符串
    但是对于基数排序,并不是这样的
    负数的话,我们可以将负数和整数进行分类考虑最后将结果合并就好
    浮点数的话,我们可以将浮点数承上一个较大的整数将其装花城整数来进行操作
    字符串的话,我们将字符串的每个字符都当成是一个关键字,从而更加方便的实现基数排序

    优点:基数排序不是交换式的,而是分配式的排序,所以说,我们的时间复杂度可以轻而易举的达到线性阶

    缺点:基数排序的内存占用和归并排序一样,非常的大,在我们的内存吃紧的情况下,基数排序不要进行考虑,但是对于我们的内存宽松,时间要求搞笑的时候,基数排序旺旺可以达到比快排更好的效果
    基数排序的LSD进行之前,我们必须要了解到所有的数组的最大的上限

    7.相应的核心代码段

    附上我的CSDN snippts连接:

    展开全文
  • 常见的五类排序算法图解和实现(多关键字排序:基数排序以及各个排序算法的总结)

    常见的五类排序算法图解和实现(多关键字排序:基数排序以及各个排序算法的总结)

    展开全文
  • 关键字排序很多时候,一个对象可以用多个特征值来刻画它,可以把每个特征值看做一个关键字,比如扑克牌有花色和点数这两个特征,如果所要求的顺序由多个关键字联合决定,我们就可以利用这种特征来使用多关键字排序...
  • 完全不同于以前的排序算法,可以说,基数排序也叫做多关键字排序,基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。 两种方式: 1、最高位优先,先按照最高位排成若干子序列,再...
  • package cn.itcast.sort; import java.util.ArrayList; import java.util.List; /**  *   * 请对整数序列进行... 可以用十进制的每个位为关键字。排序时使用十个动态数组为临时空间,进行分配和收集。  
  • 基数排序 桶排序 首先来看看桶排序: 为什么桶排序的时间复杂度是O(M+N)? 因为分配的时间复杂度是M(也就是桶的数量),而收集起来的时间复杂度是N,因此最终时间复杂度是O(M+N)。 上面那种是理想的桶排序,因为...
  • 基数排序

    2010-11-23 21:40:00
    #define RADIX 10 //关键字基数,此时是十进制整数的基数 typedef struct { int keys[3]; int next; }SLCell; typedef struct { SLCell r[11]; int keynum; //记录的当前关键字个数 int recnum;
  • 基数排序之多关键字排序运用队列

    千次阅读 2015-08-19 08:54:19
    源代码如下: #include #include typedef struct QUEUEnode* link; struct QUEUEnode{ int item ; link next; link head , tail; }; link NEW(int item, link next){ link x = (link) malloc(sizeof... x->ite
  • 链式基数排序

    2015-11-26 18:10:36
    #include using namespace std; #define MAX_NUM_OF_KEY 8 //关键字项数的...#define RADIX 10 //关键字基数,此时是十进制整数的基数 #define MAX_SPACE 10000 typedef int DataType ; typedef struct 
  • C语言中数据结构之链式基数排序 实现效果图: 实例代码: #include #include #include #define TRUE 1 #define FALSE 0 ...#define RADIX 10 //关键字基数,此时是十进制整数的基数 #define MAX_SPA
  • // 基数排序:一种多关键字的排序算法,可用桶排序实现。 int maxbit(int data[], int n) //辅助函数,求数据的最大位数 { int maxData = data[0]; ///< 最大数 /// 先求出最大数,再求其位数,这样有...
  • 按照关键字为依据进行分组的排序方法,有MSD和LSD两种方案。其中,LSD方案很特别,只通过分配与收集即可完成排序。
  • 数据结构——链式基数排序

    千次阅读 2013-09-03 16:43:00
    #include using namespace std; #define MAX_NUM_OF_KEY 8 //关键字项数的...#define RADIX 10 //关键字基数,此时是十进制整数的基数 #define MAX_SPACE 10000 typedef int DataType ; typedef struct {
  • _DataStructure_C_Impl:基数排序

    千次阅读 2015-08-14 00:58:56
    #include #include #include ...#define Radix 10 /*关键字基数,此时是十进制整数的基数*/ #define MaxSize 1000 #define N 6 typedef int KeyType; /*定义关键字类型*/ typedef struct { KeyType
  • ????表排序 ????物理排序 ????桶排序 ????基数排序 ????多关键字排序 ????各种排序算法的比较 学习资源来源: 浙大 数据结构
  • 关键字排序

    2019-10-01 10:15:56
    关键字排序就是基数排序,我是用单链表实现多关键字的排序的,但最主要的方法仍是“分配”,“收集”。单链表只是在分配与收集过程中起暂时的存储作用。不仅可以用链表,还可以用栈、队列……(都是线性的!!!...
  • 关键字排序。c++

    2020-02-25 18:20:12
    基于多关键字排序/基数排序的长方形排列。
  • 基数排序的奇技淫巧

    2017-02-12 20:37:00
    =2^32-1的基数排序,那么就把一个数分成几段多关键字基数排序就行了,类似后缀数组?  分成8位/8位/8位/8位比分成16位/16位要快【丧病的底层优化  写的是16/16的 代码如下: #include<iostream> ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 980
精华内容 392
关键字:

关键字基数