桶（箱子）排序

桶排序是基于链表的，相邻的桶之间和桶中相邻的元素之间皆用链表相连接，可以把它想象成一个矩阵。
用一个例子来说明桶排序。

假设有一个链表，其中的元素需要进行排序，元素为ABCDEFGHIJ,其值依次为2454304344，如A2->B4->C5->D4->E3->F0->G4->H3->I4->J4。若根据值进行排序。首先我们定义5个桶bin[5]用来装这10个元素，然后依次遍历每个元素，根据其值将其放入对应的桶中，及bin[0]=F，bin[1]=NULL，bin[2]=A，bin[3]={E，H，J},bin[4]={B，D，G，I},bin[5]=C。最后我们根据bin[0]~bin[5]桶的顺序重新排列元素，及FAEHJBDGIC。至此桶排序完成。

桶排序时需要先删除原先各个节点的后驱结点指针，然后再将各个节点分配至各个桶中，把每一个箱子中节点在用链表串联起来，再根据桶的顺序重新排列节点。
接下来是代码

void binSort(linklist<linknode> &chain, int range) {

	linklist<linknode> *bin = new linklist<linknode>[range + 1];
	int numberofelement = chain.size();

	for (int i = 0; i < numberofelement; i++) {
		linknode node = chain.get(0);
		chain.erase(0);
		bin[node.value].insert(0, node);
	}
	for(int i=range,i>=0;i++)
		while (!bin[i].empty())
		{
			linknode node = bin[i].get(0);
			bin[i].erase(0);
			chain.insert(0, node);
		}
	delete[]bin;
}

代码思路：bin数组下标为0~range，所以大小为range+1。第一个for循环遍历原链表中每个元素并分配至相应的桶中，利用get函数得到数组第一个元素并保存到node节点中，erase函数对原链表元素进行删除，再利用insert函数将get到的元素插入到各个桶中。至此，元素在桶中与桶之间有序。第二个for循环遍历桶及桶中元素，再次利用get、earse和insert函数依次将排序后的元素重返至原链表中。

在数据结构黑皮书中还给出了桶排序作为链表chain成员函数的具体实现，代码也很有意思，可以借鉴。

template<class T>
void chain<T>::binSort(int range) {
	chainNode<T> **bottom, **top;//指向指针的指针，第一个指针为桶内指针数组，第二个指针为桶间指针数组
	bottom = new chainNode<T>*[range + 1];
	top = new chainNode<T>*[range + 1];
	//bottom数组必须初始化
	for (int i = 0; i < range; i++) {
		bottom[i] = NULL;
	}
	//将原链表节点分配到箱中
	for (; firstnode != NULL; firstnode = firstnode->next) {
		int thebin = firstnode.value;
		if (bottom[thebin] == NUll)//若箱子为空
			bottom[thebin] = top[thebin] = firstnode;
		else {//箱子不空时仅改变top指针
			top[thebin]->next = firstnode;
			top[thebin] = firstnode;
		}
	}
	//把箱子中的节点收集到有序链表
	chainNode<T>*y = NULL;
	for (int i = 0; i <= range; i++) {
		if (bottom[i] != NULL) {
			if (y == NULL)//分配第一个节点
				firstnode = bottom[i];
			else
			//因为桶内已为有序链表，所以只需要改变bottom和top指针使不同桶链表首尾相连
				y->next = bottom[i];
			y = top[i];
		}
	}
}

桶排序时间复杂度为O(n+range)，观察代码可发现桶排序不会改变值相同的节点的相对次序，所以是一种稳定排序。

基数排序

基数排序是桶排序的扩展，与桶排序不同，基数排序并不对数进行直接排序，而是把数按照某种基数radix分解为数字，然后对数字进行排序。如基数10可以把十进制数928分解为9、2、8，基数60可以把十进制数3725分解为1、2、5。这就是基数排序。

用一个例题来具体说明。假设对0~999的10个整数进行排序，若使用桶排序，则range=1000，这时候需要初始化1000个步骤，节点分配需要10个步骤，析构又需要1000个步骤，总共2010个步骤。

而采用基数排序，将基数r=10。
假设10个数字分别为：216->521->425->116->91->515->124->34->96->24
首先按照最低位(个位）对链表进行排序，结果为：521->91->124->34->24->425->515->216->116->96
接着按照第二位(十位）对链表进行排序，结果为：515->216->116->521->124->24->425->34->91->96
最后按照第三位(百位）对链表进行排序，结果为：24->34->91->96->116->124->216->425->515->521
至此，基数排序完成。

基数排序是在桶排序的基础上发展而来，是一种稳定的排序，时间复杂度为O(cn)=O(n)，c为常量。