【数据结构】C++用链表实现一个箱子排序附源代码详解

简介: 【数据结构】C++用链表实现一个箱子排序附源代码详解

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 链表实现箱子排序


一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的,故箱子的类型应设计成链表为宜。


我们现在来讲解一个简单的例子,以便来让大家更好了解这个过程。

微信图片_20220421151057.png

2.1 example

下面是一个学生链表。为了更好说明问题,我们简化了学生的存储结构。每个学生节点保存一个字符,表示学生的姓名,再存一个数字,表示学生的分数。分数范围为0-5。


2.2 箱子排序的步骤

有了上面的输入链表以后。我们采用以下步骤进行箱子排序:

1) 逐个删除输入链表的节点,然后把删除的节点分配到相应的箱子中。

2) 把每个箱子中的元素收集并链接起来,使其成为一个有序链表。


比如上面的输入链表,我们要做的是:

1) 连续删除链表的首元素,并将其插入到相对应箱子的链表头部。

2) 从最后一个箱子开始,逐个删除每个箱子的元素,并将其插入一个初始为空的链表的头部。


如下图所示:

微信图片_20220421151101.png

那么排序好的链表如下:

微信图片_20220421151103.png

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}


最后贴上一张运行效果:

微信图片_20220421151107.jpg


相关文章
|
2月前
|
安全 编译器 C语言
【C++数据结构】string的模拟实现
【C++数据结构】string的模拟实现
05_用一个栈实现另一个栈的排序
05_用一个栈实现另一个栈的排序
|
2月前
|
C语言
数据结构——排序【上】
数据结构——排序【上】
19 2
|
2月前
|
搜索推荐 算法 测试技术
【数据结构】排序
【数据结构】排序
|
3月前
|
搜索推荐
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
|
3月前
|
存储 数据格式 运维
开发与运维C++问题之更改数据模型为通用数据结构如何解决
开发与运维C++问题之更改数据模型为通用数据结构如何解决
21 1
|
3月前
|
搜索推荐
【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】
【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】
|
3月前
|
搜索推荐 测试技术
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
|
3月前
|
存储 C++
C++的list-map链表与映射表
```markdown C++ 中的`list`和`map`提供链表和映射表功能。`list`是双向链表,支持头尾插入删除(`push_front/push_back/pop_front/pop_back`),迭代器遍历及任意位置插入删除。`map`是键值对集合,自动按键排序,支持直接通过键来添加、修改和删除元素。两者均能使用范围for循环遍历,`map`的`count`函数用于统计键值出现次数。 ```
28 1
|
3月前
|
存储 算法 C++
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
52 0