从0开始学习C++ 第三十一课 归并排序和堆排序

发布时间:2024年01月23日

归并排序 (Merge Sort)

概念:
归并排序是一种分治策略的排序算法。它将一个数组分成两半,分别对它们进行排序,然后将结果归并成一个有序数组。

逐步分析:

  1. 分解:将数组从中间分成前后两部分,然后对前后两部分分别排序。
  2. 解决:递归地对两个子序列进行归并排序。
  3. 合并:将两个排序好的子序列合并成一个有序序列。

C++ 代码示例:

#include <vector>

// 将两个有序数组合并成一个有序数组的函数
void merge(std::vector<int> &array, int left, int mid, int right) {
    std::vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;

    // 合并两个有序数组
    while (i <= mid && j <= right) {
        if (array[i] <= array[j]) {
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    }

    // 复制剩余的元素
    while (i <= mid) {
        temp[k++] = array[i++];
    }
    while (j <= right) {
        temp[k++] = array[j++];
    }

    // 将临时数组的内容复制回原数组
    for (i = left, k = 0; i <= right; ++i, ++k) {
        array[i] = temp[k];
    }
}

// 归并排序的递归函数
void mergeSort(std::vector<int> &array, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);
        merge(array, left, mid, right);
    }
}

时间复杂度: O(n log n),无论是最好、最坏还是平均情况。
空间复杂度: O(n),因为需要与原数组同样大小的空间来存储临时数组。
是否稳定: 是,归并排序是稳定的排序算法。

堆排序 (Heap Sort)

概念:
堆排序是基于堆(通常是最大堆)的选择排序。堆是完全二叉树,其中父节点的值总是大于其子节点。

逐步分析:

  1. 构建最大堆:将无序数组构建成最大堆。
  2. 选择顶部:最大元素总是在堆的顶部。
  3. 排序:将顶部的最大元素与数组末尾的元素交换,然后缩小堆的大小,再次构建最大堆。

C++ 代码示例:

#include <vector>

// 用于调整最大堆的函数
void heapify(std::vector<int> &array, int n, int i) {
    int largest = i; // 初始化最大的为根
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    // 如果左子节点大于根节点
    if (left < n && array[left] > array[largest]) {
        largest = left;
    }

    // 如果右子节点大于当前最大的
    if (right < n && array[right] > array[largest]) {
        largest = right;
    }

    // 如果最大的不是根节点,交换它和根节点
    if (largest != i) {
        std::swap(array[i], array[largest]);
        // 递归地调整子树
        heapify(array, n, largest);
    }
}

// 堆排序函数
void heapSort(std::vector<int> &array) {
    int n = array.size();

    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(array, n, i);
    }

    // 一个个从堆顶取出元素
    for (int i = n - 1; i > 0; i--) {
        // 移动当前根到数组的末端
        std::swap(array[0], array[i]);
        // 调用 heapify 函数在减少的堆上
        heapify(array, i, 0);
    }
}

时间复杂度: O(n log n),因为要对 n 个节点进行 log n 次调整。
空间复杂度: O(1),因为排序是在原地进行的。
是否稳定: 否,堆排序是不稳定的排序算法。

在实际的项目中,通常不会有这么多的注释,但这里为了帮助理解每一步的过程,故添加了详细注释。

文章来源:https://blog.csdn.net/weixin_44738632/article/details/135730326
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。