10.3.1 桶排序 (先:桶小-O(M+N)-线性排序)

桶排序之前的算法一个共同特点:仅仅基于比较大小来决定元素位置的，这些算法的最坏/下界时间复杂度是O(NLogN)，不管运行多坏，总能制造出一个最坏的情况，让算法以最快的方法跑，也只能跑到O(NLogN)，有没有可能更快呢？也就是除了比较之外，还能干点别的事，这就是基数排序，在基数排序之前，需要先学习桶排序。

这个N可以很大，但是这里的成绩只有101个不同的值，基于此数据的特点，可以在线性时间内把学生按照成绩排序。

可以把每个成绩值构造成一个桶，取名叫count数组，数组中每个元素是一个指针，开始被初始化为一个空链表的头指针，有了101个空链表，对应了101个空的桶。

第一个学生考了88分，进来找到88这个桶，把此学生的信息插到这个链表的表头。

根据grade成绩的值，找count对应的链表，把成绩从小到大输出。

那么此算法的时间复杂度受N和M的影响，把N个学生的信息，每一次插入表头是常数倍的时间，O(N)的时间复杂度，输出时需要扫描每一个桶，一共有M个桶。

当M非常小时，比如4个万学生只有101个桶，这就是一种线性的算法了。

10.3.2 基数排序 (后:桶大-O(P(N+B))-次位优先LSD)

此时桶大，需要排序的整数很少，就不可能在线性时间内做排序了，此排序方法叫基数排序。

这里的0-999最多3位数，那么每一位数有10种可能。

比如:二进制的基数是2，八进制的基数是8，十进制的基数是10。

对输入序列执行”次位优先”策略，简称LSD算法。

比如216，个位数6是最次位，百位数2是主位，那么这里的比较先从个位数开始。

这里的基数是10，建立10个桶。

红颜色:按个位排序收集。

紫颜色:按十位排序收集。

蓝颜色:按百位排序收集。

每一趟颜色的收集，收集过程就是扫描每一个桶，每一个桶里的元素按照顺序用一个链表串起来。

比如按照十位数排序的这趟Pass2收集过程，序列中的0、1、8没有十位数，默认十位数是0，所以放在0这列。

时间复杂度T。

每一趟的排序一共经历了P趟排序。

在每一趟排序中，要把N个数全部都收集起来，然后分配，分配的过程跟桶的个数B是有关的。

执行趟数P*(桶数B+整数元素数量N(10))，就是整体的时间复杂度，比正常排序的时间复杂度要好。

时间复杂度的好坏，取决于基数桶数B多大，P实际上是LogB(还有桶中链表中的实际元素数量M)。

如果桶数B和元素数量N的数量级相比，如果桶数B非常小的话，那么那么整个算法是线性复杂度的。

10.3.3 多关键字的排序 (基数排序处理-主/次位优先)

比如一副扑克牌是按照2种关键字排序的。

花色:主关键字，理解成上一章节”次未排序”中处理整数中的高位。

面值:次关键字，整体上是按照四种花色排序的，在每一种花色内部，按照面值排序，理解成上一章节”次未排序”中处理整数中的低位。

主位优先MSD(慢)

主位优先简称MSD，按照主位根据四个花色/主关键字建立四个桶，把所有的50多张牌一张张的放在对应的花色桶中，在每个桶内分别排序，最后合并结果。

这里的时间复杂度比完成的看成一个待排数组要稍微好些，但是这里还是不如”次未排序”。

次位优先LSD(快)

次位优先简称LSD，按照次位根据素有的面值/次位关键字来建立13个桶，把所有的50多张牌一张张的放在对应的面值的桶中，合并结果，然后再为花色建4个桶，接下来只需要从上到下把这些牌按照花色放到对应的花色桶中，最后收集并把结果合并即可，这样就得到了最后的有序序列，要注意这里并不用排序，时间复杂度要比”主位优先”要快。

源码:基数排序-主位优先MSD

#include<stdio.h>
/*
排序-基数排序-主位优先
*/
int main(void){
	return 0;
}

/* 假设元素最多有MaxDigit个关键字，基数全是同样的Radix */
#define MaxDigit 4
#define Radix 10

/* 桶元素结点 */
typedef struct Node *PtrToNode;
struct Node{
	int key;
	PtrToNode next;
};

/* 桶头结点 */
struct HeadNode{
	PtrToNode head, tail;
};

typedef struct HeadNode Bucket[Radix];

/* 默认次位D=1, 主位D<=MaxDigit */
int GetDigit(int X, int D){
	int d, i;
	for(i = 1; i <= D; i++){
		d = X % Radix;
		X /= Radix;
	}
	return d;
}


/* 统一函数接口 */
void MSDRadixSort(ElementType A[], int N){
	MSD(A, 0, N - 1, MaxDigit);
}


/* 核心递归函数: 对A[L]...A[R]的第D位数进行排序 */
void MSD(ElementType A[], int L, int R, int 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;
	}
	/* 将原始序列逆序存入初始链表List */
	for(i = L; i <= R; i++){
		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记录当前要处理的A[]的左右端下标 */
	i = j = L;
	/* 对于每个桶 */
	for(Di = 0; Di < Radix; Di++){
		/* 将非空的桶整桶倒入A[], 递归排序 */
		if(B[Di].head){
			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);
			/* 为下一个桶对应的A[]左端 */
			i = j;
		}
	}

}

源码:基数排序-次位优先LSD

#include<stdio.h>
/*
排序-基数排序-次位优先
*/
int main(void){
	return 0;
}

/* 假设元素最多有MaxDigit个关键字，基数全是同样的Radix */
#define MaxDigit 4
#define Radix 10

/* 桶元素结点 */
typedef struct Node *PtrToNode;
struct Node{
	int key;
	PtrToNode next
};

/* 桶头结点 */
struct HeadNode{
	PtrToNode head,tail;
};

typedef struct HeadNode Bucket[Radix];

/* 默认次位D=1, 主位D<=MaxDigit */
int GetDigit(int X, int D){
	int d, i;
	for(i = 1; i <= D; i++){
		d = X % Radix;
		X /= Radix;
	}
	return d;
}

/* 基数排序 - 次位优先 */
void LSDRadixSort(ElementType 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;
	}
	/* 将原始序列逆序存入初始链表List */
	for(i = 0; i < N; i++){
		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;
		/* 将每个桶的元素顺序收集入List */
		for(Di = Radix - 1; Di >= 0; Di--){
			/* 如果桶不为空 */
			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);
	}

}