排序演算法----基數排序（RadixSort（L，max））單鏈表版本

轉載http://blog.csdn.net/Shayabean_/article/details/44885917博客

先說說基數排序的思想：   

基數排序是非比較型的排序演算法，其原理是將整數按位數切割成不同的數字，然後按每個位數分別比較。

將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。在每一次排序中，按照當前位把數組元素放到對應        

的桶當中，然後把桶0到桶9中的元素按先進先出的方式放回數組中。這樣從最低位排序一直到最高位排序完成以後, 數列就變成一個有序序列。

這個版本的基數排序RadixSort（L，max）較RadixSort（L）不同的是需要輸入待排序列最大數的位數。因為RadixSort（L）最大數位在程式中已經計算過了，因為需要計算最大數，所以需要對待排鏈表最開始迴圈一次，所以RadixSort（L，max）速度比RadixSort（L）稍快。

這篇博客包括4個文件，兩個頭文件RadixSort.h和fatal.h，一個庫函數RadixSort.c，和一個測試文件Test_Radix_Sort.c

頭文件fatal.h:

1 #include<stdio.h>
2 #include<stdlib.h>
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 #include<stdbool.h>
 6 #define ListEmpty -2
 7 
 8 struct Node;
 9 typedef struct Node *PtrToNode;
10 typedef PtrToNode List;
11 typedef PtrToNode Position;
12 
13 List MakeEmpty(List L);
14 bool IsEmpty(List L);
15 bool IsLast(Position P, List L);
16 Position Header(List L);
17 Position Advance(Position P);
18 ElementType Retrieve(Position P);
19 void DeleteList(List L);
20 void PrintList(const List L);
21 void Insert(ElementType X, List L, Position P);
22 void MoveNode(List L1, List L2);//將表L2中的頭節點移動成為L1的尾節點
23 void RadixSort(List L,int max);//最終基數排序函數，輸入鏈表L，將L排序得到新的排序鏈表L,其中max是待排元素最高有多少位
24 #endif // !RADIX_SORT_H

其中RadixSort是最終排序函數，調用它即可排序。

庫函數RadixSort.c

  1 #include "RadixSort.h"
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<malloc.h>
  5 #include<math.h>
  6 #include"fatal.h"
  7 struct Node
  8 {
  9     ElementType Element;
 10     Position Next;
 11 };
 12 
 13 //初始化鏈表
 14 List MakeEmpty(List L)
 15 {
 16     if (L != NULL)
 17         DeleteList(L);//如果鏈表非空，則刪除鏈表
 18     L = malloc(sizeof(struct Node));
 19     if (L == NULL)
 20         FatalError("Out of memory!");
 21     L->Next = NULL;
 22     return L;
 23 }
 24 //判斷鏈表是否為空
 25 bool IsEmpty(List L)
 26 {
 27     return L->Next == NULL;
 28 }
 29 
 30 //判斷當前指針P是否指向鏈表最後一個元素
 31 bool IsLast(Position P, List L)
 32 {
 33     return P->Next == NULL;
 34 }
 35 
 36 //獲取鏈表頭
 37 Position Header(List L)
 38 {
 39     return L;
 40 }
 41 
 42 //獲取位置P的下一個位置
 43 Position Advance(Position P)
 44 {
 45     return P->Next;
 46 }
 47 
 48 //提取位置P處結構裡面的值
 49 ElementType Retrieve(Position P)
 50 {
 51     return P->Element;
 52 }
 53 
 54 //刪除鏈表
 55 void DeleteList(List L)
 56 {
 57     Position P, Temp;
 58     P = L->Next;
 59     L->Next = NULL;
 60     while (P != NULL)
 61     {
 62         Temp = P->Next;
 63         free(P);
 64         P = Temp;
 65     }
 66 }
 67 
 68 //列印鏈表
 69 void PrintList(const List L)
 70 {
 71     Position P = Header(L);
 72     if (IsEmpty(L))
 73         printf("Empty list\n");
 74     else
 75     {
 76         do
 77         {
 78             P = Advance(P);
 79             printf("%d ", Retrieve(P));
 80         } while (!IsLast(P, L));
 81         printf("\n");
 82     }
 83 }
 84 
 85 //插入元素X到位置P後面
 86 void Insert(ElementType X, List L, Position P)
 87 {
 88     Position  TmpCell;
 89     TmpCell = malloc(sizeof(struct Node));
 90     if (TmpCell == NULL)
 91         FatalError("Out of Space!!!");
 92     TmpCell->Element = X;
 93     TmpCell->Next = P->Next;
 94     P->Next = TmpCell;
 95 }
 96 
 97 void MoveNode(List L1, List L2)
 98 {
 99     //將表L2中的頭節點移動成為L1的尾節點 
100     Position Tmp1 = L1;
101     Position Tmp2;
102     if (IsEmpty(L2)) exit(ListEmpty);
103     while (!IsLast(Tmp1,L1))
104         Tmp1 = Tmp1->Next;//使Tmp1指向L1表尾 
105     Tmp2 = L2->Next;
106     L2->Next = Tmp2->Next;
107     Tmp1->Next = Tmp2;
108     Tmp2->Next = NULL;    
109 }
110 
111 void RadixSort(List L,int max)
112 {
113     //if (IsEmpty(L)) return L; //如果要排序的鏈表L是空表，則不排序
114     int i,j, TmpSub;//Tmpsub存儲數的個位、十位、百位
115     ElementType FirstElement;//存儲鏈表的第一個元素
116 
117     List Bucket[10];//開闢10個桶，依次為0~9
118     for (i = 0; i < 10; i++) Bucket[i] = MakeEmpty(NULL);//對10桶進行初始化，每一個數組都是一個鏈表
119     for (i = 0; i < max; i++)//開始提取每一位數的個位、十位、百位
120     {
121         while (!IsEmpty(L))//當L中的元素被取光了，則迴圈結束
122         {
123             FirstElement = L->Next->Element;//取出第一個節點的數據
124             TmpSub = (int)(FirstElement / pow(10, i)) % 10;//依次取出個十百位數字 
125             MoveNode(Bucket[TmpSub], L);//將L中的節點依次移到對應的桶中
126         }
127         for (j = 0; j < 10; j++)    //將桶中的數再次移動到L中
128         {
129             while (!IsEmpty(Bucket[j])) MoveNode(L, Bucket[j]);
130         }
131     }
132     for (i = 0; i < 10; i++) free(Bucket[i]) ;//釋放掉10個桶
133 }

測試函數Test_Radix_Sort.c

 1 #include<stdio.h>
 2 #include "RadixSort.h"
 3 #include"fatal.h"
 4 #include<time.h>
 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,4);//調用排序函數排序
25     printf("基數排序後的結果：");
26     PrintList(L);
27 }