链表应用：箱子排序

1、问题描述

假定一个链表中包含了一个班级内所有学生的信息，每个节点中含有这样的域：学生姓名、社会保险号码、每次作业和考试的分数以及所有作业和考试的加权总分。假定所有的分数均为0 ~ 1 0 0范围内的整数。如果采用第 2章中所给出的任一种排序算法对表中的学生按分数进行排序，所需要花费的时间均为 O (n ² )，其中 n 为班级中的学生总数。一种更快的排序方法为箱子排序（ bin sort）。在箱子排序过程中，节点首先被放入箱子之中，具有相同分数的节点都放在同一个箱子中，然后通过把箱子链接起来就可以创建一个有序的链表。

　　怎样实现箱子呢？注意到每个箱子都是一个由节点组成的线性表。箱子中的节点数目介于0到n之间。一种简单的方法就是把每个箱子都描述成一个链表。在进行节点分配之前，所有的箱子都是空的。
　　对于箱子排序，需要能够： 1 )从欲排序链表的首部开始，逐个删除每个节点，并把所删除的节点放入适当的箱子中（即相应的链表中）； 2) 收集并链接每个箱子中的节点，产生一个排序的链表。如果所输入的链表为 C h a i n类型（见程序 3 - 8），那么可以： 1) 连续地删除链表首元素并将其插入到相应箱子链表的首部； 2) 逐个删除每个箱子中的元素（从最后一个箱子开始）并将其插入到一个初始为空的链表的首部。
　　实现1：
　　　　

 1 void Binsort(Chain<T>& C,int range)
 2 {
 3     int length=C.Length();
 4     T x;
 5     Chain<T>* Bin=new Chain<T>[range+1];
 6 //分配到每个箱子
 7     for(int i=1;i<=length;++i)
 8     {
 9         C.Delete(1,x);
10         Bin[x].Insert(0,x);
11     }
12     
13     for(int i=range;i>=0;--i)
14     {
15 //收集箱子
16         while(!Bin[i].Empty())
17         {
18             T temp;
19             Bin[i].Delete(1,x);
20             C.Insert(0,x);
21         }    
22     }
23     
24     delete[] Bin;
25 }

View Code

实现2：将Binsort作为链表的成员函数

 1 template<class T>
 2 void Chain<T>::Binsort(int range, int(*value)(T& x))
 3 {
 4     int b;//箱子索引号
 5     ChainNode<T> **bottom, **top;
 6     //箱子初始化
 7     bottom = new ChainNode<T>*[range + 1];
 8     top = new ChainNode<T>*[range + 1];
 9     for (b = 0; b <= range; b++)
10     {
11         bottom[b] = 0;
12     }
13 
14     for (; first; first = first->link)
15     {
16         b = value(first->data);
17         if (bottom[b])
18         {
19             top[b]->link = first;
20             top[b] = first;
21         }
22         else
23         {
24             bottom[b] = top[b] = first;
25         }
26     }
27 
28     ChainNode<T> *y = 0;
29     for (b = 0; b <= range; b++)
30     {
31         if (bottom[b])
32         {
33             if (y)
34                 y->link = bottom[b];
35             else
36                 first = bottom[b];
37 
38             y = top[b];
39         }
40     }
41     if (y) y->link = 0;
42     delete[] bottom;
43     delete[] top;
44 
45 }

View Code

B i n S o r t的时间复杂性，可以看到，第一和第三个 f o r循环所需要的时间为 ( r a n g e )，第二个for 循环所需要的时间为 (n)，因此总的时间复杂性为 (n+ r a n g e )。可以注意到 B i n S o r t函数并未改变具有同样分数的节点之间的相对次序。如果一个排序算法能够保持同值元素之间的相对次序，则该算法被称之为稳
定排序（ stable sort）。