算法表述：
基数排序也叫桶排序，我自称它为神奇的排序。之所以说它神奇，请读者仔细往下读，最后你就会明白我为什么这么说了。他的基本原理为首先找出序列中最大的那个数，依据这个数的位数确定入桶出桶的次数。之后将数按位进行分离，依据位数值选择对应的桶，当数字全部入桶之后，我们在将数字进行出桶。这里我们将桶设计为单链表结构，对于入桶操作我们设计为尾插法，出桶操作我们设计为头删法。那么桶的个数我们如何确定呢？依据数的取值范围可以确定桶的个数。如果是针对十进制数进行排序，那么我们只需要设计十个桶便可以实现（位数值的取值范围是0~9）。
算法执行过程分析：
例如：336 719 329 170 66 511 36 519 200 504 说明：将数按照由低位到高位进行拆分，下面的每一次图示均为一次完整的入桶或出桶操作结果，由于序列中最大数字为719，有三位，故需三次入桶出桶操作。 按个位入桶：
按个位出桶： 170 200 504 336 66 719 329 519
按十位入桶：
按十位出桶： 200 504 719 519 329 336 66 170
按百位入桶：
按百位出桶： 66 170 200 329 336 504 519 719 此时序列有序（是不是很神奇呢！！！！）
代码实现：
#include <stdio.h>
#include <assert.h>
#include <math.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node *next;
}Node,*List;
void InitList(Node *plist)
{
assert(plist != NULL);
plist->next = NULL;
}
Node *GetNode(int val)
{
Node *pGet = (Node *)malloc(sizeof(Node));
assert(pGet !=NULL);
pGet->data = val;
pGet->next = NULL;
return pGet;
}
void Insert_tail(Node *plist,int val)
{
assert(plist != NULL);
Node *p = plist;
while (p->next != NULL)
{
p = p->next;
}
Node *pGet = GetNode(val);
p->next = pGet;
}
bool DelHeadNode(Node *plist,int *res)
{
assert(plist != NULL);
Node *pDel = plist->next;
if (pDel == NULL)
{
return false;
}
*res = pDel->data;
plist->next = pDel->next;
free(pDel);
pDel = NULL;
return true;
}
int GetMaxBit(int *arr, int length)
{
assert(arr != NULL);
int max = INT_MIN;
for (int i = 0; i < length; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
int digit = 0;
while (max != 0)
{
digit++;
max /= 10;
}
return digit;
}
int GetNum(int num, int figures) // 123 123 / 1 % 10 == 3 123 / 10 % 10 == 2 123 / 100 % 10 == 1
{
int base = pow((double)10,(figures));
return num / base % 10;
}
//figures --> 从右往左数第figures位的数字
void Radix(int *arr,int length,int figures)
{
Node head[10];
for (int i = 0; i < 10; i++)
{
InitList(&head[i]); // 初始化10个桶
}
int tmp = 0;
// 1、入桶 == 》 拿到数字，判断第figures位的数字为多少，并入相应的桶
int i = 0;
for (; i < length; i++)
{
tmp = GetNum(arr[i],figures); // 第figures位的数字为tmp
Insert_tail(&head[tmp],arr[i]); // 将 arr[i] 出到 tmp桶中
}
// 2、出桶
i = 0; // i 代表数组下标
int j = 0;
while (j < 10) // j 代表桶的个数
{
while (DelHeadNode(&head[j],&arr[i]))
{
i++;
}
j++;
}
}
void RadixSort(int *arr, int length)
{
int count = GetMaxBit(arr ,length);
for (int i = 0; i < count; i++)
{
Radix(arr,length,i);
}
}
void Show(int *arr, int length)
{
for (int i = 0; i < length; i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
void test(int *arr, int length)
{
RadixSort(arr,length);
Show(arr,length);
}
void test1()
{
int arr[] ={1,2,3,4,12,4444,2222,1112,11};
int length = sizeof(arr)/sizeof(arr[0]);
test(arr,length);
}
void test2()
{
int arr[] ={336,719,329,170,66,511,36,519,200,504};
int length = sizeof(arr)/sizeof(arr[0]);
test(arr,length);
}
int main()
{
test1();
test2();
return 0；
}
总结：
针对基数排序：
平均时间复杂度为O(d(n+r))，最好情况下O(d(n+rd))；最差情况下O(d(n+r))空间复杂度：O((n+rd))稳定性：稳定排序
