排序算法----基数排序（RadixSort（L））单链表智能版本

转载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:

 #include<stdio.h>

 #include<stdlib.h>

 #define Error(Str) FatalError(Str)

 #define FatalError(Str) fprintf(stderr, "%s\n", Str), exit(1);

头文件RadixSort.h：

 typedef int ElementType;

 #ifndef RADIX_SORT_H

 #define RADIX_SORT_H

 #include<stdbool.h>

 #include<assert.h>

 #define ListEmpty -2

 struct Node;

 typedef struct Node *PtrToNode;

 typedef PtrToNode List;

 typedef PtrToNode Position;

 List MakeEmpty(List L);

 bool IsEmpty(List L);

 bool IsLast(Position P, List L);

 Position Header(List L);

 Position Advance(Position P);

 ElementType Retrieve(Position P);

 void DeleteList(List L);

 void PrintList(const List L);

 ElementType Max_LinkedList(List L);//获取链表的最大值

 int Get_Num_Length(ElementType Num);//获取某个数的位数

 void Insert(ElementType X, List L, Position P);

 void MoveNode(List L1, List L2);//将表L2中的头节点移动成为L1的尾节点

 void RadixSort(List L);//最终基数排序函数，输入链表L，将L排序得到新的排序链表L

 #endif // !RADIX_SORT_H

其中RadixSort是最终排序函数，调用它即可排序。

库函数RadixSort.c

 #include "RadixSort.h"

 #include<stdio.h>

 #include<stdlib.h>

 #include<malloc.h>

 #include<math.h>

 #include"fatal.h"

 //定义结构体

 struct Node

 {

     ElementType Element;

     Position Next;

 };

 //初始化链表

 List MakeEmpty(List L)

 {

     if (L != NULL)

         DeleteList(L);//如果链表非空，则删除链表

     L = malloc(sizeof(struct Node));

     if (L == NULL)

         FatalError("Out of memory!");

     L->Next = NULL;

     return L;

 }

 //判断链表是否为空

 bool IsEmpty(List L)

 {

     return L->Next == NULL;

 }

 //判断当前指针P是否指向链表最后一个元素

 bool IsLast(Position P, List L)

 {

     return P->Next == NULL;

 }

 //获取链表头

 Position Header(List L)

 {

     return L;

 }

 //获取位置P的下一个位置

 Position Advance(Position P)

 {

     return P->Next;

 }

 //提取位置P处结构里面的值

 ElementType Retrieve(Position P)

 {

     return P->Element;

 }

 //删除链表

 void DeleteList(List L)

 {

     Position P, Temp;

     P = L->Next;

     L->Next = NULL;

     while (P != NULL)

     {

         Temp = P->Next;

         free(P);

         P = Temp;

     }

 }

 //打印链表

 void PrintList(const List L)

 {

     Position P = Header(L);

     if (IsEmpty(L))

         printf("Empty list\n");

     else

     {

         do

         {

             P = Advance(P);

             printf("%d ", Retrieve(P));

         } while (!IsLast(P, L));

         printf("\n");

     }

 }

 //获取链表的最大值

 ElementType Max_LinkedList(List L)

 {

     if (IsEmpty(L))

         Error("Empty List")

     else

     {

         Position P = L->Next;

         ElementType Max = P->Element;

         while (P != NULL)

         {

             if (P->Element > Max)

                 Max = P->Element;

             P = P->Next;

         }

         return Max;

     }

 }

 //计算一个数有多少位

 int Get_Num_Length(ElementType Num)

 {

     int Length=;

     while ((Num /= ) != ) Length++;

     return Length;

 }

 //插入元素X到位置P后面

 void Insert(ElementType X, List L, Position P)

 {

     Position  TmpCell;

     TmpCell = malloc(sizeof(struct Node));

     if (TmpCell == NULL)

         FatalError("Out of Space!!!");

     TmpCell->Element = X;

     TmpCell->Next = P->Next;

     P->Next = TmpCell;

 }

 void MoveNode(List L1, List L2)

 {

     //将表L2中的头节点移动成为L1的尾节点

     Position Tmp1 = L1;

     Position Tmp2;

     if (IsEmpty(L2)) exit(ListEmpty);

     while (!IsLast(Tmp1,L1))

         Tmp1 = Tmp1->Next;//使Tmp1指向L1表尾

     Tmp2 = L2->Next;

     L2->Next = Tmp2->Next;

     Tmp1->Next = Tmp2;

     Tmp2->Next = NULL;

 }

 //基数排序核心代码

 void RadixSort(List L)

 {

     int i,j,Max_Length, TmpSub;//Tmpsub存储数的个位、十位、百位

     ElementType FirstElement;//存储链表的第一个元素

     Max_Length = Get_Num_Length(Max_LinkedList(L));

     List Bucket[];//开辟10个桶，依次为0~9

     for (i = ; i < ; i++) Bucket[i] = MakeEmpty(NULL);//对10桶进行初始化，每一个数组都是一个链表

     for (i = ; i < Max_Length; i++)//开始提取每一位数的个位、十位、百位

     {

         while (!IsEmpty(L))//当L中的元素被取光了，则循环结束

         {

             FirstElement = L->Next->Element;//取出第一个节点的数据

             TmpSub = (int)(FirstElement / pow(, i)) % ;//依次取出个十百位数字

             MoveNode(Bucket[TmpSub], L);//将L中的节点依次移到对应的桶中

         }

         for (j = ; j < ; j++)    //将桶中的数再次移动到L中

         {

             while (!IsEmpty(Bucket[j])) MoveNode(L, Bucket[j]);

         }

     }

     for (i = ; i < ; i++) free(Bucket[i]) ;//释放掉10个桶

 }

测试函数Test_Radix_Sort.c

 #include<stdio.h>

 #include "RadixSort.h"

 #include"fatal.h"

 #include<time.h>

 int main()

 {

     int  amount;
     List L; Position P;

     L = MakeEmpty(NULL);//初始化链表

     P = L;

     if (L == NULL) Error("Out of Space!!!");

     printf("随机生成多少位数:");

     scanf_s("%d", &amount);

     srand((unsigned)time(NULL));

     for (int i = ; i < amount; i++)

     {

         Insert(rand()%, L, P);

             P = Advance(P);

     }

     printf("排序前的结果：");

     PrintList(L);

     RadixSort(L);//调用排序函数排序

     printf("基数排序后的结果：");

     PrintList(L);

 }

巴特西

排序算法----基数排序（RadixSort（L））单链表智能版本

最新文章

热门文章