图文详解：基数排序之c语言实现

基数排序算法是一个很有趣的算法，相比于其它排序算法，其过程甚是“新奇”。相信了解这一算法后的伙伴们肯定会为之一叹——“握草”！（是我本人没错了哈哈哈哈）

总的来说，基数排序算法采用“移位排序”的方式进行排序，啥是“移位排序”？比如对于一个数组a[]={13,14,99,520},基数排序算法会这样操作

1、对元素的个位数值进行大小比较并从小到大排序，得到结果为
a[]={520,13,14,99};
2、对元素的十位数值进行大小比较并从小到大排序，得到结果为
a[]={13,14,520,99};
3、对元素数值的百位进行大小比较并排序，得到结果为
a[]={13,14,99,520};（没有百位数的元素其“百位数”默认为零）

握草 ！！！！

不知不觉中竟然排好了，amzing!!!

其实原理很巧妙，首先我们要理解为什么要从低位到高位排序，这是因为在比较大小时，高位将起到决定性的作用，就像99和520，尽管520的个位和十位都比99小，但520的百位比99大（99默认其百位为0），然后我们就要理解为什么按照上面这样的方式排序就能实现无序元素的排序有序化，这里列出两个小例子

1、对于这样一个十位数相等，个位数不相等的几个数13，14，11，是不是只要对他们的个位数值进行排序就好了，显然是OK的，排序后变成11，13，14

2、对于这样一个十位数不全相等，个位数也不相等的几个数23，14，11，显然只对个位上的数值进行排序是不够的（对个位进行排序后为11，23，14），这时候我们还需要对各元素的十位上的数值进行一次排序然后变成11，14，23

所以，基数排序算法的本质其实也比大小，只是它不像其他排序把元素当成一个整体看待，而是把元素“拆分”后再进行比较排序

然而，到这里我们还没有接触到基数排序的另一个精髓的地方，通过上面的两个小例子我们只是知道基数排序的整体思路——就是依次从元素的低位到到高位进行比较排序，但每次比较的过程我们却不知道，就像23、14、11，我们都知道先拿元素的个位进行比较，然后拿元素的十位进行比较，但对于个位比较和十位比较的具体过程我们却不清楚，难道又得用冒泡、快速等其他算法进行排序？咱们基数排序肯定不同意啊是不是。

这里咱们基数排序又整出一个“握草”操作——“桶”，啥是桶？

上图！！！！！

如上图，数组t就是一个“桶”，由于十进制的数的每一位都是0~9，所以数组t就是一个含有十个元素，且每个元素的初始值为0的数组，那它有什么用呢？从图上可以看出，以个位排序的时候，11对应在数组t的下标为1的位置，且t[1]加1，13对应在数组t的下标为3的位置，且t[3]加1，同理对应在24数组t的下标为4的位置，且t[4]加1，以十位排序的时候，11、13都对应在数组t的下标为1的位置，t[1]加两次一，24对应在数组t的下标为2的位置，t[2]加一。所以若有一元素的某个位的数值与数组t的下标值相等，则数组t的该下标的数值加一。BUT！！！这有什么用？继续上图

还是以个位排序为例，如上图，数组t进行t[i]+=t[i-1]之后，就可以得到元素的存放位置了，例如，原数组a[]={24,13,11}在进行个位排序之后，可以得到——11的新位置为（1-1）、13的新位置为（2-1），24的新位置为（3-1），也就是a[0]=11，a[1]=13、a[2]=24，然后原数组a[]={24，13，11}变成a[]={11，13，24}，同理，十位、百位、千位排序也是如此

c代码实现如下

#include<stdio.h>
#include<stdlib.h>
void radix(int*a,int length)
{
	int max=a[0];
 	for(int i=1;i<length;i++)//找出最大值
 	{
	 	 if(a[i]>max)
	 	 {
	  	 	max=a[i];
	  	 }
	 }
 	int base=1;
 	int *b=(int*)malloc(sizeof(int)*length);//每次操作后元素的排序状态都会保存在这个中间过度数组中
 	while(max/base>0)//循环的次数为最大值的位数，比如520是三位数，则循环三次
 	{
  		int t[10]={0};//声明并定义一个“桶数组”
 	for(int i=0;i<length;i++)//实现上面第一个小图的功能
  	{
  		 t[a[i]/base%10]++;
  	}
  	for(i=1;i<10;i++)//实现上面第二个小图的功能
 	{
  		 t[i]+=t[i-1];
  	}
 	for(i=length-1;i>=0;i--)
  	{
  		 b[t[a[i]/base%10]-1]=a[i];
  		 t[a[i]/base%10]--;
  	}
  	for(i=0;i<length;i++)//赋值
  	{
   		a[i]=b[i];
  	}
  	base=base*10;
 	}
}

int main()
{
	int a[]={13,99,520,14};
  	int length=sizeof(a)/sizeof(int);
 	 int *b=(int *)malloc(sizeof(int)*length);
 	radix(a,length);
  	for(int i=0;i<length;i++)
    	printf("%d ",a[i]);
 	 printf("\n");
	return 0;
}