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

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. 当删除一个最大堆的堆顶（并不是完全删除，而是替换到最后面），经过自我调节，第二大的元素就会被交换上来，成为最大堆的新堆顶。由于这个特性，我们每一次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。那么我们只要反复删除堆顶，反复调节二叉堆，所得到的集合就成为了一个有序集合。
4. 

图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 << "无法打开文件：" << filename << std::endl;
        return;
    }
    else
    {
        std::cout << "生成成功"<
    }
    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 << "存入成功"<
    }
    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;
}