《数据结构》课程设计--c++快速排序、希尔排序、冒泡排序、堆排序、归并排序、基数排序
·
任务描述
任务背景和目标
电子英汉词典任务，实现词典的排序功能。为了简化任务，每个单词词条只有英文单词自身，字段长度不超过100个字节。待排序词典的词条数量不超过1000条，详见3。
功能列表
1）交互界面（10分）
自定，文字菜单式、命令行交互式、图形交互方式均可；
2）单词排序（10分×5=50分）
使用至少五种不同的排序算法；
3）排序效率比较（20分）
统计不同排序算法所花的排序时间，在报告中加以比较和解释；
4）排序后的词典输出（4分×5=20分）
按要求输出不同算法排序后的词典；
待排序词典及其输入格式
1) 文件名为 “dictrandom.txt”
2) 每行一个单词，乱序排列
3) 由 "===" 开始的行是注释行，处理时应该略过
排序后的词典输出格式要求
1）文件名为 “dictsorted1.txt”~ “dictsorted5.txt”
2）第1行：=======姓名 学号 排序算法==============
3）第2行到n+1行：n个单词词条按照升序排列（a-z排序)
4）最后1行：=========xxx.xxx 秒============
（排序所用时间，代码自动生成）
算法总述
本次实验实现了一个简易的电子英汉词典中单词排序的算法集合。以下是主要的功能和算法：
Dictionary.h
定义一个简单的词典类 Dictionary，其中包括一个嵌套的 Word 类，用于表示词典中的单词及其相关信息。它提供了添加单词、加载数据、打印字典、保存字典等基本功能。此外，实现了多种排序算法--冒泡排序、快速排序、希尔排序、堆排序、归并排序和基数排序，以便对字典中的单词进行排序。
Sort.h
实现以下排序算法：快速排序、希尔排序、冒泡排序、堆排序、归并排序和基数排序。每个算法都写成了 Dictionary 类的成员函数，对字典中的单词进行排序，使得单词按照字母顺序排列。
Test.h
通过使用不同的排序算法对字典进行多次排序，并计算每种算法的平均排序时间。其中定义了一个模板函数 SortingTest，用于测试单个排序函数的性能。然后，通过调用 test 函数，依次测试了实现的排序算法，最后，将每种排序算法的平均排序时间按照从小到大的顺序输出。这个测试模块可以帮助评估每种排序算法在给定数据集上的效率，并为选择最适合的排序算法提供参考。
Main.cpp
主函数利用了字典类的不同排序方法对数据进行排序，并将排序结果保存到文件中。接着，调用了测试模块来评估每种排序算法的性能，并输出排序时间。
实验内容
解决方案
类和文件和输入输出
#ifndef DICTIONARY_H
#define DICTIONARY_H
#include <chrono>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Word
{
public:
string word;
Word() : word("") {}
Word(string word) : word(word) {}
bool operator<=(const Word& other) const // 重载小于等于运算符
{
return word <= other.word;
}
};
class Dictionary
{
public:
vector<Word> words;
int size;
using DurationType = std::chrono::nanoseconds::rep;
DurationType duration;
// auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start).count();
Dictionary() : size(0), duration(0) {}
Dictionary(string filename) : size(0), duration(0)
{
load_data(filename);
}
// 深拷贝构造函数
Dictionary(const Dictionary &other) : size(other.size), duration(other.duration)
{
for(const auto &word : other.words)
{
words.push_back(word);
}
}
void add_word(Word inputword);
void load_data(string filename);
void print_dict();
void save_dict(string filename, string method);
void Q_sort(int l, int r);
void QuickSort_sj(int low, int high);
void Shell_sort();
static bool compareWords(const Word &a, const Word &b);
void SortDictionary();
void Bubble_sort();
void BuildHeap();
void HeadAdjust(int k,int len);//以k为根
void HeapSort();
void Merge(int low, int mid, int high);
void MergeSort();
void RadixSort();
};
void Dictionary::add_word(Word inputword)
{
words.push_back(inputword);
}
void Dictionary::load_data(string filename)
{
ifstream file(filename);
string word;
while (file >> word)
{
add_word(Word(word));
size++;
}
file.close();
}
void Dictionary::print_dict()
{
for (int i = 0; i < size; i++)
{
cout << words[i].word << endl;
}
cout << duration << endl;
}
void Dictionary::save_dict(string filename, string method)
{
ofstream file(filename);
file << "=======第六组 2024/4 " << method << "==============" << endl;
for (int i = 0; i < size; i++)
{
file << words[i].word << endl;
}
file << "=========" << duration << "秒==============" << endl;
file.close();
}
bool Dictionary::compareWords(const Word &a, const Word &b)
{
return a.word < b.word;
}
#endif
- 定义了一个 Dictionary 类，用于管理单词集合，并提供了多种排序算法。该类包含了单词集合的向量 words、单词数量 size 和排序所花费的时间 duration，同时提供了默认构造函数和从文件加载单词的构造函数，以及深拷贝构造函数，实现了添加单词、加载数据、打印字典、保存字典等基本功能。快速排序、希尔排序、冒泡排序、堆排序、归并排序和基数排序等多种排序算法都是 Dictionary 类的成员函数，可以直接在字典对象上调用。同时提供了静态比较函数 compareWords 用于排序算法中的比较操作，辅助函数包括打印字典中的单词和将字典中的单词保存到文件中。
单词排序
#ifndef SORT_h
#define SORT_h
#include <algorithm>
#include "Dictionary.h"
// 这里写排序，如果要写dictionary的成员函数记得先去dictionary.h里面声明
// 排序时应当拷贝构造一个Dictionary dictx(dict);对dictx进行排序而不是使用原始的dict
// 或者将排序函数返回值设置为Dictionary类型,传入const Dictionary& dict,返回排序后的Dictionary
void Dictionary::SortDictionary()
{
sort(words.begin(), words.end(), compareWords);
}
void Dictionary::Q_sort(int l, int r) //快速排序
{
if (l < r)
{
int i = l, j = r;
Word pivot = words[(l + r) / 2]; // 选择中间的元素作为枢纽元
// 分区操作，将比枢纽元小的元素放在左侧，比枢纽元大的元素放在右侧
while (i <= j)
{
while (words[i].word < pivot.word)
i++;
while (words[j].word > pivot.word)
j--;
if (i <= j)
{
swap(words[i], words[j]);
i++;
j--;
}
}
// 递归调用，对左侧和右侧分区进行快速排序
if (l < j)
Q_sort(l, j);
if (i < r)
Q_sort(i, r);
}
}
void Dictionary::QuickSort_sj(int low, int high)
{
if (low < high)
{
string e = words[low].word;// 选择第一个元素作为枢纽元
int i = low, j = high;
while (i < j)
{
while (i < j && words[j].word >= e)
j--;
if (i < j)
words[i++] = words[j]; //在交换元素时，没有像第一种实现那样使用 swap 函数，而是直接通过赋值操作来实现
while (i < j && words[i].word <= e)
i++;
if (i < j)
words[j--] = words[i];
}
words[i].word = e;
// 递归调用，对左侧和右侧分区进行快速排序
if (low < i - 1)
QuickSort_sj(low, i - 1);
if (i + 1 < high)
QuickSort_sj(i + 1, high);
}
}
void Dictionary::Shell_sort() //希尔排序
{
int n = size;
for (int gap = n / 2; gap > 0; gap /= 2) // 初始步长设定为数组长度的一半
{
for (int i = gap; i < n; i++) // 在每个步长下进行插入排序
{
Word temp = words[i]; // 暂存当前位置的元素
// 将当前位置前面的元素逐个后移，直到找到合适的位置插入 temp
int j;
for (j = i; j >= gap && words[j - gap].word > temp.word; j -= gap)
{
words[j] = words[j - gap];
}
// 插入 temp
words[j] = temp;
}
}
}
void Dictionary::Bubble_sort()
{
int n=size;
for(int i=0;i<n-1;i++)
{
bool flag=false;
for(int j=n-1;j>=1;j--)
{
if(words[j-1].word>words[j].word)
{
swap(words[j-1],words[j]);
flag=true;
}
}
if(flag==false)return;
}
}
void Dictionary::BuildHeap() //建立大根堆
{
int len = size;
for (int i = len / 2 - 1; i >= 0; i--)
{
HeadAdjust(i, len);
}
}
void Dictionary::HeadAdjust(int k, int len) {
string temp = words[k].word;
for (int i = 2 * k + 1; i < len; i = 2 * i + 1)
{ //将结点i和孩子比较
if (i + 1 < len && words[i].word < words[i + 1].word)
{//比较左孩子和右孩子的大小，找到大的孩子
i++;
}
if (temp >= words[i].word)
{
break;
}
else
{
words[k].word = words[i].word;
k = i;
}
}
words[k].word = temp;
}
void Dictionary::HeapSort()
{
int len = size;
BuildHeap();
for (int i = len - 1; i > 0; i--)
{
swap(words[0], words[i]);
HeadAdjust(0, i); // 传入 i 参数
}
}
void Dictionary::Merge(int low, int mid, int high)
// 将有序子序列words[low .. mid]和words[mid + 1 .. midhigh]归并为新的有序序列words[low .. high]
{
Word* tmpwords = new Word[high + 1];
int i = low, j = mid + 1, k = low;
while (i <= mid && j <= high)
if (words[i] <= words[j])
tmpwords[k++] = words[i++];
else
tmpwords[k++] = words[j++];
while (i <= mid)
tmpwords[k++] = words[i++];
while (j <= high)
tmpwords[k++] = words[j++];
for (i = low; i <= high; i++)
words[i] = tmpwords[i];
delete[]tmpwords;
}
void Dictionary::MergeSort() // 两路归并排序
{
int len = 1, i;
while (len < size)
{
i = 0;
while (i + 2 * len <= size) // 对从i开始的长度为len的两个相邻有序区间进行归并
{
Merge(i, i + len - 1, i + 2 * len - 1);
i += 2 * len;
}
if (i + len < size) // 对最后两个相邻有序区间进行归并
{
Merge(i, i + len - 1, size - 1);
}
len *= 2;
}
}
void Dictionary::RadixSort() // LSD基数排序
{
// 获取字符串的最大长度
int maxLength = 0;
for (const Word& str : words)
{
maxLength = max(maxLength, static_cast<int>(str.word.size()));
}
// 按照每个字符的 ASCII 值进行计数排序
for (int i = maxLength - 1; i >= 0; --i) {
vector<vector<string>> buckets(256); // 每个桶代表一个字符的取值范围
// 将字符串放入对应的桶中
for (const Word& tmpword : words)
{
if (i < tmpword.word.size())
{
buckets[tmpword.word[i]].push_back(tmpword.word);
}
else
{
buckets[0].push_back(tmpword.word); // 空字符放在0号桶中
}
}
// 从桶中收集字符串
int index = 0;
for (const vector<string>& bucket : buckets)
{
for (const string& str : bucket)
{
words[index++] = str;
}
}
}
}
#endif
Sort.h文件中实现了多种排序算法，包括快速排序、希尔排序、冒泡排序、堆排序、归并排序和基数排序。
- SortDictionary：使用 std::sort 函数对单词集合进行排序，利用 compareWords 函数进行比较。
- Q_sort (快速排序)：使用分治法，选择中间元素枢纽元对单词集合进行划分，递归地对左右子数组进行排序。
- QuickSort_sj (快速排序)：选择第一个元素作为枢纽元，通过左右指针将小于枢纽元的元素放在左侧，大于枢纽元的元素放在右侧，递归地对左右子数组进行排序。
- Shell_sort (希尔排序)：初始步长设定为数组长度的一半，通过插入排序对每个步长下的子数组进行排序，逐步减小步长直至为1。
- Bubble_sort (冒泡排序)：依次比较相邻的两个元素，若顺序不正确则交换，直至没有需要交换的元素。
- HeapSort (堆排序)：首先建立大根堆，然后依次取出堆顶元素与最后一个元素交换，并重新调整堆，直至所有元素有序。
- MergeSort (归并排序)：采用自底向上的归并思想，先将相邻的两个元素归并为有序序列，再将相邻的有序序列归并为更大的有序序列，直至整个数组有序。
- RadixSort (基数排序)：从低位到高位依次进行计数排序，根据每个字符的 ASCII 值将单词放入对应的桶中，最后按顺序收集单词。
这些排序算法都被实现为 Dictionary 类的成员函数，可以直接在字典对象上调用。
排序效率比较
#ifndef TEST_H
#define TEST_H
#include <iostream>
#include <vector>
#include <string>
#include <chrono>
#include "Dictionary.h"
#include "Sort.h"
using namespace std;
using namespace std::chrono;
// 模板简化测试代码
template <typename SortFunction>
pair<long long, string> SortingTest(Dictionary &dict, const string &name, SortFunction sortFunction)
{
const int n = 100;
long long total_duration = 0;
for (int i = 0; i < n; ++i)
{
auto start = high_resolution_clock::now();
Dictionary sortedDict = dict;
sortFunction(sortedDict);
auto stop = high_resolution_clock::now();
total_duration += duration_cast<nanoseconds>(stop - start).count();
}
return make_pair(total_duration / n, name);
}
void test(Dictionary &dict)
{
vector<pair<long long, string>> results;
results.push_back(SortingTest(dict, "直接使用sort函数", [](Dictionary &dict)
{ dict.SortDictionary(); }));
results.push_back(SortingTest(dict, "快速排序(mid元素为枢轴元)", [](Dictionary &dict)
{ dict.Q_sort(0, dict.size - 1); }));
results.push_back(SortingTest(dict, "快速排序(第一个元素为枢轴元)", [](Dictionary &dict)
{ dict.QuickSort_sj(0, dict.size - 1); }));
results.push_back(SortingTest(dict, "希尔排序", [](Dictionary &dict)
{ dict.Shell_sort(); }));
results.push_back(SortingTest(dict, "冒泡排序", [](Dictionary &dict)
{ dict.Bubble_sort(); }));
results.push_back(SortingTest(dict, "堆排序", [](Dictionary &dict)
{ dict.HeapSort(); }));
results.push_back(SortingTest(dict, "两路归并排序", [](Dictionary &dict)
{ dict.MergeSort(); }));
results.push_back(SortingTest(dict, "基数排序", [](Dictionary &dict)
{ dict.RadixSort(); }));
// 对时间进行排序输出
sort(results.begin(), results.end());
cout << "时间排序：" << endl;
for (const auto &result : results)
{
cout << result.second << ": " << result.first << "纳秒" << endl;
}
}
#endif
测试代码评估不同排序算法的性能，通过模板函数 SortingTest 来简化测试流程，并提供了一个 test 函数来执行实际的测试。
- 在 SortingTest 函数中，对于每个排序算法，它重复了 100 次排序操作，并记录了每次排序所花费的时间。最后，它返回了平均排序时间以及排序算法的名称。
- 在 test 函数中，它对每个排序算法调用 SortingTest 函数，并将结果存储在一个向量中。然后，对结果向量按照排序时间进行排序，并输出排序结果。
通过这个测试框架，可以很方便地评估每个排序算法在给定数据集上的性能表现，从而选择最合适的算法来进行排序。
Main.cpp设计
#include "Dictionary.h"
#include "Sort.h"
#include "Test.h"
using namespace std;
using namespace std::chrono;
int main()
{
Dictionary dict("dictrandom.txt");
cout << "Size: " << dict.size << endl;
dict.print_dict();
Dictionary dict0(dict);
dict0.SortDictionary();
dict0.save_dict("dict0.txt","直接使用sort函数");
Dictionary dict1(dict);
dict1.Q_sort(0, dict1.size-1);
dict1.save_dict("dict1.txt","快速(mid元素为枢纽元)");
Dictionary dict2(dict);
dict2.QuickSort_sj(0, dict2.size-1);
dict2.save_dict("dict2.txt","快速(第一个元素为枢纽元)");
Dictionary dict3(dict);
dict3.Shell_sort();
dict3.save_dict("dict3.txt","希尔");
Dictionary dict4(dict);
dict4.Bubble_sort();
dict4.save_dict("dict4.txt","冒泡");
Dictionary dict5(dict);
dict5.HeapSort();
dict5.save_dict("dict5.txt","堆");
Dictionary dict6(dict);
dict6.MergeSort();
dict6.save_dict("dict6.txt", "两路归并");
Dictionary dict7(dict);
dict7.RadixSort();
dict7.save_dict("dict7.txt", "基数");
test(dict);
system("pause");
}
主函数首先创建了一个字典对象 dict，并从文件中加载数据。然后，它使用不同的排序算法对该字典进行排序，并将排序后的结果保存到文件中。接着，调用了 test 函数来评估每个排序算法的性能。主函数通过执行不同的排序算法，并保存排序结果以及评估排序算法的性能。
实验结果
在上述工作外，我们还使用Qt搭建了一个如下的交互界面：
为篇幅考虑，只展示一种排序的输出结果，其他结果都十分类似。
排序结果
以下是调用Sort函数的结果：
排序时间效率比较
分析：
- 快速排序(第一个元素为枢轴元)：快速排序通常是一种高效的排序算法，在这组数据上表现较好，耗时较短。
- 堆排序：堆排序在大多数情况下具有稳定的性能，但它需要构建和调整堆，因此相对于其他简单的排序算法来说，它的耗时可能会稍多一些
- 快速排序(mid元素为枢轴元)：与快速排序(第一个元素为枢轴元)相比，选择枢轴元素的位置不同可能会影响快速排序的性能。在这个实验中，以中间元素作为枢轴元素的快速排序的耗时略多于以第一个元素作为枢轴元素的快速排序。
- 直接使用sort函数：C++的标准库中提供了高效的排序算法，其中的std::sort函数通常使用了高效的排序实现。直接使用sort函数进行排序在这组数据上耗时较长，可能是由于内部实现对于特定数据的排序不够高效。
- 希尔排序：希尔排序是一种插入排序的改进版本，通过对数据进行分组和插入排序来实现。在这个实验中，希尔排序的耗时比其他算法稍长。
- 基数排序：基数排序是一种非比较排序算法，它根据关键字的每一位进行排序，适用于特定数据范围较小的场景。在这个实验中，基数排序的耗时较长，可能是由于数据规模较大或者具体实现的一些细节的影响。
- 两路归并排序：归并排序是一种稳定且效率较高的排序算法，但在这个实验中，耗时最长，可能是由于数据规模较大或者同样是具体实现细节的影响。
- 冒泡排序：冒泡排序通常是效率最低的排序算法之一，它的耗时通常是其他算法的几倍甚至更多。在这个实验中，冒泡排序的耗时最长，这与其简单且低效的排序方式有关。
算法复杂度分析
1）快速排序：
适用场景：适用于大规模数据的排序，平均时间复杂度较好。
性能特点：快速排序具有较好的平均时间复杂度，但最坏情况下可能出现性能退化，需要额外的优化手段（如随机化选择枢轴）。平均时间复杂度：O(nlogn)、最坏时间复杂度：O(n^2)、空间复杂度：O(logn)（递归调用所需的栈空间）
2）希尔排序：
适用场景：适用于中等规模数据的排序，尤其是在数据量较大且随机性较强的情况下。
性能特点：希尔排序的时间复杂度取决于增量序列的选择，不稳定性能较为灵活，但最坏情况下性能较差。平均时间复杂度：取决于增量序列的选择，在最好情况下为O(nlogn)，最坏情况下为O(n^2)、最坏时间复杂度：O(n^2)、空间复杂度：O(1)
3）冒泡排序：
适用场景：适用于小规模数据的排序，或者数据基本有序的情况下。
性能特点：冒泡排序的时间复杂度较高，不推荐在大规模数据下使用，但实现简单。平均时间复杂度：O(n^2)、最好时间复杂度O(n)、最坏时间复杂度：O(n^2)、空间复杂度：O(1)
4）堆排序：
适用场景：适用于大规模数据的排序，尤其是需要稳定性能的情况下。
性能特点：堆排序具有较好的平均时间复杂度和稳定性能，适用于大规模数据的排序，且不受数据分布情况影响。平均时间复杂度：O(nlogn)、空间复杂度：O(1)
5）归并排序：
适用场景：适用于大规模数据的排序，尤其是需要稳定性能的情况下。
性能特点：归并排序的时间复杂度稳定且较好，适用于大规模数据的排序，但需要额外的空间来存储临时数据。平均时间复杂度：O(nlogn)、空间复杂度：O(n)（需要额外的空间来存储临时数据）
6）基数排序：
适用场景：适用于多关键字比较的排序，尤其是关键字位数较小的情况下。
性能特点：基数排序的时间复杂度取决于关键字位数和关键字取值范围，适用于多关键字比较的场景，但对内存要求较高。平均时间复杂度：O(d*(n+radix))，其中d为关键字位数，n为数据元素个数，radix为关键字的取值范围大小、空间复杂度：O(n+2radix)
综上所述，根据具体的数据规模、数据分布情况和性能需求，可以选择合适的排序算法来提高程序的效率和性能。
总结
这次实验实现了多种排序算法，并提供了一个测试框架来评估每种排序算法的性能。通过字典类，可以加载、保存和打印单词数据，并对其中的单词进行排序。排序算法包括快速排序、希尔排序、冒泡排序、堆排序、归并排序和基数排序等。测试框架通过对每种排序算法进行重复测试，并计算平均排序时间，从而评估其性能。加载数据后，依次使用不同排序算法对字典进行排序，并将排序结果保存到文件中。随后调用测试框架评估每个排序算法的性能，并输出排序时间结果。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
26
0- 0
已为社区贡献4条内容
所有评论(0)