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

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

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>