基数排序原理
基数排序（以整形为例），将整形10进制按每位拆分，然后从低位到高位依次比较各个位。主要分为两个过程：
(1)分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中（比如53,个位为3，则放入3号桶中）
(2)收集，再将放置在0~9号桶中的数据按顺序放到数组中
基数排序二维数组实现
源代码
/******************************************************** *函数名称：GetNumInPos *参数说明：num 一个整形数据 * pos 表示要获得的整形的第pos位数据 *说明： 找到num的从低到高的第pos位的数据 *********************************************************/ int GetNumInPos(int num,int pos) { int temp = 1,i; for (i = 0; i < pos - 1; i++) temp *= 10; return (num / temp) % 10; } /******************************************************** *函数名称：RadixSort *参数说明：pDataArray 无序数组； * iDataNum为无序数据个数 *说明： 基数排序 *********************************************************/ #define RADIX_10 10 //整形排序 #define KEYNUM_31 10 //关键字个数，这里为整形位数 void RadixSort(int* pDataArray, int iDataNum) { int *radixArrays[RADIX_10]; //分别为0~9的序列空间 int pos,i,k,j; for (i = 0; i < 10; i++) { radixArrays[i] = (int *)malloc(sizeof(int) * (iDataNum + 1)); radixArrays[i][0] = 0; //index为0处记录这组数据的个数 } for ( pos = 1; pos <= KEYNUM_31; pos++) //从个位开始到31位 { for ( i = 0; i < iDataNum; i++) //分配过程 { int num = GetNumInPos(pDataArray[i], pos); int index = ++radixArrays[num][0]; radixArrays[num][index] = pDataArray[i]; } for ( i = 0, j =0; i < RADIX_10; i++) //收集 { for (k = 1; k <= radixArrays[i][0]; k++) pDataArray[j++] = radixArrays[i][k]; radixArrays[i][0] = 0; //复位 } } } int main(void) { int a[] = {521 ,310 ,72 ,373 ,15, 546 ,385, 856, 187, 147}; RadixSort(a,10); int i; for(i = 0;i<10;i++){ printf("%d ",a[i]); } return 0; }
转自：http://blog.csdn.net/cjf_iceking/article/details/7943609
算法理解：建立一个二维数组，第一维度表示桶序列号，第二维度存放每一位分配后的序列 大小为 d*(n+1) d为待排序序列最高位数，d有多少位就对序列n进行循环，一次循环 对一位进行排序，最后得出排序序列
基数排序单链表实现
原理：分配的桶(数组)存放单链表，每一个桶里面单链表的每个节点的内容(除头结点)存放同一个桶里面的元素，next指向下一个元素
实现代码
#ifndef __SINGLY_LINKED_LIST_H__ #define __SINGLY_LINKED_LIST_H__ typedef int ElementType; struct Node; typedef struct Node* PtrToNode; typedef PtrToNode List; typedef PtrToNode Position; struct Node { ElementType Val; Position Next; }; void CreateList(List*); void DeleteList(List); int IsEmpty(List); int IsLast(Position, List); Position Header(List); Position First(List); Position Advance(Position); Position Find(ElementType, List); ElementType GetAt(Position); void MakeEmpty(List); void Delete(ElementType, List); void Insert(ElementType, Position, List); void InsertFront(ElementType, List); void InsertBack(ElementType, List); #endif
#include <stdlib.h> #include "SinglyLinkedList.h" void CreateList(List* L) { PtrToNode pHeader = (struct Node*)malloc(sizeof(struct Node)); pHeader->Next = NULL; *L = pHeader; } void DeleteList(List L) { MakeEmpty(L); free(L); } int IsEmpty(List L) { return L->Next == NULL; } int IsLast(Position P, List L) { return P->Next == NULL; } Position Header(List L) { return L; } Position First(List L) { return L->Next; } Position Advance(Position P) { return P->Next; } Position Find(ElementType X, List L) { Position p = L->Next; while(p != NULL && p->Val != X) { p = p->Next; } return p; } ElementType GetAt(Position P) { return P->Val; } void MakeEmpty(List L) { Position p, tmp; p = L->Next; while(p != NULL) { tmp = p->Next; free(p); p = NULL; p = tmp; } L->Next = NULL; } void Delete(ElementType X, List L) { Position p, tmp; p = L; while(p->Next != NULL && p->Next->Val != X) { p = p->Next; } if(!IsLast(p, L)) { tmp = p->Next; p->Next = tmp->Next; free(tmp); tmp = NULL; // 错误示范： //free(p->Next); //p->Next = tmp->Next; } } void Insert(ElementType X, Position P, List L) { PtrToNode pNode; pNode = (struct Node*)malloc(sizeof(struct Node)); pNode->Val = X; pNode->Next = P->Next; P->Next = pNode; } void InsertFront(ElementType X, List L) { Position pos; PtrToNode pNode; pos = L; pNode = (struct Node*)malloc(sizeof(struct Node)); pNode->Val = X; pNode->Next = pos->Next; pos->Next = pNode; } void InsertBack(ElementType X, List L) { Position pos; PtrToNode pNode; // move to tail pos = L; while(pos->Next != NULL) pos = pos->Next; pNode = (struct Node*)malloc(sizeof(struct Node)); pNode->Val = X; pNode->Next = pos->Next; pos->Next = pNode; }
#include <stdio.h> #include <stdlib.h> #include "SinglyLinkedList.h" #define N 10 // 排序的数个数 #define B 10 // 桶数，即基数 #define P 3 // 位数 void RadixSort(int arr[]); int GetDigit(int x, int y); void PrintArray(int arr[], int size); int main() { int i; //int arr[N]; int arr[N] = {64, 8, 216, 512, 27, 729, 0, 1, 343, 125}; // 10, 3 //int arr[N] = {64, 8, 216, 512, 125, 729, 0, 729, 343, 125}; //int arr[N] = {12, 58, 37, 64, 52, 36, 99, 63, 18, 9, 20, 88, 47}; // 13, 2 printf("before sort: "); PrintArray(arr, N); RadixSort(arr); printf("after sort: "); PrintArray(arr, N); system("PAUSE"); return 0; } void RadixSort(int arr[]) { int i, j, k, digit; Position pos; List bucket[B]; // 创建桶 for(i=0; i<B; ++i) CreateList(&bucket[i]); // 从低位到高位循环每一位数字 for(i=0; i<P; ++i) { // 将桶置空 for(j=0; j<B; ++j) MakeEmpty(bucket[j]); // 根据当前位上的数字，将之放入对应桶中。并注意顺序（后进的放在后面） for(j=0; j<N; ++j) { digit = GetDigit(arr[j], i); InsertBack(arr[j], bucket[digit]); } k = 0; // 将每趟排序后的结果存回arr for(j=0; j<B; ++j) { pos = First(bucket[j]); while(pos != NULL) { arr[k++] = pos->Val; pos = pos->Next; } } } for(i=0; i<B; ++i) DeleteList(bucket[i]); } // 取整数x的倒数第y位数字，y从0开始 int GetDigit(int x, int y) { int i, t = 1; for(i=0; i<=y; ++i) t *= 10; return (x % t) / (t / 10); } void PrintArray(int arr[], int size) { int i; for(i=0; i<size; ++i) { printf("%d ", arr[i]); } printf(" "); }
数组实现和链表实现的优缺点：数组浪费空间，链表按需生成空间。