箱排序以及其基数排序
这两个新的排序方式，我们是建立在链表的情况下推出来
极大的程度上减少了算法问题的复杂度
箱排序（算法描述）
假设有一组长度为N的待排关键字序列K[1…n]。
首先将这个序列划分成M个的子区间(桶)。
然后基于某种映射函数 ，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。
对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。
然后依次枚举输出B[0]…B[M]中的全部内容即是一个有序序列。
为保证排序是稳定的，分配过程中装箱及收集过程中的连接必须按先进先出原则进行
（1） 实现方法一
每个箱子设为一个链队列。当一记录装入某箱子时，应做人队操作将其插入该箱子尾部；而收集过程则是对箱子做出队操作，依次将出队的记录放到输出序列中。
（2） 实现方法二
若输入的待排序记录是以链表形式给出时，出队操作可简化为是将整个箱子链表链接到输出链表的尾部。这只需要修改输出链表的尾结点中的指针域，令其指向箱子链表的头，然后修改输出链表的尾指针，令其指向箱子链表的尾即可。
iostream。out可以通过operator out（const &stud_node*p）
重载函数也是可以的
这个是链式表的箱子 分类，从他的排序过程看，一开始的含有数字并且和链接点，第二步开始通过相同的数字将链表集合在一起，并且在第三步的整体排序过程将空箱子进行了删除，重新根据数字的大小将链表生成
箱子排序的形式
逐个删除输入链表的节点，把删除的节点分配到相应的箱子里
把每一个箱子中的链表收集并链接起来，使其成为一个有序链表。
如果输入的链表是程序的chain表
{
连续删除链表的首元素，并将其插入相应的某个箱子的链表首位
从最后一个箱子开始，租个删除每个箱子里的元素，并将其插入一个初始为空的链表首位
}
![在箱子排序的形式
逐个删除输入链表的节点，把删除的节点分配到相应的箱子里
把每一个箱子中的链表收集并链接起来，使其成为一个有序链表。
如果输入的链表是程序的chain表
{
连续删除链表的首元素，并将其插入相应的某个箱子的链表首位
从最后一个箱子开始，租个删除每个箱子里的元素，并将其插入一个初始为空的链表首位
}
struct studentrecord
{
int score;
string* name;
int operator!=(const studentrecord &x)const
{
return (score != x.score);
}
};
ostream& operator<<(ostream& out, const studentrecord& x)
{
out << x.score << ’ ’ << *x.name << endl;
return out;
}
声明的studentrecord的定义
在链接表中delete只是删除数据，free才是将整个节点处理掉
数组角度的理解
假如待排序列K= {49、38 、35、 97 、 76、 73 、 27、 49 }。这些数据全部在1—100之间。因此我们定制10个桶，然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中，并在每个非空的桶中进行快速排序后得到如下图所示：
1、箱排序的基本思想 箱排序也称桶排序(Bucket Sort)，其基本思想是：设置若干个箱子，依次扫描待排序的记录R[0]，R[1]，…，R[n-1]，把关键字等于k的记录全都装入到第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。【例】要将一副混洗的52张扑克牌按点数A<2<…<J<Q<K排序，需设置13个"箱子"，排序时依次将每张牌按点数放入相应的箱子里，然后依次将这些箱子首尾相接，就得到了按点数递增序排列的一副牌。2、箱排序中，箱子的个数取决于关键字的取值范围。 若R[0…n-1]中关键字的取值范围是0到m-1的整数，则必须设置m个箱子。因此箱排序要求关键字的类型是有限类型，否则可能要无限个箱子。3、箱子的类型应设计成链表为宜 一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的，故箱子的类型应设计成链表为宜。4、为保证排序是稳定的，分配过程中装箱及收集过程中的连接必须按先进先出原则进行。（1） 实现方法一 每个箱子设为一个链队列。当一记录装入某箱子时，应做人队操作将其插入该箱子尾部；而收集过程则是对箱子做出队操作，依次将出队的记录放到输出序列中。（2） 实现方法二 若输入的待排序记录是以链表形式给出时，出队操作可简化为是将整个箱子链表链接到输出链表的尾部。这只需要修改输出链表的尾结点中的指针域，令其指向箱子链表的头，然后修改输出链表的尾指针，令其指向箱子链表的尾即可。
基数排序中
基数排序的排序原理不难理解，但是在算法设计上，个人感觉还是比那些常见的排序要难的，耐心慢慢一步步理解，还是比较容易看懂的，注意基数排序有两种，一种是高位优先，一种是低位优先，在这里我只讲低位优先，即先排个位，再排十位
基数排序的时间复杂度为O (nlog®m)，其中r为所采取的基数，而m为堆数
注：比其他的稳定
class RadixSort2{
private byte digits = 3;//元素的位数
private List[] list = new List[10];
public RadixSort2(){
super();
for(int i = 0; i < list.length; i++){
//LinkedList和ArrayList性能相当, ArrayList指定容量与不指定相当. 奇怪
list[i] = new ArrayList(10000);
}
}
public void sort(int[] arr){
int count = 1;
for(int j = 0;j < digits; j++){
//一遍循环处理一位
for(int i = 0;i < arr.length; i++){
//add(new Node(arr[i]),(arr[i]/count) % 10);
list[(arr[i]/count) % 10].add(arr[i]);
}
copy(arr);
count*=10;
}
}
这种情况看上去更像是根据位数来进行排序比较 private void copy(int[] arr) {
// 把链表中的元素复制回数组
int k = 0;//数组下标
for(int i = 0; i < list.length; i++){
for(Object o : list[i]){
arr[k++] = (Integer)o;
}
list[i].clear() ;
把链表数据扣出来，进行类似于数组的处理，然后在排序改变节点的链接顺序，重新放回到新节点上