精华内容
下载资源
问答
  • 链式基数排序

    2021-04-22 16:22:02
    链式基数排序 基本策略 分配----收集 何为链式基数排序? 将单关键字排序转成多关建字排序,具体为,在排序过程中,将关键字拆分成若干项,然后把每一项作为一个“关键字“。 对于整数或字符串型的关键字,可将其...

    链式基数排序

    基本策略

    • 分配----收集

    何为链式基数排序?

    • 将单关键字排序转成多关建字排序,具体为,在排序过程中,将关键字拆分成若干项,然后把每一项作为一个“关键字“。
    • 对于整数或字符串型的关键字,可将其拆分为单个数字或单个字母。
    • 例如:当单关键字“ 123 ”,从低位到高位可拆成关键字 “3”,“2”,“1”

    基本思想

    • 从最低位的关键字开始,按关键字的不同值将序列中的数据分配到不同的队列中
    • 然后按关键字从小到大(升序)收集起来,此时完成一趟分配—收集
    • 重复分配—收集,直到最高位分配—收集完成,则序列有序

    实例分析

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    算法分析

    • 将序列中的数据元素按个位进行分配,并将该数据元素存入相应队列
    • 重复以上操作,直到序列所有数据元素均按个位存入相应队列
    • 按照队列先后顺序,将每个队列中的元素连在一起构成新队列。
    • 将新队列仿照以上操作进行分配(这次按百位分配)、收集
    • 重复以上操作,直到序列中数据元素的最高位分配收集完成

    使用场景

    • 适用于关键字长度不长的整数或字符串排序

    核心算法实现(c语言)

    • 分配
    /*
    * Function: distributeRadix
    * Description: 对序列进行分配
    * Parameter: Queue* que 指向链队的指针
    * Return: void
    */
    void distributeRadix(Queue* que)
    {
    	//初始化十个带头结点的队列
    	for (int i = 0; i < 10; i++)
    	{
    		initQueue(&queue[i]);
    	}
    
    	Node* p = (*que).front->next;
    	while (p != NULL)
    	{
    		int k = getKey(p);
    		queue[k].rear->next = p;
    		queue[k].rear = p;
    		p = p->next;
    		queue[k].rear->next = NULL;
    	}
    	//清空队列
    	clear(que);
    }
    
    • 收集
    /*
    * Function: collectRadix
    * Description: 对分配好的队列进行收集
    * Parameter: Queue* que 指向链队的指针
    * Return: void
    */
    void collectRadix(Queue* que)
    {
    	int index = 0;	//标记第一个非空队列位置,默认 0
    	for (index = 0; index < 10; index++)
    	{
    		if (&queue[index].front->next->data != NULL)
    		{
    			break;
    		}
    	}
    	//将第一个非空队列加入链队中
    	Node* p = queue[index].front->next;
    	while (p != NULL)
    	{
    		(*que).rear->next = p;
    		(*que).rear = p;
    		p = p->next;
    		(*que).rear->next = NULL;
    	}
    
    	//继续寻找剩下的非空队列并添加到que链队中
    	for (index++; index < 10; index++)
    	{
    		Node* q = queue[index].front->next;
    		while (q != NULL)
    		{
    			(*que).rear->next = q;
    			(*que).rear = q;
    			q = q->next;
    			(*que).rear->next = NULL;
    		}
    	}
    	//清空10个队列
    	for (int i = 0; i < 10; i++)
    	{
    		clear(&queue[i]);
    	}
    	//除数  用于获取数据元素某位的关键字
    	divisior *= 10;
    }
    

    算法测试(c语言)

    #include <stdio.h>
    
    
    //结点
    typedef struct Node
    {
    	int data;
    	struct Node* next;
    }Node;
    //队列
    typedef struct Queue
    {
    	Node* front;
    	Node* rear;
    }Queue;
    
    //队列数组,存放10个队列
    Queue queue[10];
    //除数  用于获取数据元素某位的关键字
    int divisior = 1;
    
    /*
    * Function: initQueue
    * Description: 将队列初始化为带头结点的链队
    * Parameter: Queue* que 指向链队的指针 
    * Return: void
    */
    void initQueue(Queue* que)
    {
    	Node* p = malloc(sizeof(Node));
    	if (p != NULL)
    	{
    		p->data = NULL;
    		p->next = NULL;
    		(*que).front = p;
    		(*que).rear = p;
    	}
    	else
    	{
    		printf("node apply error!\n");
    	}
    }
    
    /*
    * Function: push
    * Description: 将数据元素从队尾入队
    * Parameter:
    			Queue* que 指向链队的指针			
    			int e 数据元素
    * return: void
    */
    void push(Queue* que, int e)
    {
    	Node* p = malloc(sizeof(Node));
    	if (p != NULL)
    	{
    		p->data = e;
    		p->next = NULL;
    		(*que).rear->next = p;
    		(*que).rear = p;
    	}
    	else
    	{
    		printf("node apply error!\n");
    	}
    }
    
    /*
    * Function: clear
    * Description: 把队列清空
    * Parameter: Queue* que 指向队列的指针
    * Return: void
    */
    void clear(Queue* que)
    {
    	(*que).front->next = NULL;
    	(*que).rear = (*que).front;
    }
    
    /*
    * Function: maxBit
    * Description: 返回数据元素最大位数
    * Parameter: Queue* que 指向无序序列的指针
    * Return: b 最大位数
    */
    int maxBit(Queue* que)
    {	
    	Node* p = (*que).front->next;
    	int maxData = p->data; 
    	while(p != NULL)
    	{
    		if (maxData < p->data)
    		{
    			maxData = p->data;
    		}
    		p = p->next;
    	}
    	int b = 0;
    	while (maxData > 0)
    	{
    		maxData /= 10;
    		b++;
    		
    	}
    	return b;
    }
    
    /*
    * Function: getKey
    * Description: 获取数据元素某位上的关键字
    * Parameter: Node* q 指向结点的指针
    * Return: k 关键字
    */
    int getKey(Node* q)
    {
    	int k = 0;
    	k = ((*q).data / divisior) % 10;
    	return k;
    }
    
    /*
    * Function: distributeRadix
    * Description: 对序列进行分配
    * Parameter: Queue* que 指向链队的指针
    * Return: void
    */
    void distributeRadix(Queue* que)
    {
    	//初始化十个带头结点的队列
    	for (int i = 0; i < 10; i++)
    	{
    		initQueue(&queue[i]);
    	}
    
    	Node* p = (*que).front->next;
    	while (p != NULL)
    	{
    		int k = getKey(p);
    		queue[k].rear->next = p;
    		queue[k].rear = p;
    		p = p->next;
    		queue[k].rear->next = NULL;
    	}
    
    	clear(que);
    }
    
    /*
    * Function: collectRadix
    * Description: 对分配好的队列进行收集
    * Parameter: Queue* que 指向链队的指针
    * Return: void
    */
    void collectRadix(Queue* que)
    {
    	int index = 0;	//标记第一个非空队列位置,默认 0
    	for (index = 0; index < 10; index++)
    	{
    		if (&queue[index].front->next->data != NULL)
    		{
    			break;
    		}
    	}
    	//将第一个非空队列加入链队中
    	Node* p = queue[index].front->next;
    	while (p != NULL)
    	{
    		(*que).rear->next = p;
    		(*que).rear = p;
    		p = p->next;
    		(*que).rear->next = NULL;
    	}
    
    	//继续寻找剩下的非空队列并添加到que链队中
    	for (index++; index < 10; index++)
    	{
    		Node* q = queue[index].front->next;
    		while (q != NULL)
    		{
    			(*que).rear->next = q;
    			(*que).rear = q;
    			q = q->next;
    			(*que).rear->next = NULL;
    		}
    	}
    
    	for (int i = 0; i < 10; i++)
    	{
    		clear(&queue[i]);
    	}
    
    	divisior *= 10;
    }
    
    /*
    * Function: radix
    * Description: 基数排序
    * Parameter: Queue* que 指向链队的指针
    * Return: void
    */
    void radix(Queue* que)
    {
    	int b = maxBit(que);
    	for (int i = 0; i < b; i++)
    	{
    
    		distributeRadix(que);
    		collectRadix(que);
    	}
    }
    
    /*
    * Function: print
    * Description: 打印序列
    * Parameter: Queue* que 指向链表的指针
    * Return: void 
    */
    void print(Queue* que)
    {
    	Node* p = (*que).front->next;
    	while (p != NULL)
    	{
    		printf("%d\t", p->data);
    		p = p->next;
    	}
    	printf("\n");
    }
    
    int main()
    {
    	Queue que;
    	initQueue(&que);
    
    	int arr[] = {39, 135, 521, 204, 367, 45, 259, 723, 412, 68};
    	int len = sizeof(arr) / sizeof(int);
    
    	for (int i = 0; i < len; i++)
    	{
    		push(&que, arr[i]);
    	}
    
    	printf("排序前序列:\n");
    	print(&que);
    
    	radix(&que);
    
    	printf("排序后序列:\n");
    	print(&que);
    
    	return 0;
    }
    

    输出如下
    在这里插入图片描述

    参考资料

    1. 《数据结构与算法》北京大学出版社 2018年版 林劼 刘震 陈端兵 戴波 著
    2. 排序算法之链式基数排序(详解)内附大佬连接
    3. 1.10 基数排序
    展开全文
  • 排序-链式基数排序

    千次阅读 2017-11-30 01:27:08
    链式基数排序

    输入格式:

    输入第一行给出正整数N105),随后一行给出N个(长整型范围内的)整数,其间以空格分隔。

    输出格式:

    在一行中输出从小到大排序后的结果,数字间以1个空格分隔,行末不得有多余空格。

    输入样例:

    11
    4 981 10 -17 0 -20 29 50 8 43 -5
    

    输出样例:

    -20 -17 -5 0 4 8 10 29 43 50 981
    
    /*
        链式基数排序 ❥(ゝω・✿ฺ)  ❥(ゝω・✿ฺ)
    */
    
    /*
       这题的关键是将负数的处理
       将余数为-9 ~ -1 转化为 0 - 8
       而余数为 0 - 9转化为 9 - 18
    */
    #include <bits/stdc++.h>
    #define MIN 0xFFFFFFFD
    using namespace std;
    typedef struct Node
    {
        int data;
        struct Node *Next;
    }Node, *NodePtr;
    typedef struct SLList
    {
        Node *head, *tail;
    }SLList;
    int GetKeySize(int n)
    {
        int cnt = 0;
        while(n != 0)
        {
            n /= 10;
            ++cnt;
        }
        return cnt;
    }
    int Ord(int val, int i)
    {
        int divisor = 1;
        for(int n = 1; n < i; ++n)
          divisor *= 10;
        if(abs(val) / divisor < 10)
            return (val / divisor) % 10;
        else
            return (abs(val) / divisor) % 10;
    }
    void Distribute(SLList &L, SLList *temp, int n)
    {
      NodePtr node = L.head;
      NodePtr tmpPtr;
      int pos;
      while(node != NULL)
      {
        tmpPtr = node->Next;
        node->Next = NULL;
        pos = Ord(node->data, n) + 9;
        if(temp[pos].head == NULL)
        {
            temp[pos].head = temp[pos].tail = node;
        }
        else
        {
            temp[pos].tail->Next = node;
            temp[pos].tail = node;
        }
        node = tmpPtr;
      }
        L.head = L.tail = NULL;//这里要置空
    }
    void Collect(SLList &L, SLList *temp)
    {
    
         for(int i = 0; i < 19; ++i)
         {
            if(temp[i].head != NULL)
            {
                if(L.head == NULL)
                {
                    L.head = temp[i].head;
                    L.tail = temp[i].tail;
                }
                else
                {
                    L.tail->Next = temp[i].head;
                    L.tail = temp[i].tail;
                }
            }
            temp[i].head = temp[i].tail = NULL;//这里要置空
         }
    
    }
    void RadixSort(SLList &L, int KeySize)
    {
         SLList temp[25];
         for(int i = 0; i < 25; ++i)
         {
             temp[i].head = temp[i].tail = NULL;
         }
         for(int i = 1; i <= KeySize; ++i)
         {
             Distribute(L, temp, i);
             Collect(L, temp);
            NodePtr cur = L.head;
         }
    }
    int main()
    {
        int N, val, pos, KeySize, MAX = MIN;
        SLList L;
        L.head = L.tail = NULL;
        scanf("%d", &N);
        for(int i = 1; i <= N; ++i)
        {
            NodePtr node = (NodePtr)malloc(sizeof(Node));
            scanf("%d", &val);
            node->data = val;
            node->Next = NULL;
            if(i == 1)
            {
                L.tail = L.head = node;
            }
            else
            {
                L.tail->Next = node;
                L.tail = L.tail->Next;
            }
            if(abs(val) > MAX)
                MAX = abs(val);
        }
         KeySize = GetKeySize(MAX);
         RadixSort(L, KeySize);
         NodePtr cur = L.head;
         printf("%d", cur->data);
         cur = cur->Next;
         while(cur != NULL)
         {
             printf(" %d", cur->data);
             cur = cur->Next;
         }
    }
    

     
    展开全文
  • 主要介绍了C语言中数据结构之链式基数排序的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
  • 文字描述  基数排序是和前面各类排序方法完全不相同,...先介绍下什么是多关键字排序,以引入链式基数排序算法。  先介绍什么是多关键字排序:  比如,对扑克牌进行排序,每张扑克牌有两个“关键字”:花色...

    文字描述

      基数排序是和前面各类排序方法完全不相同,前面几篇文章介绍的排序算法的实现主要是通过关键字间的比较和移动记录这两种操作,而实现基数排序不需要进行记录关键字间的比较。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。先介绍下什么是多关键字排序,以引入链式基数排序算法。

     

      先介绍什么是多关键字排序:

      比如,对扑克牌进行排序,每张扑克牌有两个“关键字”:花色(梅花<方块<红桃<黑桃)和面值(2<3<,…,A),且“花色”的地位高于”面值”, 那么对扑克牌排序有两种方法:

      方法1:先按不同“花色”分成有次序的4堆,每一堆的”花色”相同; 然后分别对每一堆内部按”面值”大小整理有序。这种先对主键字字进行排序,再对次关键字排序的方法叫最高位优先法(简称MSD: Most Significant first)

      方法2:先按不同”面值”分成13堆,然后将13堆自小到大叠在一起(“3”在”2”之上,”4”在”3”之上,…,最上面的是4张”A”),然后将这幅牌整个颠倒过来再重新按不同花色分成4堆,最后将这4堆按自小到的次序合在一起(梅花在最下面,黑桃在最上面)。这种先对次键字字进行排序,再对主关键字排序的方法叫最低位优先法(简称LSD: Least Significant first)

      采用第二种方法LSD法对多关键字进行排序时,也可以不采用之前介绍的各种通过关键字间的比较来实现排序的方法,而是通过若干次“分配”和“收集”来实现排序。

     

      关于链式基数排序的介绍:

      采用多关键字排序中的LSD方法,先对低优先级关键字排序,再按照高点的优先级关键字排序,不过基数排序在排序过程中不需要经过关键字的比较,而是借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法。

      比如,若关键字是十进制表示的数字,且范围在[0,999]内,则可以把每一个十进制数字看成由三个关键字组成(K0, K1, K2),其中K0是百位数,K1是十位数,K2是个位数。基RADIX的取值为10; 按LSD进行排序,从最低位关键字起,按关键字的不同值将序列中记录“分配”到RADIX个队列中后再“收集”之,如此重复d次。按这种方法实现的排序称之为基数排序,以链表作存储结构的基数排序叫链式基数排序。

     

    示意图

     

    算法分析

      对n个记录(假设每个记录含d个关键字,每个关键字的取值范围为rd个值)进行链式基数排序的时间复杂度为d*(n+rd),其中每一躺分配的时间复杂度为n,每一躺收集的时间复杂度为rd,整个排序需进行d躺分配和收集。

      所需辅助空间为2*rd个队列指针,由于采用链表作存储结构,相对于其他采用顺序存储结构的排序方法而言,还增加了n个指针域的空间。

      链式基数排序是稳定的排序。

     

    代码实现

      1 #include <stdio.h>
      2 #include <stdlib.h>
      3 #include <string.h>
      4 
      5 #define DEBUG
      6 
      7 #define EQ(a, b) ((a) == (b))
      8 #define LT(a, b) ((a) <  (b))
      9 #define LQ(a, b) ((a) <= (b))
     10 
     11 //关键字项数的最大个数
     12 #define MAX_NUM_OF_KEY    8
     13 //关键字基数,此时是十进制整数的基数就是10
     14 #define RADIX            10
     15 //静态链表的最大长度
     16 #define MAX_SPACE        10000
     17 
     18 //定义结点中的关键字类型为int
     19 typedef int KeyType;
     20 //定义结点中除关键字外的附件信息为char
     21 typedef char InfoType;
     22 
     23 //静态链表的结点类型
     24 typedef struct{
     25     //关键字
     26     KeyType    keys[MAX_NUM_OF_KEY];
     27     //除关键字外的其他数据项
     28     InfoType otheritems;
     29     int next;
     30 }SLCell;
     31 
     32 //静态链表类型
     33 typedef struct{
     34     //静态链表的可利用空间,r[0]为头结点
     35     SLCell r[MAX_SPACE];
     36     //每个记录的关键字个数
     37     int keynum;
     38     //静态链表的当前长度
     39     int recnum;
     40 }SLList;
     41 
     42 //指针数组类型
     43 typedef int ArrType[RADIX];
     44 
     45 void PrintSList(SLList L)
     46 {
     47     int i = 0;
     48     printf("下标值 ");
     49     for(i=0; i<=L.recnum; i++){
     50         printf(" %-6d", i);
     51     }
     52     printf("\n关键字 ");
     53     for(i=0; i<=L.recnum; i++){
     54         printf(" %-1d%-1d%-1d,%-2c", L.r[i].keys[2], L.r[i].keys[1], L.r[i].keys[0], L.r[i].otheritems);
     55     }
     56 //    printf("\n其他值 ");
     57 //    for(i=0; i<=L.recnum; i++){
     58 //        printf(" %-5c", L.r[i].otheritems);
     59 //    }
     60     printf("\n下一项 ");
     61     for(i=0; i<=L.recnum; i++){
     62         printf(" %-6d", L.r[i].next);
     63     }
     64     printf("\n");
     65     return;
     66 }
     67 
     68 void PrintArr(ArrType arr, int size)
     69 {
     70     int i = 0;
     71     for(i=0; i<size; i++){
     72         printf("[%d]%-2d ", i, arr[i]);
     73     }
     74     printf("\n");
     75 }
     76 
     77 /*
     78  *静态链表L的r域中记录已按(key[0],...,key[i-1])有序
     79  *本算法按第i个关键字keys[i]建立RADIX个子表,使同一子表中记录的keys[i]相同。
     80  *f[0,...,RADIX-1]和e[0,...,RADIX-1]分别指向各子表中的第一个记录和最后一个记录。
     81  */
     82 void Distribute(SLCell *r, int i, ArrType f, ArrType e)
     83 {
     84     int j = 0;
     85     //各子表初始化为空
     86     for(j=0; j<RADIX; j++)
     87         f[j] = e[j] = 0;
     88 
     89     int p = 0;
     90     for(p=r[0].next; p; p=r[p].next){
     91         j = r[p].keys[i];
     92         if(!f[j])
     93             f[j] = p;
     94         else
     95             r[e[j]].next = p;
     96         //将p所指的结点插入第j个字表中
     97         e[j] = p;
     98     }
     99 }
    100 
    101 /*
    102  * 本算法按keys[i]自小到大地将f[0,...,RADIX-1]所指各子表依次链接成一个链表
    103  * e[0,...,RADIX-1]为各子表的尾指针
    104  */
    105 void Collect(SLCell *r, int i, ArrType f, ArrType e){
    106     int j = 0, t = 0;
    107     //找到第一个非空子表,
    108     for(j=0; !f[j]; j++);
    109     //r[0].next指向第一个非空子表的第一个结点
    110     r[0].next = f[j];
    111     //t指向第一个非空子表的最后结点
    112     t = e[j];
    113     while(j<RADIX){
    114         //找下一个非空子表
    115         for(j+=1; !f[j]; j++);
    116         //链接两个非空子表
    117         if(j<RADIX && f[j]){
    118             r[t].next = f[j];
    119             t = e[j];
    120         }
    121     }
    122     //t指向最后一个非空子表中的最后一个结点
    123     r[t].next = 0;
    124 }
    125 
    126 /*
    127  * L是采用静态链表表示的顺序表。
    128  * 对L作基数排序,使得L成为按关键字自小到大的有效静态链表,L->r[0]为头结点
    129  */
    130 void RadixSort(SLList *L)
    131 {
    132     int i = 0;
    133     //将L改造成静态链表
    134     for(i=0; i<L->recnum; i++)
    135         L->r[i].next = i+1;
    136     L->r[L->recnum].next = 0;
    137 #ifdef DEBUG
    138     printf("将L改造成静态链表\n");
    139     PrintSList(*L);
    140 #endif
    141 
    142     ArrType f, e;
    143     //按最低位优先依次对各关键字进行分配和收集
    144     for(i=0; i<L->keynum; i++){
    145         //第i趟分配
    146         Distribute(L->r, i, f, e);
    147 #ifdef DEBUG
    148         printf("第%d趟分配---------------------------------------\n");
    149         PrintSList(*L);
    150         printf("头指针队列:");
    151         PrintArr(f, RADIX);
    152         printf("尾指针队列:");
    153         PrintArr(e, RADIX);
    154 #endif
    155         //第i躺收集
    156         Collect(L->r, i, f, e);
    157 #ifdef DEBUG
    158         printf("第%d趟收集----\n");
    159         PrintSList(*L);
    160         printf("按next打印:");
    161         int p = 0;
    162         for(p=L->r[0].next; p; p=L->r[p].next){
    163             printf("%d%d%d ", L->r[p].keys[2], L->r[p].keys[1], L->r[p].keys[0]);
    164         }
    165         printf("\n");
    166 #endif
    167     }
    168 }
    169 
    170 int getRedFromStr(char str[], int i, SLCell *result)
    171 {
    172     int key = atoi(str);
    173     if(key<0 || key >999){
    174         printf("Error:too big!\n");
    175         return -1;
    176     }
    177     int units = 0, tens = 0, huns = 0;
    178     //百位
    179     huns = key/100;
    180     //十位
    181     tens = (key-100*huns)/10;
    182     //个位
    183     units = (key-100*huns-10*tens)/1;
    184     result->keys[0] = units;
    185     result->keys[1] = tens;
    186     result->keys[2] = huns;
    187     result->otheritems = 'a'+i-1;
    188     return 0;
    189 }
    190 
    191 
    192 int main(int argc, char *argv[])
    193 {
    194     SLList L;
    195     int i = 0;
    196     for(i=1; i<argc; i++){
    197         if(i>MAX_SPACE)
    198             break;
    199         if(getRedFromStr(argv[i], i, &L.r[i]) < 0){
    200             printf("Error:only 0-999!\n");
    201             return -1;
    202         }
    203     }
    204     L.keynum = 3;
    205     L.recnum = i-1;
    206     L.r[0].next = 0;
    207     L.r[0].otheritems = '0';
    208     RadixSort(&L);
    209     return 0;
    210 }
    链式基数排序

     

    运行

     

    转载于:https://www.cnblogs.com/aimmiao/p/9397464.html

    展开全文
  • 排序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
      ③在基数排序中不需要移动数据元素,并且它是一种稳定的排序方法。
    展开全文
  • 10.6.2 链式基数排序

    2021-02-28 14:16:52
    链式基数排序 “分配” 和 “收集” 的实际操作仅为修改链表中的指针和设置队列的头尾指针。 算法如下 #define MAX_NUM_OF_KEY 8 //关键字项数的最大值 #define RADIX 10 // 关键字基数,此时是十进制整数的...
  • 所谓链式基数排序,就是实现基数排序时,为减少所需的辅助存储空间,应采用链表作存储结构,即链式基数排序。而基数排序也叫做多关键字排序,基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部...
  • 思想 每一轮将多个数按由低位到高位的顺序,依次放入 多个 链表(桶)中。 输出时,将链表(桶)的数据依次合并到 ...下面演示使用 链式基数排序,进行每一趟的“分配”与“收集”过程。 第一趟 第二趟 第三趟 ...
  • 排序算法之链式基数排序(详解)内附大佬连接

    千次阅读 多人点赞 2019-05-09 21:18:33
    所谓链式基数排序,就是实现基数排序时,为减少所需的辅助存储空间,应采用链表作存储结构,即链式基数排序。而基数排序也叫做多关键字排序,基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部...
  • 一个 关于链式基数排序的源代码 用记事本给大家的
  • 基数排序--链式基数排序(Radix)

    千次阅读 2010-12-03 17:43:00
    链式基数排序:属于”分配式排序”(distribution sort)基数排序法又称“桶子法”(bucket sort)或bin sort。 链式基数排序思想:透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,...
  • 7-2 链式基数排序 (20分) 实现链式基数排序,待排序关键字n满足1≤n≤1000,最大关键字数位≤5。 输入样例: 第一行输入待排序个数n(1≤n≤1000),再输入n个数(n的数位≤5)。 10 278 109 63 930 589 184 505 269 8 ...
  • C语言中数据结构之链式基数排序实现效果图:实例代码:#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1typedef int Status;typedef int ElemType;#define ...
  • 基数排序与链式基数排序

    万次阅读 2011-12-15 20:35:19
    基数排序是采用“分配”与“收集”的办法,用对多关键码进行排序的思想实现对单关键码进行排序的方法。 多关键码排序: 1.以扑克牌排序为例。每张扑克牌有两个“关键码”:花色和面值。其有序关系为: 花色: ...
  • 1.需求分析 ①.问题描述 给出一组数据,按照最低位优先的方法完成基数排序。多关键码排序按照从最主位关键码到最次位或从最次位到最主位关键码的顺序逐次排序。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,608
精华内容 1,843
关键字:

链式基数排序