南京师范大学计电院数据结构课设——排序算法

1 排序算法

1.1 题目要求

���程实现希尔、快速、堆排序、归并排序算法。要求首先随机产生10000个数据存入磁盘文件，然后读入数据文件，分别采用不同的排序方法进行排序并将结果存入文件中。

1.2 算法思想描述

1.2.1 随机数生成

当需要生成一系列随机数时，常常需要使用随机函数。然而，传统的rand()函数所生成的数据并不能被视为真正的随机数，因其仅限于某个特定范围内的值，并且在多次运行同一rand()函数时，所产生的随机数序列是完全一致的，缺乏真正的随机性。为此，我们需要借助srand()函数来设置rand()函数生成随机数时的种子值，通过不同的种子值，我们可以获得不同的随机数序列。

为了实现更接近真正随机数的序列生成，一种常见的做法是利用srand((int)time(NULL))的方式，即利用系统时钟来产生随机数种子。该方法将当前时间转换为一个整数，并将其作为srand()函数的参数，以初始化随机数生成器的种子值。由于时间的变化是无法预测的，因此每次程序运行时都会获得一个不同的种子值，从而产生不同的随机数序列。

图1.1 随机生成数示例代码

1.2.2 希尔排序

希尔排序（Shell Sort）是一种基于插入排序的排序算法，它通过将待排序的元素按照一定的间隔分组，对每组进行插入排序，随着间隔逐渐减小，最终使得整个序列达到有序状态。

下面是希尔排序的基本思想和实现步骤：

1. 选择一个间隔序列（称为增量序列），通常初始间隔为数组长度的一半，然后逐步缩小间隔直到为1。
2. 对于每个间隔，将数组分成多个子序列，子序列的元素之间相隔间隔个位置。
3. 对每个子序列进行插入排序，即将子序列中的元素按照插入排序的方式进行排序。
4. 重复步骤2和步骤3，直到间隔为1时，进行最后一次插入排序。

图1.2 希尔排序示例代码

1.2.3 快速排序

快速排序（Quick Sort）是一种高效的排序算法，它采用分治法（Divide and Conquer）策略来排序一个数组。快速排序的基本思想是选择一个基准元素（pivot），将数组分割成两个子数组，其中一个子数组的元素都比基准元素小，另一个子数组的元素都比基准元素大，然后对这两个子数组分别进行递归排序，最终将整个数组排序完成。

图1.3 快速排序示例代码

1.2.4 堆排序

堆排序（Heap Sort）是一种利用堆数据结构进行排序的算法。堆是一种完全二叉树，具有以下性质：对于每个节点i，其父节点的值小于等于节点i的值（最大堆），或者父节点的值大于等于节点i的值（最小堆）。在堆排序中，我们使用最大堆来进行排序。

下面是堆排序的基本思想和实现步骤：

1. 把无序数组构建成二叉堆。
2. 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。
3. 当删除一个最大堆的堆顶（并不是完全删除，而是替换到最后面），经过自我调节，第二大的元素就会被交换上来，成为最大堆的新堆顶。由于这个特性，我们每一次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。那么我们只要反复删除堆顶，反复调节二叉堆，所得到的集合就成为了一个有序集合。

图1.4 堆排序示例代码

1.2.5 归并排序

归并排序（Merge Sort）是一种基于分治法（Divide and Conquer）的排序算法，它将待排序的数组逐步分割成较小的子数组，然后将这些子数组逐个合并，最终得到一个有序的数组。合并2个数组的称为2路归并，合并3个数组的称为3路归并，多路归并。归并排序是稳定的。

图1.5 归并排序示例代码

1.3 程序设计

1.3.1 程序设计思路

图1.6 程序设计思路图

1.3.2 生成input.txt文件

先创建一个文件并打开，然后生成随机数存储到该文件中作为后续的输入文件。

图1.7 生成input.txt文件代码

1.3.3 生成排序结果文件

首先完成文件的存入函数，再分别调用不同的排序算法完成排序再存入对应的文件中。

图1.8将数据存入文件代码

图1.9 排序并存入文件代码

1.3.4完整代码（C++）

#include #include #include #include // 生成随机数并保存到文件void generateRandomNumbers(const std::string& filename, int count) {    std::ofstream file(filename);    if (!file.is_open()) {        std::cout