基本思想

基数排序不是基于比较的排序，它的原理是将整数分割成多位单个数字，然后依次按每位的数字进行排序(必须是稳定的排序)，最终得到结果。当然，它的用途也不仅限于对数字的排序。

图解

先按个位大小对数进行排序，再按十位排序，最后按百位排序即得到结果

代码

伪代码

C代码

#include 
    
     #include 
     
      #include 
      
       void Counting_sort(int * a, int * b, int k, int len, int * ans)//内部稳定排序，按数组a来对数组ans排序，结果放在b里{    k++;    int * c = (int *)malloc(sizeof(int)*k);    int i, j;    for(i = 0; i < k; i++)    {        c[i] = 0;    }    for(j = 0; j < len; j++)    {        c[a[j]] += 1;    }    for(i = 1; i < k; i++)    {        c[i] += c[i-1];    }    for(j = len-1; j >= 0; j--)    {        b[c[a[j]]-1] = ans[j];        c[a[j]]--;    }}void Radix_sort(int * a, int * b, int k, int len)//基数排序{    int i;    int Max = a[0];    for(i = 1; i < len; i++)//找最大数    {        if(a[i] > Max)            Max = a[i];    }    int count = 1;//循环次数    while(Max/10!=0)//通过最大数算所需循环次数    {        Max/=10;        count++;    }    int p[len];//存放单位数    int t = 1;    while(count!=0)    {        for(i = 0; i < len; i++)//计算单位数        {            p[i] = a[i] % (int)pow(10,t) / pow(10,t-1);        }        t++;        Counting_sort(p,b,k,len,a);//内部稳定排序        for(i = 0; i < len; i++)        {            a[i] = b[i];        }        count--;    }}void Show(int * p, int len){    int i;    for(i = 0; i < len; i++)    {        printf("%d ", p[i]);    }    printf("\n");}int main(){    int len = 8;    int a[] = {12,15,13,0,12,3,0,3};    int k = 20;    int b[8];    Radix_sort(a,b,k,len);    Show(b,len);    return 0;}