【C++】深入解析归并排序

---

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C++

---

---

---

💯前言

• 归并排序（Merge Sort） 是一种经典的分治算法，因其高效性与稳定性而在计算机科学中占据重要地位。它以清晰的逻辑和出色的性能在各类排序算法中脱颖而出。本篇将深入探讨归并排序的基本原理、实现步骤、代码剖析以及优化方法，帮助您全面掌握这一基础算法。
  C++ 参考手册
  

---

💯归并排序简介

归并排序是基于分治（Divide and Conquer）思想的排序算法，其核心思想是将待排序数组划分为多个子数组，递归对每个子数组排序后再合并为一个有序数组。其主要特性包括：

1. 时间复杂度： 在所有情况下（最佳、最坏、平均），归并排序的时间复杂度均为$O(n\log n)$。
2. 空间复杂度： 需要额外的$O(n)$ 空间来存储临时数组。
3. 稳定性： 是稳定的排序算法，能够保留相同元素的原始顺序。

归并排序尤其适合处理大规模数据集，特别是在需要稳定排序的场景中（如数据库多字段排序）。其分而治之的结构清晰明确，也使其成为教学和研究中的常用算法。

---

💯代码实现及详解

以下是归并排序的核心代码：

// 对 array 数组下标范围在 [start, end) 的元素进行排序
void MergeSort(int *array, int start, int end) {
    // 递归终止条件
    if (start == end - 1)
        return;

    // 对两个子数组分开排序
    int mid = (end + start) / 2;
    MergeSort(array, start, mid);
    MergeSort(array, mid, end);

    // 分配临时的空间存放合并元素
    int *tmp = new int[end - start];

    // 依次取出子数组的元素，进行合并
    int left_idx = start, right_idx = mid, i = 0;
    while (left_idx < mid && right_idx < end) {
        if (array[left_idx] < array[right_idx])
            tmp[i++] = array[left_idx++];
        else
            tmp[i++] = array[right_idx++];
    }

    // 如果有子数组元素没有取完，则全部并入临时空间
    while (left_idx < mid)
        tmp[i++] = array[left_idx++];
    while (right_idx < end)
        tmp[i++] = array[right_idx++];

    // 从临时空间复制回原数组
    for (int i = 0, idx = start; i < end - start; i++, idx++)
        array[idx] = tmp[i];

    // 释放临时空间
    delete[] tmp;
}

---

💯分步解析代码

1. 递归终止条件

if (start == end - 1)
    return;

• 当子数组的长度为 1 时，数组被视为已经有序，无需进一步排序。
• 此时递归终止，返回上一层。

递归终止条件是分治算法的核心部分。如果递归不终止，将导致程序陷入死循环，最终崩溃。

---

2. 划分子数组

int mid = (end + start) / 2;
MergeSort(array, start, mid);
MergeSort(array, mid, end);

• 通过计算中点 mid，将数组分为两部分：
  • 左子数组范围 [start, mid)。
  • 右子数组范围 [mid, end)。
• 递归对两个子数组排序。

划分步骤是归并排序的分治思想体现。通过不断二分，问题规模递减至可以直接解决的最小单位。

---

3. 分配临时空间

int *tmp = new int[end - start];

• 使用临时数组 tmp 存储合并后的有序结果，避免在原数组上直接操作引发数据混乱。

---

4. 合并两个子数组

---

双指针合并

int left_idx = start, right_idx = mid, i = 0;
while (left_idx < mid && right_idx < end) {
    if (array[left_idx] < array[right_idx])
        tmp[i++] = array[left_idx++];
    else
        tmp[i++] = array[right_idx++];
}

• 初始化双指针：
  • left_idx 指向左子数组的起始位置。
  • right_idx 指向右子数组的起始位置。
• 比较左右子数组当前元素，将较小值存入 tmp。

---

处理剩余元素

while (left_idx < mid)
    tmp[i++] = array[left_idx++];
while (right_idx < end)
    tmp[i++] = array[right_idx++];

• 若某一子数组元素已全部存入 tmp，则将另一子数组的剩余元素直接追加到 tmp 中。

双指针策略使得合并过程高效且简单，是归并排序的重要优化点。

---

5. 复制回原数组

for (int i = 0, idx = start; i < end - start; i++, idx++)
    array[idx] = tmp[i];

• 将 tmp 中的有序数据复制回原数组的对应位置。

---

6. 释放临时空间

delete[] tmp;

• 释放动态分配的临时空间，避免内存泄漏。

---

💯算法核心思想

---

1. 分治策略

归并排序通过递归将问题分解为更小的子问题，最终逐步解决并合并结果。分治策略是许多高效算法的基础思想，如快速排序、二分查找等。

---

2. 递归树分析

• 递归树的深度为$\log n$，每层递归的合并操作需要$O(n)$。
• 总时间复杂度为$O(n\log n)$。

---

3. 稳定性

• 在合并过程中，若左右子数组元素相等，优先选择左子数组元素，确保算法稳定。
• 这一特性在多字段排序场景中尤为重要。

---

💯优化与扩展

---

1. 减少临时空间分配

通过预分配全局临时数组，在整个排序过程中重复使用，以降低空间消耗并提升效率。

---

代码优化示例：

void MergeSort(int *array, int *tmp, int start, int end) {
    if (start == end - 1)
        return;

    int mid = (end + start) / 2;
    MergeSort(array, tmp, start, mid);
    MergeSort(array, tmp, mid, end);

    int left_idx = start, right_idx = mid, i = start;
    while (left_idx < mid && right_idx < end) {
        if (array[left_idx] < array[right_idx])
            tmp[i++] = array[left_idx++];
        else
            tmp[i++] = array[right_idx++];
    }
    while (left_idx < mid)
        tmp[i++] = array[left_idx++];
    while (right_idx < end)
        tmp[i++] = array[right_idx++];

    for (int i = start; i < end; i++)
        array[i] = tmp[i];
}

---

2. 迭代版归并排序

• 通过迭代方式取代递归实现，避免深度递归可能导致的栈溢出问题。
• 逐步合并小规模子数组直至整个数组有序。

---

💯总结

• 
  归并排序 是一种高效稳定的排序算法，特别适合处理大规模数据和需要稳定性的场景。其分治思想使其在解决其他复杂问题中也具有重要的借鉴意义。通过优化空间分配或实现迭代版本，归并排序可以进一步提升性能，适应更多实际应用需求。

---

---

原文地址：https://blog.csdn.net/2201_75539691/article/details/144379692

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！