一、基数排序
基数排序(RADIX SORT)是一种基于计数排序或者是最优桶排序。这里区分一下基数排序与桶排序
- 基数排序只是借用十只桶来为0-9这十个基数进行排序分堆（可以说是最优的桶排序），反复的在保持稳定的情况下，对个位、十位。分别进行桶排序
- 桶排序里面的桶不一定是十个桶，可以是任意多的桶，只是桶的数量会影响排序的速度，桶排序主要是将元素映射到桶里面，再在各个桶里面进行排序，最后再将各个桶里面的数组归并在一起
对于基数排序是元素与元素之间不需要比较，都是统计数组里面的元素个数来实现的，是一种稳定的排序算法。
二、基数排序的思想
基数排序的思想就是，计算最大的数的位数，从个位为排序依据对各个数字进行排序，然后以十位为排序依据对各个数进行排序，依次类推，直至达到最大数的位数。那么最后得到的序列就是有序序列。
三、基于最优桶排序的基数排序
主要步骤：
1、把所有的元素都分配到相应的桶中
2、把所有桶中的元素都集合起来放回到数组中
3、依次循环上面两步，循环次数为最大元素最高位
完整代码：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXSIZE 10
int FindMaxFin(int arr[],int len)//找到最大值的位数
{int max = arr[0];int temp = 0;for(int i = 0;i < len;i++){if(arr[i] > max){max = arr[i];}}while(max != 0){max = max/10;temp++;}return temp;
}
int FindNum(int arr[],int i,int fin)//找到数字的每位的值
{return arr[i]/(int)pow(10.0,fin)%10;
}
void Radix(int arr[],int len,int fin)
{int numfin;//放数字的位的值int backet[10][MAXSIZE] = {};//定义一个二维数组int num[10] = {};//存放相应的桶0~9，每个桶中存放的元素个数for(int i = 0;i < len;i++)//将数据存放在相应的桶中{numfin = FindNum(arr,i,fin);backet[numfin][num[numfin]] = arr[i];num[numfin]++;}int bindex = 0;int aindex = 0;for(int i = 0;i < 10;i++)//将桶中的数据再放回数组中{bindex = 0;while(bindex < num[i]){arr[aindex++] = backet[i][bindex++];}}}
void RadixSort(int arr[],int len)
{int max = FindMaxFin(arr,len);for(int i = 0;i < max;i++){Radix(arr,len,i);}
}
void Show(int arr[],int len)
{for(int i = 0;i < len;i++){printf("%d ",arr[i]);}
}
int main()
{int arr[] = {39,5,89,3,480,295};int len = sizeof(arr)/sizeof(arr[0]);RadixSort(arr,len);Show(arr,len);
}