01 箱子排序
1.1 什么是分配排序？
分配排序的基本思想：排序过程无须比较关键字，而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶：O(n)。
1.2 什么是箱子排序？
箱子排序是分配排序的一种，箱子排序也称桶排序(Bucket Sort)，其基本思想是：设置若干个箱子，依次扫描待排序的记录 R[0]，R[1]，…，R[n-1]，把关键字等于 k 的记录全都装入到第 k 个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。
比如，要将一个班的同学按分数排序，分数范围是0-100分。需设置 101 个"箱子"（R[0]，R[1]，…，R[100]），排序时依次将每个同学按分数放入相应的箱子里，然后依次将这些箱子首尾相接，就得到了按分数递增序排列的一个班的同学。
1.3 关于箱子个数
箱排序中，箱子的个数取决于关键字的取值范围。
若关键字的取值范围是0到m-1的整数，则必须设置 m 个箱子。因此箱排序要求关键字的类型是有限类型，否则可能要无限个箱子。
02 链表实现箱子排序
一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的，故箱子的类型应设计成链表为宜。
我们现在来讲解一个简单的例子，以便来让大家更好了解这个过程。
2.1 example
下面是一个学生链表。为了更好说明问题，我们简化了学生的存储结构。每个学生节点保存一个字符，表示学生的姓名，再存一个数字，表示学生的分数。分数范围为0-5。
2.2 箱子排序的步骤
有了上面的输入链表以后。我们采用以下步骤进行箱子排序：
1） 逐个删除输入链表的节点，然后把删除的节点分配到相应的箱子中。
2） 把每个箱子中的元素收集并链接起来，使其成为一个有序链表。
比如上面的输入链表，我们要做的是：
1） 连续删除链表的首元素，并将其插入到相对应箱子的链表头部。
2） 从最后一个箱子开始，逐个删除每个箱子的元素，并将其插入一个初始为空的链表的头部。
如下图所示：
那么排序好的链表如下：
03 动手写代码
3.1 studentRecord结构体
先来看看代码：
1struct studentRecord 2{ 3 int score; 4 string name; 5 6 studentRecord() {} 7 studentRecord(int theScore, string theName) :score(theScore), name(theName) {} 8 9 int operator != (const studentRecord & x) const 10 { 11 return (score != x.score); 12 } 13 operator int() const { return score; } 14};
在studentRecord这个结构体里面，我们重载了 != 这个运算符，以便用于比较等操作。还重载了int()运算符，这样一来，借助int()转换符就可以直接对学生结构体进行+-*/等操作了。
3.2 箱子排序代码
还是先看看代码吧。
1void binSort(chain<studentRecord> & theChain, int range) 2{ 3 chain<studentRecord> * bin = new chain<studentRecord>[range + 1]; // 0 to range 4 int numberOfElements = theChain.size(); 5 6 for (int i = 0; i < numberOfElements; i++) 7 { 8 studentRecord record = theChain.get(0); 9 theChain.erase(0); 10 11 bin[record.score].insert(0, record); 12 } 13 for (int j = range; j >= 0; j--) 14 { 15 while (!bin[j].empty()) 16 { 17 studentRecord record = bin[j].get(0); 18 bin[j].erase(0); 19 theChain.insert(0, record); 20 } 21 } 22 23 delete[] bin; 24}
该函数只有两个参数，一个是学生链表。还有一个是排序范围（设置为0~range）。函数主体就是按部就班的进行上面所说的两步操作了。这里的chain链表是事先封装好的一个类。
04 完整代码
贴上一个完整的代码：
1#include <iostream> 2#include <string> 3#include <time.h> 4#include <stdlib.h> 5#include "../03_线性表_链式描述/chain.h" 6#include "../03_线性表_链式描述/chain.cpp" 7 8using std::cout; 9using std::cin; 10using std::endl; 11using std::string; 12 13struct studentRecord 14{ 15 int score; 16 string name; 17 18 studentRecord() {} 19 studentRecord(int theScore, string theName) :score(theScore), name(theName) {} 20 21 int operator != (const studentRecord & x) const 22 { 23 return (score != x.score); 24 } 25 operator int() const { return score; } 26}; 27 28//override out 29ostream & operator<<(ostream & out, const studentRecord & x) 30{ 31 out << x.name << " " << x.score << endl; 32 return out; 33} 34 35void binSort(chain<studentRecord> & theChain, int range) 36{ 37 chain<studentRecord> * bin = new chain<studentRecord>[range + 1]; // 0 to range 38 int numberOfElements = theChain.size(); 39 40 for (int i = 0; i < numberOfElements; i++) 41 { 42 studentRecord record = theChain.get(0); 43 theChain.erase(0); 44 45 bin[record.score].insert(0, record); 46 } 47 for (int j = range; j >= 0; j--) 48 { 49 while (!bin[j].empty()) 50 { 51 studentRecord record = bin[j].get(0); 52 bin[j].erase(0); 53 theChain.insert(0, record); 54 } 55 } 56 57 delete[] bin; 58} 59 60int main() 61{ 62 srand(time(0)); 63 chain<studentRecord> students; 64 studentRecord someOne; 65 for (int i = 0; i < 100; i++) 66 { 67 char Name = i % 26 + 'A'; 68 someOne.name = Name; 69 someOne.score = rand() % 101; 70 students.insert(0, someOne); 71 } 72 73 binSort(students, 100); 74 cout << " "; 75 students.output(cout); 76 77 cin.get(); 78 79 return 0; 80}
最后贴上一张运行效果：
