转载http://blog.csdn.net/Shayabean_/article/details/44885917博客
先说说基数排序的思想：
基数排序是非比较型的排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。在每一次排序中，按照当前位把数组元素放到对应
的桶当中，然后把桶0到桶9中的元素按先进先出的方式放回数组中。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
这个智能版本的基数排序RadixSort（L）较之前的RadixSort（L，max）不同的是不需要输入待排序列最大数的位数。因为最大数位在程序中已经计算过了，但是因为需要计算最大数，所以需要对待排链表最开始循环一次，RadixSort（L，max）速度比RadixSort（L）稍快。
这篇博客包括4个文件，两个头文件RadixSort.h和fatal.h，一个库函数RadixSort.c，和一个测试文件Test_Radix_Sort.c
头文件fatal.h:
1 #include2 #include 3 #define Error(Str) FatalError(Str)4 #define FatalError(Str) fprintf(stderr, "%s\n", Str), exit(1);
头文件RadixSort.h：
1 typedef int ElementType; 2 #ifndef RADIX_SORT_H 3 #define RADIX_SORT_H 4 5 #include6 #include 7 #define ListEmpty -2 8 9 struct Node;10 typedef struct Node *PtrToNode;11 typedef PtrToNode List;12 typedef PtrToNode Position;13 14 List MakeEmpty(List L);15 bool IsEmpty(List L);16 bool IsLast(Position P, List L);17 Position Header(List L);18 Position Advance(Position P);19 ElementType Retrieve(Position P);20 void DeleteList(List L);21 void PrintList(const List L);22 ElementType Max_LinkedList(List L);//获取链表的最大值23 int Get_Num_Length(ElementType Num);//获取某个数的位数24 void Insert(ElementType X, List L, Position P);25 void MoveNode(List L1, List L2);//将表L2中的头节点移动成为L1的尾节点26 void RadixSort(List L);//最终基数排序函数，输入链表L，将L排序得到新的排序链表L27 #endif // !RADIX_SORT_H
其中RadixSort是最终排序函数，调用它即可排序。
库函数RadixSort.c
1 #include "RadixSort.h" 2 #include3 #include 4 #include 5 #include 6 #include"fatal.h" 7 8 //定义结构体 9 struct Node 10 { 11 ElementType Element; 12 Position Next; 13 }; 14 15 //初始化链表 16 List MakeEmpty(List L) 17 { 18 if (L != NULL) 19 DeleteList(L);//如果链表非空，则删除链表 20 L = malloc(sizeof(struct Node)); 21 if (L == NULL) 22 FatalError("Out of memory!"); 23 L->Next = NULL; 24 return L; 25 } 26 //判断链表是否为空 27 bool IsEmpty(List L) 28 { 29 return L->Next == NULL; 30 } 31 32 //判断当前指针P是否指向链表最后一个元素 33 bool IsLast(Position P, List L) 34 { 35 return P->Next == NULL; 36 } 37 38 //获取链表头 39 Position Header(List L) 40 { 41 return L; 42 } 43 44 //获取位置P的下一个位置 45 Position Advance(Position P) 46 { 47 return P->Next; 48 } 49 50 //提取位置P处结构里面的值 51 ElementType Retrieve(Position P) 52 { 53 return P->Element; 54 } 55 56 //删除链表 57 void DeleteList(List L) 58 { 59 Position P, Temp; 60 P = L->Next; 61 L->Next = NULL; 62 while (P != NULL) 63 { 64 Temp = P->Next; 65 free(P); 66 P = Temp; 67 } 68 } 69 70 //打印链表 71 void PrintList(const List L) 72 { 73 Position P = Header(L); 74 if (IsEmpty(L)) 75 printf("Empty list\n"); 76 else 77 { 78 do 79 { 80 P = Advance(P); 81 printf("%d ", Retrieve(P)); 82 } while (!IsLast(P, L)); 83 printf("\n"); 84 } 85 } 86 87 //获取链表的最大值 88 ElementType Max_LinkedList(List L) 89 { 90 if (IsEmpty(L)) 91 Error("Empty List") 92 else 93 { 94 Position P = L->Next; 95 ElementType Max = P->Element; 96 while (P != NULL) 97 { 98 if (P->Element > Max) 99 Max = P->Element;100 P = P->Next;101 }102 return Max;103 }104 }105 106 //计算一个数有多少位107 int Get_Num_Length(ElementType Num)108 {109 int Length=1;110 while ((Num /= 10) != 0) Length++;111 return Length;112 }113 114 //插入元素X到位置P后面115 void Insert(ElementType X, List L, Position P)116 {117 Position TmpCell;118 TmpCell = malloc(sizeof(struct Node));119 if (TmpCell == NULL)120 FatalError("Out of Space!!!");121 TmpCell->Element = X;122 TmpCell->Next = P->Next;123 P->Next = TmpCell;124 }125 126 void MoveNode(List L1, List L2)127 {128 //将表L2中的头节点移动成为L1的尾节点 129 Position Tmp1 = L1;130 Position Tmp2;131 if (IsEmpty(L2)) exit(ListEmpty);132 while (!IsLast(Tmp1,L1))133 Tmp1 = Tmp1->Next;//使Tmp1指向L1表尾 134 Tmp2 = L2->Next;135 L2->Next = Tmp2->Next;136 Tmp1->Next = Tmp2;137 Tmp2->Next = NULL; 138 }139 140 //基数排序核心代码141 void RadixSort(List L)142 {143 int i,j,Max_Length, TmpSub;//Tmpsub存储数的个位、十位、百位144 ElementType FirstElement;//存储链表的第一个元素145 Max_Length = Get_Num_Length(Max_LinkedList(L));146 List Bucket[10];//开辟10个桶，依次为0~9147 for (i = 0; i < 10; i++) Bucket[i] = MakeEmpty(NULL);//对10桶进行初始化，每一个数组都是一个链表148 for (i = 0; i < Max_Length; i++)//开始提取每一位数的个位、十位、百位149 {150 while (!IsEmpty(L))//当L中的元素被取光了，则循环结束151 {152 FirstElement = L->Next->Element;//取出第一个节点的数据153 TmpSub = (int)(FirstElement / pow(10, i)) % 10;//依次取出个十百位数字 154 MoveNode(Bucket[TmpSub], L);//将L中的节点依次移到对应的桶中155 }156 for (j = 0; j < 10; j++) //将桶中的数再次移动到L中157 {158 while (!IsEmpty(Bucket[j])) MoveNode(L, Bucket[j]);159 }160 }161 for (i = 0; i < 10; i++) free(Bucket[i]) ;//释放掉10个桶162 }
测试函数Test_Radix_Sort.c
1 #include2 #include "RadixSort.h" 3 #include"fatal.h" 4 #include 5 6 int main() 7 { 8 int amount; 10 List L; Position P;11 L = MakeEmpty(NULL);//初始化链表12 P = L;13 if (L == NULL) Error("Out of Space!!!");14 printf("随机生成多少位数:");15 scanf_s("%d", &amount);16 srand((unsigned)time(NULL));17 for (int i = 0; i < amount; i++)18 {19 Insert(rand()%10000, L, P);20 P = Advance(P);21 }22 printf("排序前的结果：");23 PrintList(L);24 RadixSort(L);//调用排序函数排序25 printf("基数排序后的结果：");26 PrintList(L);27 }
