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

    千次阅读 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
      ③在基数排序中不需要移动数据元素,并且它是一种稳定的排序方法。
    展开全文
  • C语言中数据结构之链式基数排序 实现效果图: 实例代码: #include #include #include #define TRUE 1 #define FALSE 0 ...#define RADIX 10 //关键字基数,此时是十进制整数的基数 #define MAX_SPA
  • package cn.itcast.sort; import java.util.ArrayList; import java.util.List; /**  *   * 请对整数序列进行... 可以用十进制的每个位为关键字。排序时使用十个动态数组为临时空间,进行分配和收集。  
    package cn.itcast.sort;

    import java.util.ArrayList;
    import java.util.List;
    /**
     * 
     * 请对整数序列进行排序。
             随机产生1000个整数,其中整数的范围0~9999
             可以用十进制的每个位为关键字。排序时使用十个动态数组为临时空间,进行分配和收集。
             采用低关键字优先的基数排序完成对整数序列的排序任务。
              注意体会仅仅依靠分配、收集的手段即可完成排序。
     *
     */
    public class ListBaseSort {

    public static void main(String[] args) {
    // TODO Auto-generated method stub
    List data = new ArrayList();

    //填充随机值,这里的随机数范围是0~9999;
    for(int i=0; i<1000; i++) 
    data.add((int)(Math.random() * 10000));

    //准备十个桶
    List[] base = new ArrayList[10];
    for(int i=0; i<base.length; i++) base[i] = new ArrayList();

    //从低到高,分配与收集,k是为数,1,10,100,1000
    //这里先是按照个,十,百,千的顺序分成四组,每组再分配10个0~9动态数组空间分别按高位排序,
    //最后递归排序次位数据。

    for(int k=1; k<=1000; k*=10){
    for(int i=0; i<data.size(); i++) 
    //按关键字分配到桶里
    base[(Integer)data.get(i)/k%10].add(data.get(i)); 
    data.clear();
    for(int i=0; i<base.length; i++) 
    data.addAll(base[i]);  //收集
    for(int i=0; i<base.length; i++)              
    base[i].clear();  //清桶
    }

    System.out.println(data);
    }

    }

    结果:


    展开全文
  • 优质文档值得推荐 常见的五类排序算法图解和实现(多关键字排序:基数排序以及各个排序算法的总结)
    展开全文
  • 我们发现也经过证实,交换式的排序的算法的时间复杂度的下界是O(n*lgn),但是这真的就是我们的排序算法的极限了吗,事实并不是这样的,我们的多关键字的分配式排序--本文的基数排序就是如此却是打破了这样的瓶颈 ...
  • 基数排序

    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;
  • 基数排序 桶排序 首先来看看桶排序: 为什么桶排序的时间复杂度是O(M+N)? 因为分配的时间复杂度是M(也就是桶的数量),而收集起来的时间复杂度是N,因此最终时间复杂度是O(M+N)。 上面那种是理想的桶排序,因为...
  • 基数排序之多关键字排序运用队列

    千次阅读 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
  • 完全不同于以前的排序算法,可以说,基数排序也叫做多关键字排序,基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。 两种方式: 1、最高位优先,先按照最高位排成若干子序列,再...
  • 链式基数排序

    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 
  • 10.6.2 链式基数排序

    2021-02-28 14:16:52
    “分配-收集”方法 基数:每个单位的数位或者字符的值集的大小(0到9,...#define RADIX 10 // 关键字基数,此时是十进制整数的基数 #define MAX_SPACE 10000 typedef struct { KeysType keys[MAX_NUM_OF_KEY]; } ..
  • 数据结构——链式基数排序

    千次阅读 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
  • 看数据结构写代码(65) 基数排序

    千次阅读 2015-05-04 09:53:55
    欢迎指出代码不足 参考书本:严蔚敏《数据结构 .C语言版》 // RadixSort.cpp : 定义控制台应用程序的入口点...#define RADIX 10//关键字基数 #define KEY_NUM 3//关键字个数 struct SLNode{//静态链表节点 int key
  • 基数排序的奇技淫巧

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

    2012-01-03 20:20:39
    参考 《数据结构》(C语言版)--严蔚敏编著...#define RADIX 10 //关键字基数,一般为10进制 #define MAX_SPACE 100 //数组最大容量 /*--- 静态链表 ---*/ struct SLCell{ int keys; //关键字 用于存储待排序的数 i
  • // 基数排序:一种多关键字的排序算法,可用桶排序实现。 int maxbit(int data[], int n) //辅助函数,求数据的最大位数 { int maxData = data[0]; ///< 最大数 /// 先求出最大数,再求其位数,这样有...
  • 按照关键字为依据进行分组的排序方法,有MSD和LSD两种方案。其中,LSD方案很特别,只通过分配与收集即可完成排序。
  • 这次的经历终于让我尝到了什么叫“尽信书不如无书”!虽然以前也有过类似的经历,但是这次的...)#include #include #define MAX_NUM_OF_KEY 3 //关键字项数的最大值#define RADIX 10 //关键字基数,此时是十进制

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,747
精华内容 13,098
关键字:

关键字基数