箱子排序
实现
把每个箱子用一个链表实现。在进行节点分配之前，每个箱子都是空的。
基本思想
1.从与排序链表的头部开始，逐个删除节点，并把它放到合适的箱子链表的头部
2.收集并连接每个箱子中的节点，产生有序的链表
两种实现
第一种实现：
只使用一个箱子数组
//range 是分数的范围
void BinSort(Chain<Node>& X,int range)
{//按分数排序
int len = X.Length();
Node x;
Chain<Node> *bin;//bin是所有的箱子
bin = new Chain<Node> [range + 1];
//分配到每个箱子中
for (int i = 1;i<=len;i++)
{
X.Delete(1,x);
bin[x.score].Insert(0,x);
}
//从箱子中收集各元素(从后向前收集)
for (int j = range;j >= 0;j--)
{
while (!bin[j].Empty())
{
bin[j].Delete(1,x);
X.Insert(0,x);
}
}
delete [] bin;
}
第二种实现
直接写成Chain的成员函数，使用两个箱子数组，一个指向头，一个指向尾。
template <class T>
void Chain<T>::BinSort(int range)
{//按分数排序
int b;//箱子索引号
bottom = new ChainNode<T>* [range +1];
top = new ChainNode<T> * [range +1];
for (b=0;b<=range;b++)//初始化
{
bottom[b] = 0;
}
//把节点分配到各个箱子中
for (; first;first = first.link)//添加到箱子中
{
b = first.data;
if (bottom[b])//箱子非空
{
top[b].link = first;
top[b] = first;
}
else //箱子为空
bottom[b] = top[b] = first;
}
//收集各箱子中的元素
ChainNode<T> *y =0;//暂存箱子的顶部指针
for (b=0;b<=range;b++)
{
if (bottom[b])//箱子非空
{
if(y)//不是第一个非空的箱子
{
y.link = bottom[b];
}
else//第一个非空的箱子
first = bottomo[b];
y = top[b];
}
}
if (y) y.link = 0;
delete [] top;
delete [] bottom;
}