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 结构体
先来看看代码:
- struct studentRecord
- {
- int score;
- string name;
- studentRecord() {}
- studentRecord(int theScore, string theName) :score(theScore), name(theName) {}
- int operator != (const studentRecord & x) const
- {
- return (score != x.score);
- }
- operator int() const { return score; }
- };
在 studentRecord 这个结构体里面, 我们重载了 != 这个运算符, 以便用于比较等操作. 还重载了 int() 运算符, 这样一来, 借助 int() 转换符就可以直接对学生结构体进行 +-*/ 等操作了.
3.2 箱子排序代码
还是先看看代码吧.
- void binSort(chain<studentRecord> & theChain, int range)
- {
- chain<studentRecord> * bin = new chain<studentRecord>[range + 1]; // 0 to range
- int numberOfElements = theChain.size();
- for (int i = 0; i < numberOfElements; i++)
- {
- studentRecord record = theChain.get(0);
- theChain.erase(0);
- bin[record.score].insert(0, record);
- }
- for (int j = range; j >= 0; j--)
- {
- while (!bin[j].empty())
- {
- studentRecord record = bin[j].get(0);
- bin[j].erase(0);
- theChain.insert(0, record);
- }
- }
- delete[] bin;
- }
该函数只有两个参数, 一个是学生链表. 还有一个是排序范围 (设置为 0~range). 函数主体就是按部就班的进行上面所说的两步操作了. 这里的 chain 链表是事先封装好的一个类.
04 完整代码
贴上一个完整的代码:
- #include <iostream>
- #include <string>
- #include <time.h>
- #include <stdlib.h>
- #include "../03_线性表_链式描述 / chain.h"
- #include "../03_线性表_链式描述 / chain.cpp"
- using std::cout;
- using std::cin;
- using std::endl;
- using std::string;
- struct studentRecord
- {
- int score;
- string name;
- studentRecord() {}
- studentRecord(int theScore, string theName) :score(theScore), name(theName) {}
- int operator != (const studentRecord & x) const
- {
- return (score != x.score);
- }
- operator int() const { return score; }
- };
- //override out
- ostream & operator<<(ostream & out, const studentRecord & x)
- {
- out << x.name << " " << x.score << endl;
- return out;
- }
- void binSort(chain<studentRecord> & theChain, int range)
- {
- chain<studentRecord> * bin = new chain<studentRecord>[range + 1]; // 0 to range
- int numberOfElements = theChain.size();
- for (int i = 0; i < numberOfElements; i++)
- {
- studentRecord record = theChain.get(0);
- theChain.erase(0);
- bin[record.score].insert(0, record);
- }
- for (int j = range; j >= 0; j--)
- {
- while (!bin[j].empty())
- {
- studentRecord record = bin[j].get(0);
- bin[j].erase(0);
- theChain.insert(0, record);
- }
- }
- delete[] bin;
- }
- int main()
- {
- srand(time(0));
- chain<studentRecord> students;
- studentRecord someOne;
- for (int i = 0; i < 100; i++)
- {
- char Name = i % 26 + 'A';
- someOne.name = Name;
- someOne.score = rand() % 101;
- students.insert(0, someOne);
- }
- binSort(students, 100);
- cout << " ";
- students.output(cout);
- cin.get();
- return 0;
- }
最后贴上一张运行效果:
来源: https://www.cnblogs.com/infroad/p/9643684.html