基数排序C/C++代码实现

偏执的太偏执、 2023-02-24 08:09 12阅读 0赞

## 链式基数排序： ##

分配类排序不需要比较关键字的大小，它 是根据关键字中各位的值，通过对待排序记录进行若干趟 “ 分配 ” 与 “ 收集” 来实现排序的，是一种 借助于多关键字排序的思想对单关键字排序的方法。基数排序(RadixSorting)是典型的分配类排序  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]

## 算法属性: ##

时间复杂度为O(n)  
空间复杂度为O(n+ rd)，（假设每个记录含d个关键字，每个关键字的取值范围为rd个值）。

稳定排序。  
基数排序使用条件有严格的要求：需要知道各级关键字的主次关系和各级关键字的取值范围。

## 代码如下： ##

#include<stdio.h>
    #include<stdlib.h>
    
    #define MAX_NUM_OF_KEY 8  //构成关键字组成部分的最大值
    #define RADIX 10          //基数，数字0~9
    #define MAX_SPACE 1000	  //静态链表最大空间
    
    //结点结构
    typedef struct
    {
        
    	int date;						//关键字
    	int keys[MAX_NUM_OF_KEY];		//关键字按位数存储
    	int next;						//存放下一个结点所在数组中的下标位置
    
    }SLCell;
    //静态链表结果
    typedef struct
    {
        
    	SLCell r[MAX_SPACE];
    	int keynum;			//关键字位数
    	int recnum;			//静态链表的当前长度
    }SLList;
    //指针数组，记录子序列首尾记录的位置
    typedef int ArrType[RADIX];
    
    
    
    //分配
    void Distribute(SLCell *r, int i, ArrType f, ArrType e)
    {
        
    	int p, j;
    	//初始化指针数组
    	for (int j = 0; j <RADIX; j++)
    	{
        
    		f[j] = 0;
    	}
    
    	for (p = r[0].next; p; p = r[p].next)
    	{
        
    		j = r[p].keys[i];			//取出关键字的第i位
    		if (!f[j])						//如果该序列为空，则直接存放
    		{
        
    			f[j] = p;
    		}
    		else							//如果不为空，则存在最后一个记录后面
    		{
        
    			r[e[j]].next = p;
    		}
    
    		e[j] = p;						//更新尾指针
    	}
    }
    
    //收集
    void Collect(SLCell *r, int i, ArrType f, ArrType e)
    {
        
    	int j, t;
    	for (j = 0; !f[j]; j++);		//遍历 直到找到一个不为空的子序列 （为空说明没有符合该子序列条件的位数）
    
    	r[0].next = f[j];				//重新让链表的头指针指向第一个子序列中不为空的首记录
    	t = e[j];						//保存该子序列的尾指针
    	for (j++; j < RADIX; j++)
    	{
        
    		if (f[j])					//找到下一个非空的子序列
    		{
        
    			r[t].next = f[j];		//链接两个非空子序列
    			t = e[j];
    		}
    	}
    	r[t].next = 0;					//把最后一个结点的next置为0
    }
    
    
    void RadixSort(SLList *L)
    {
        
    	ArrType f, e;							//分别指向首和尾的两个指针数组
    	for (int i = 0; i <L->keynum; i++)		//从个位开始 依次进行分配和收集
    	{
        
    		Distribute(L->r, i, f, e);
    		Collect(L->r, i, f, e);
    	}
    }
    
    
    
    
    //打印排序结果
    void println(SLList *L)
    {
        
    	int p;
    	for (p = L->r[0].next; p; p = L->r[p].next)
    	{
        
    		printf("%d, ", L->r[p].date);
    
    	}
    	printf("\n");
    }
    
    
    
    //关键字按位分开存储到数组中
    void creatkeys(int key, int i, SLList *L)
    {
        
    
    	for (int j = 0; j <L->keynum; j++)			//0为个位，1为十为，2为百位
    	{
        
    		L->r[i].keys[j] = key % 10;
    		key = key / 10;
    	}
    	L->r[i - 1].next = i;
    	i++;
    }
    
    
    int main()
    {
        
    	SLList *L = (SLList*)malloc(sizeof(SLList));
    
    	L->keynum = 3;
    	L->recnum = 0;
    
    	L->r[1].date = 50;
    	creatkeys(50, 1, L);
    	L->r[2].date = 23;
    	creatkeys(23, 2, L);
    	L->r[3].date = 142;
    	creatkeys(142, 3, L);
    	L->r[4].date = 128;
    	creatkeys(128, 4, L);
    	L->r[5].date = 7;
    	creatkeys(7, 5, L);
    
    	L->recnum = 5;
    	L->r[5].next = 0;
    
    	RadixSort(L);
    	println(L);
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: /images/20230209/20c4ab505e8e43158a0db4a0101bbcff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]: /images/20230209/4184eb728e0f43c692ba66a5f5d17a5c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 2]: /images/20230209/bfd1956893a5479f9905007e31306a72.png