基数排序(Radix Sort)----(排序算法十四)

我就是我 2022-09-17 15:13 125阅读 0赞

# 1.排序原理 #

# 2.代码实现 #

#include <stdio.h>
    #include <malloc.h>
    
    #define RADIX_10 10    //整形排序
    #define KEYNUM_31 3  //关键字个数，这里为整形位数
    
    //printArray打印出数组  
    void printArray(int a[],int size){    
        printf("数组为：%d ",a[0]);    
        for (int i=1;i<size;i++)    
        {    
            printf(" %d ",a[i]);    
        }    
        printf("\n");    
    }  
    
    /********************************************************
    *函数名称：GetNumInPos
    *参数说明：num 一个整形数据
    *		   pos 表示要获得的整形的第pos位数据
    *说明：    找到num的从低到高的第pos位的数据
    *********************************************************/
    int GetNumInPos(int num,int pos)
    {
    	int temp = 1;
    	for (int i = 0; i < pos - 1; i++)
    		temp *= 10;
    	return (num / temp) % 10;
    }
    
    /********************************************************
    *函数名称：RadixSort
    *参数说明：pDataArray 无序数组；
    *		   iDataNum为无序数据个数
    *说明：    基数排序
    *********************************************************/
    
    void RadixSort(int* pDataArray, int iDataNum)
    {
    	int *radixArrays[RADIX_10];    //分别为0~9的序列空间
    	for (int i = 0; i < 10; i++)
    	{
    		radixArrays[i] = (int *)malloc(sizeof(int) * (iDataNum + 1));
    		radixArrays[i][0] = 0;    //index为0处记录这组数据的个数
    	}
    	
    	for (int pos = 1; pos <= KEYNUM_31; pos++)    //从个位开始到31位
    	{
    		for (int i = 0; i < iDataNum; i++)    //分配过程
    		{
    			int num = GetNumInPos(pDataArray[i], pos);
    			int index = ++radixArrays[num][0];
    			radixArrays[num][index] = pDataArray[i];
    		}
    		for (int ii = 0, j =0; ii < RADIX_10; ii++)    //收集
    		{
    			for (int k = 1; k <= radixArrays[ii][0]; k++)
    				pDataArray[j++] = radixArrays[ii][k];
    			radixArrays[ii][0] = 0;    //复位
    		}
    		printArray(pDataArray,10);
    	}
    }
    
    
    void main(){
    	int a[10]={278,109,63,930,589,184,505,269,8,83};
    	int n=10;
    	RadixSort(a,10);
    }

# 3.结果 #

数组为：930  63  83  184  505  278  8  109  589  269
    数组为：505  8  109  930  63  269  278  83  184  589
    数组为：8  63  83  109  184  269  278  505  589  930