排序算法1——图解冒泡排序及其实现（三种方法，基于模板及函数指针）
排序算法2——图解简单选择排序及其实现
排序算法3——图解直接插入排序以及折半（二分）插入排序及其实现
排序算法4——图解希尔排序及其实现
排序算法5——图解堆排序及其实现
排序算法6——图解归并排序及其递归与非递归实现
排序算法7——图解快速排序（两种主元选择方法）以及CUTOFF时间测试
排序算法8——图解表排序
排序算法9——图解桶排序及其实现
排序算法10——图解基数排序（次位优先法LSD和主位优先法MSD）
排序算法——比较与总结
基数排序的概念
基数排序是桶排序的一种推广。
给定N个记录，每个记录的关键字为一整数，取值范围在0到M之间
之前提到的桶排序是在N远大于M的情况下使用的。
若如果M比N大很多，这时桶排序就需要M个桶，会造成巨大的
空间浪费
。
而以R为基数对关键字进行分解以后，就只需要R个桶就可以了。
例如：
对于数字826
如果根据基数10来分解，可以得到8、2、6三个关键字，
其中8是最主位关键字，6是最次位关键字
如果根据基数16来分解，可以得到3、3、A三个关键字，
其中3是最主位关键字，A是最次位关键字
次位优先法LSD
对于给定范围在0-999之间的10个关键字
{64，8，216，512，27，729，0，1，343，125}
① 先为最次位关键字建立桶（10个），将关键字按最次位分别放到10个桶中
② 然后将①中得到的序列按十位放到相应的桶里
③ 做一次收集，扫描每一个桶，收集到一个链表中串起来
④ 将③中得到的序列按最主位放到桶中
⑤ 最后做一次收集，这样就得到一个有序的序列了
对N个关键字用R个桶进行基数排序时，其时间复杂度为
O（D（N+R ））
其中，
D为分配收集的次数，也就是关键字按基数分解后的位数
当记录的
个数N
与
桶的个数R
基本
是一个数量级
时，基数排序可以达到
线性复杂度
。
基数排序用链表实现的好处：不需要将记录进行物理移动，对于大型记录的排序是有利的
而代价是：需要
O（N）
额外空间存放指针
测试结果及代码
1）次位优先法LSD
#include <iostream>
/* 基数排序 - 次位优先 */
/* 假设元素最多有MaxDigit个关键字，基数全是同样的Radix */
#define MaxDigit 4
#define Radix 10
typedef int ElemType;
/* 桶元素结点 */
typedef struct Node *PtrToNode;
struct Node {
int key;
PtrToNode next;
};
/* 桶头结点 */
struct HeadNode {
PtrToNode head, tail;
};
typedef struct HeadNode Bucket[Radix];
int GetDigit(int X, int D)
{ /* 默认次位D=1, 主位D<=MaxDigit */
int d, i;
for (i = 1; i <= D; i++) {
d = X % Radix;
X /= Radix;
}
return d;
}
void LSDRadixSort(ElemType A[], int N)
{ /* 基数排序 - 次位优先 */
int D, Di, i;
Bucket B;
PtrToNode tmp, p, List = NULL;
for (i = 0; i<Radix; i++) /* 初始化每个桶为空链表 */
B[i].head = B[i].tail = NULL;
for (i = 0; i<N; i++) { /* 将原始序列逆序存入初始链表List */
tmp = (PtrToNode)malloc(sizeof(struct Node));
tmp->key = A[i];
tmp->next = List;
List = tmp;
}
/* 下面开始排序 */
for (D = 1; D <= MaxDigit; D++) { /* 对数据的每一位循环处理 */
/* 下面是分配的过程 */
p = List;
while (p) {
Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
/* 从List中摘除 */
tmp = p; p = p->next;
/* 插入B[Di]号桶尾 */
tmp->next = NULL;
if (B[Di].head == NULL)
B[Di].head = B[Di].tail = tmp;
else {
B[Di].tail->next = tmp;
B[Di].tail = tmp;
}
}
/* 下面是收集的过程 */
List = NULL;
for (Di = Radix - 1; Di >= 0; Di--) { /* 将每个桶的元素顺序收集入List */
if (B[Di].head) { /* 如果桶不为空 */
/* 整桶插入List表头 */
B[Di].tail->next = List;
List = B[Di].head;
B[Di].head = B[Di].tail = NULL; /* 清空桶 */
}
}
}
/* 将List倒入A[]并释放空间 */
for (i = 0; i<N; i++) {
tmp = List;
List = List->next;
A[i] = tmp->key;
free(tmp);
}
}
template<class T>
void ArrShow(T *A, int length) {
for (int i = 0; i < length; ++i) {
std::cout << A[i] << " ";
}
puts("\n");
}
int main(int argc, char *argv[]) {
int test[9] = { 1, 2, 11, 66, 53, 53, 54, 16, 4 };
ArrShow(test, 9);
puts("LSDRadixSort : ");
LSDRadixSort(test, 9);
ArrShow(test, 9);
return 0;
}
2）主位优先法MSD
#include <iostream>
/* 基数排序 - 主位优先 */
/* 假设元素最多有MaxDigit个关键字，基数全是同样的Radix */
#define MaxDigit 4
#define Radix 10
typedef int ElemType;
/* 桶元素结点 */
typedef struct Node *PtrToNode;
struct Node{
int key;
PtrToNode next;
};
/* 桶头结点 */
struct HeadNode {
PtrToNode head, tail;
};
typedef struct HeadNode Bucket[Radix];
int GetDigit(int X, int D)
{ /* 默认次位D=1, 主位D<=MaxDigit */
int d, i;
for (i = 1; i <= D; i++) {
d = X%Radix;
X /= Radix;
}
return d;
}
void MSD(ElemType A[], int L, int R, int D)
{ /* 核心递归函数: 对A[L]...A[R]的第D位数进行排序 */
int Di, i, j;
Bucket B;
PtrToNode tmp, p, List = NULL;
if (D == 0) return; /* 递归终止条件 */
for (i = 0; i<Radix; i++) /* 初始化每个桶为空链表 */
B[i].head = B[i].tail = NULL;
for (i = L; i <= R; i++) { /* 将原始序列逆序存入初始链表List */
tmp = (PtrToNode)malloc(sizeof(struct Node));
tmp->key = A[i];
tmp->next = List;
List = tmp;
}
/* 下面是分配的过程 */
p = List;
while (p) {
Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
/* 从List中摘除 */
tmp = p; p = p->next;
/* 插入B[Di]号桶 */
if (B[Di].head == NULL) B[Di].tail = tmp;
tmp->next = B[Di].head;
B[Di].head = tmp;
}
/* 下面是收集的过程 */
i = j = L; /* i, j记录当前要处理的A[]的左右端下标 */
for (Di = 0; Di<Radix; Di++) { /* 对于每个桶 */
if (B[Di].head) { /* 将非空的桶整桶倒入A[], 递归排序 */
p = B[Di].head;
while (p) {
tmp = p;
p = p->next;
A[j++] = tmp->key;
free(tmp);
}
/* 递归对该桶数据排序, 位数减1 */
MSD(A, i, j - 1, D - 1);
i = j; /* 为下一个桶对应的A[]左端 */
}
}
}
void MSDRadixSort(ElemType A[], int N)
{ /* 统一接口 */
MSD(A, 0, N - 1, MaxDigit);
}
template<class T>
void ArrShow(T *A, int length) {
for (int i = 0; i < length; ++i) {
std::cout << A[i] << " ";
}
puts("\n");
}
int main(int argc, char *argv[]) {
int test[9] = { 1, 2, 11, 66, 53, 53, 54, 16, 4 };
ArrShow(test, 9);
puts("MSDRadixSort : ");
MSDRadixSort(test, 9);
ArrShow(test, 9);
return 0;
}