114-对基数排序算法的实现和分析

落日映苍穹つ 2022-12-30 03:46 118阅读 0赞

## 基数排序 ##

在此先书写一下需要用到的辅助函数和队列的实现（需要用到队列）

#include<stdlib.h>
    #include<string.h>
    #define INITSIZE 10
    #include<stdio.h> 
    
    typedef int ElemType;
    
    typedef struct queue
    {
        
    	ElemType *data;//存储元素的空间的首地址
    	int      front;//队列头
    	int       rear;//队列尾
    	int       size;//标识当前空间的结束位置 扩容 
    }Queue;
    
    void InitQueue(Queue *que)//初始化 
    {
        
    	if(que==NULL) exit(0);
    	que->data=(ElemType *)malloc(sizeof(ElemType)*INITSIZE);
    	if(que->data==NULL) exit(0);
    	que->front=que->rear=0;
    	que->size=INITSIZE; 
    }
    
    
    static bool AppendSpace(Queue *que)//扩容 
    {
        
    	ElemType *new_space=(ElemType *)malloc(sizeof(ElemType)*que->size*2);
    	if(new_space==NULL) return false;
    	int index=0;
    	while(que->front!=que->rear)
    	{
        
    		new_space[index++]=que->data[que->front];
    		que->front=(que->front+1)%que->size; 
    	}
    	que->front=0;
    	que->rear=que->size-1;
    	que->size *=2;
    	free(que->data);
    	que->data=new_space;
    	return true;
    }
    
    bool IsFull(Queue *que)//判满 
    {
        
    	if(que==NULL) exit(0);
    	return (que->rear+1)%que->size==que->front;//类似于处理环形 
    }
    
    bool IsEmpty(Queue *que)//判空 
    {
        
    	if(que==NULL) exit(0);
    	return que->front==que->rear;
    }
    
    bool Push(Queue *que,ElemType val)//入队(从尾入) 
    {
        
    	if(que==NULL) exit(0);
    	if(IsFull(que))
    	{
        
    		if(!AppendSpace(que))
    		{
        
    			return false;
    		}
    	}
    	que->data[que->rear]=val;
    	que->rear=(que->rear+1)%que->size;
    	return true;
    }
    
    bool Top(Queue *que,ElemType *reval)//获取队列头的值 
    {
        
    	if(que==NULL) exit(0);
    	if(IsEmpty(que)) return false;
    	*reval=que->data[que->front];
    	return true;
    }
    
    bool Pop(Queue *que)//出队(从头出) 
    {
        
    	if(que==NULL) exit(0);
    	if(IsEmpty(que)) return false;
    	que->front=(que->front+1)%que->size;
    	return true;
    }
    
    void DestroyQueue(Queue *que)//销毁 
    {
        
    	if(que==NULL) exit(0);
    	free(que->data);
    	que->data=NULL;
    	que->front=que->rear=que->size=0;
    }
    
    /*辅助函数：
        1.打印数据
    	2.判断整个数据序列是否已经有序
    	3.交互两个数据swap方法
    */
    
    void Show(int *arr,int len)//打印数据
    {
        
    	for(int i=0;i<len;++i)
    	{
        
    		printf("%d  ",arr[i]);
    	}
    	printf("\n");
    }
    
    bool IsSort(int *arr,int len)//判断整个数据序列是否已经有序
    {
        
    	for(int i=0;i<len-1;++i)
    	{
        
    		if(arr[i]>arr[i+1])
    		{
        
    			return false;
    		}
    	}
    	return true;
    }
    
    void SwapValue(int *a,int *b)//交互两个数据swap方法
    {
        
    	int tmp=*a;
    	*a=*b;
    	*b=tmp; 
    }

## 什么是基数排序 ##

基数排序是一个针对于有多个关键字的排序算法  
数字模拟有多个关键字：个位 十位 百位 千位 …  
按某一位上的数值进行排序：按照这一位上的数字的取值范围(0-9)申请相应个数的队列  
遍历整个待排序序列，将每一个数据按照这一位上的数值存储到相应下标的队列中  
将队列中的数值按照顺序依次弹出

下图是示例  
先从个位 后从十位 按照队列  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]  
**接下来实现基数排序算法**

int GetMaxDigits(int *arr,int len)//获取序列中最大值的位数
    {
        
    	int max_value=arr[0];
    	for(int i=0;i<len;++i)
    	{
        
    		if(max_value<arr[i])
    		{
        
    			max_value=arr[i];
    		}
    	}
    		int digits=0;
    		while(max_value)
    		{
        
    			digits++;
    			max_value/=10;
    		}
    		return digits;
    }
    
    int GetDigitsValue(int value,int digits)
    {
        
    	while(digits)
    	{
        
    		value/=10;
    		digits--;
    	}
    	return value%10;
    }
    
    void RadixSort(int *arr,int len)
    {
        
    	//最长的位数
    	int max_digits=GetMaxDigits(arr,len);
    	Queue que[10];
    	for(int i=0;i<10;++i)
    	{
        
    		InitQueue(&que[i]);
    	}
    	for(int i=0;i<max_digits;++i)
    	{
        
    		for(int j=0;j<len;++j)
    		{
        
    			int digits_value=GetDigitsValue(arr[j],i);
    			Push(&que[digits_value],arr[j]);
    		}
    		int index=0;
    		for(int k=0;k<10;++k)
    		{
        
    			while(!IsEmpty(&que[k]))
    			{
        
    				Top(&que[k],&arr[index]);
    				index++;
    				Pop(&que[k]);
    			}
    		}
    	}
    	for(int i=0;i<10;++i)
    	{
        
    		DestroyQueue(&que[i]);
    	} 
    }

**最后完成主函数**

int main()
    {
        
    	int arr[]={
        7,87,29,75,41,50,62,92,69,22,76,77,35};
    	Show(arr,sizeof(arr)/sizeof(arr[0]));
    	RadixSort(arr,sizeof(arr)/sizeof(arr[0]));
    	Show(arr,sizeof(arr)/sizeof(arr[0])); 
    	return 0;
    	
    }

**运行结果如下**  
![在这里插入图片描述][20201223231014325.png_pic_center]  
**基数排序算法的分析**  
时间复杂度 O(d*n) d:关键字的个数  
空间复杂度O(w*n) w:数字取值范围的个数  
稳定性：稳定

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/bfa900c9d6e349b79f15f413547717ad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/202012232309097.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201223230915315.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[20201223231014325.png_pic_center]: https://img-blog.csdnimg.cn/20201223231014325.png#pic_center