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;
}
