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

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。
对于每个间隔，将数组分成多个子序列，子序列的元素之间相隔间隔个位置。
对每个子序列进行插入排序，即将子序列中的元素按照插入排序的方式进行排序。
重复步骤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.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 <iostream>
#include <fstream>
#include <vector>
#include <algorithm>// 生成随机数并保存到文件
void generateRandomNumbers(const std::string& filename, int count) {std::ofstream file(filename);if (!file.is_open()) {std::cout << "无法打开文件：" << filename << std::endl;return;}else{std::cout << "生成成功"<<std::endl;}srand(time(NULL));for (int i = 0; i < count; ++i) {int num = rand() % 100000;  // 生成0到99999之间的随机数file << num << std::endl;}file.close();
}// 从文件中读取数据
std::vector<int> readNumbersFromFile(const std::string& filename) {std::vector<int> numbers;std::ifstream file(filename);if (!file.is_open()) {std::cout << "无法打开文件：" << filename << std::endl;return numbers;}int num;while (file >> num) {numbers.push_back(num);}file.close();return numbers;
}// 将数据存入文件
void writeNumbersToFile(const std::string& filename, const std::vector<int>& numbers) {std::ofstream file(filename);if (!file.is_open()) {std::cout << "无法打开文件：" << filename << std::endl;return;}else{std::cout << "存入成功"<<std::endl;}for (int num : numbers) {file << num << std::endl;}file.close();
}// 希尔排序
void shellSort(std::vector<int>& numbers) {int n = numbers.size();for (int gap = n / 2; gap > 0; gap /= 2) {for (int i = gap; i < n; ++i) {int temp = numbers[i];int j = i;while (j >= gap && numbers[j - gap] > temp) {numbers[j] = numbers[j - gap];j -= gap;}numbers[j] = temp;}}
}// 快速排序
void quickSort(std::vector<int>& numbers, int low, int high) {if (low < high) {int pivot = numbers[high];int i = low - 1;for (int j = low; j <= high - 1; ++j) {if (numbers[j] < pivot) {++i;std::swap(numbers[i], numbers[j]);}}std::swap(numbers[i + 1], numbers[high]);int partitionIndex = i + 1;quickSort(numbers, low, partitionIndex - 1);quickSort(numbers, partitionIndex + 1, high);}
}// 堆排序
void heapify(std::vector<int>& numbers, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && numbers[left] > numbers[largest])largest = left;if (right < n && numbers[right] > numbers[largest])largest = right;if (largest != i) {std::swap(numbers[i], numbers[largest]);heapify(numbers, n, largest);}
}void heapSort(std::vector<int>& numbers) {int n = numbers.size();for (int i = n / 2 - 1; i >= 0; --i)heapify(numbers, n, i);for (int i = n - 1; i >= 0; --i) {std::swap(numbers[0], numbers[i]);heapify(numbers, i, 0);}
}// 归并排序
void merge(std::vector<int>& numbers, int left, int middle, int right) {int n1 = middle - left + 1;int n2 = right - middle;std::vector<int> leftArr(n1);std::vector<int> rightArr(n2);for (int i = 0; i < n1; ++i)leftArr[i] = numbers[left + i];for (int j = 0; j < n2; ++j)rightArr[j] = numbers[middle + 1 + j];int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (leftArr[i] <= rightArr[j]) {numbers[k] = leftArr[i];++i;}else {numbers[k] = rightArr[j];++j;}++k;}while (i < n1) {numbers[k] = leftArr[i];++i;++k;}while (j < n2) {numbers[k] = rightArr[j];++j;++k;}
}void mergeSort(std::vector<int>& numbers, int left, int right) {if (left < right) {int middle = left + (right - left) / 2;mergeSort(numbers, left, middle);mergeSort(numbers, middle + 1, right);merge(numbers, left, middle, right);}
}int main() {// 生成随机数并保存到文件generateRandomNumbers("input.txt", 10000);// 从文件中读取数据std::vector<int> numbers = readNumbersFromFile("input.txt");// 复制数据用于各种排序算法std::vector<int> numbersShell = numbers;std::vector<int> numbersQuick = numbers;std::vector<int> numbersHeap = numbers;std::vector<int> numbersMerge = numbers;// 希尔排序shellSort(numbersShell);// 将结果存入文件writeNumbersToFile("shell_sorted.txt", numbersShell);// 快速排序quickSort(numbersQuick, 0, numbersQuick.size() - 1);// 将结果存入文件writeNumbersToFile("quick_sorted.txt", numbersQuick);// 堆排序heapSort(numbersHeap);// 将结果存入文件writeNumbersToFile("heap_sorted.txt", numbersHeap);// 归并排序mergeSort(numbersMerge, 0, numbersMerge.size() - 1);// 将结果存入文件writeNumbersToFile("merge_sorted.txt", numbersMerge);return 0;
}