基数排序是通过“分配”和“收集”过程来实现排序

（1）假设有欲排数据序列如下所示：

73  22  93  43  55  14  28  65  39  81

首先根据个位数的数值，在遍历数据时将它们各自分配到编号0至9的桶（个位数值与桶号一一对应）中。

分配结果（逻辑想象）如下图所示：

分配结束后。接下来将所有桶中所盛数据按照桶号由小到大（桶中由顶至底）依次重新收集串起来，得到如下仍然无序的数据序列：

81  22  73  93  43  14  55  65  28  39

接着，再进行一次分配，这次根据十位数值来分配（原理同上），分配结果（逻辑想象）如下图所示：

分配结束后。接下来再将所有桶中所盛的数据（原理同上）依次重新收集串接起来，得到如下的数据序列：

14  22  28  39  43  55  65  73  81  93

观察可以看到，此时原无序数据序列已经排序完毕。如果排序的数据序列有三位数以上的数据，则重复进行以上的动作直至最高位数为止。

代码 （C语言实现）

1 #ifndef __SINGLY_LINKED_LIST_H__  2 #define __SINGLY_LINKED_LIST_H__  3   4 typedef int ElementType;  5 struct Node;  6 typedef struct Node* PtrToNode;  7 typedef PtrToNode List;  8 typedef PtrToNode Position;  9  10 struct Node 11 { 12     ElementType Val; 13     Position Next; 14 }; 15 void  CreateList(List*); 16 void  DeleteList(List); 17 int  IsEmpty(List); 18 int  IsLast(Position, List); 19 Position  Header(List); 20 Position  First(List); 21 Position  Advance(Position); 22 Position  Find(ElementType, List); 23 ElementType  GetAt(Position); 24 void  MakeEmpty(List); 25 void  Delete(ElementType, List); 26 void  Insert(ElementType, Position, List); 27 void  InsertFront(ElementType, List); 28 void  InsertBack(ElementType, List); 29  30 #endif 31 void  CreateList(List* L) 32 { 33     PtrToNode pHeader = (struct Node*)malloc(sizeof(struct Node)); 34     pHeader->Next = NULL; 35     *L = pHeader; 36 } 37  38 void  DeleteList(List L) 39 { 40     MakeEmpty(L); 41     free(L); 42 } 43  44 int  IsEmpty(List L) 45 { 46     return L->Next == NULL; 47 } 48  49 int  IsLast(Position P, List L) 50 { 51     return P->Next == NULL; 52 } 53  54 Position  Header(List L) 55 { 56     return L; 57 } 58  59 Position  First(List L) 60 { 61     return L->Next; 62 } 63  64 Position  Advance(Position P) 65 { 66     return P->Next; 67 } 68  69 Position  Find(ElementType X, List L) 70 { 71     Position p = L->Next; 72     while(p != NULL && p->Val != X) 73     { 74         p = p->Next; 75     } 76     return p; 77 } 78  79 ElementType  GetAt(Position P) 80 { 81     return P->Val; 82 } 83  84 void MakeEmpty(List L) 85 { 86     Position p, tmp; 87     p = L->Next; 88     while(p != NULL) 89     { 90         tmp = p->Next; 91         free(p); 92         p = NULL; 93         p = tmp; 94     } 95     L->Next = NULL; 96 } 97  98 void  Delete(ElementType X, List L) 99 {100     Position p, tmp;101     p = L;102     while(p->Next != NULL && p->Next->Val != X)103     {104         p = p->Next;105     }106     if(!IsLast(p, L))107     {108         tmp = p->Next;109         p->Next = tmp->Next;110         free(tmp);111         tmp = NULL;112         // 错误示范：113         //free(p->Next);114         //p->Next = tmp->Next;115     }116 }117 118 void  Insert(ElementType X, Position P, List L)119 {120     PtrToNode pNode;121     pNode = (struct Node*)malloc(sizeof(struct Node));122     pNode->Val = X;123     pNode->Next = P->Next;124     P->Next = pNode;125 }126 127 void  InsertFront(ElementType X, List L)128 {129     Position pos;130     PtrToNode pNode;131     pos = L;132     pNode = (struct Node*)malloc(sizeof(struct Node));133     pNode->Val = X;134     pNode->Next = pos->Next;135     pos->Next = pNode;136 }137 138 void  InsertBack(ElementType X, List L)139 {140     Position pos;141     PtrToNode pNode;142     // move to tail143     pos = L;144     while(pos->Next != NULL)145         pos = pos->Next;146     pNode = (struct Node*)malloc(sizeof(struct Node));147     pNode->Val = X;148     pNode->Next = pos->Next;149     pos->Next = pNode;150 }

 

1 #include 
     
       2 #include 
      
        3 #include "SinglyLinkedList.h" 4  5 #define N 10    // 排序的数个数 6 #define B 10    // 桶数，即基数 7 #define P 3        // 位数 8  9 void RadixSort(int arr[]);10 int GetDigit(int x, int y);11 void PrintArray(int arr[], int size);12 13 int main()14 {15     int i;16     //int arr[N];17     int arr[N] = {
    64, 8, 216, 512, 27, 729, 0, 1, 343, 125};    // 10, 318     //int arr[N] = {64, 8, 216, 512, 125, 729, 0, 729, 343, 125};19     //int arr[N] = {12, 58, 37, 64, 52, 36, 99, 63, 18, 9, 20, 88, 47}; // 13, 220 21     printf("before sort: ");22     PrintArray(arr, N);23 24     RadixSort(arr);25 26     printf("after sort: ");27     PrintArray(arr, N);28 29     system("PAUSE");30     return 0;31 }32 33 void RadixSort(int arr[])34 {35     int i, j, k, digit;36     Position pos;37     List bucket[B];38 39     // 创建桶40     for(i=0; i
       
        Val;60                 pos = pos->Next;61             }62         }63     }64 65     for(i=0; i