数据结构：归并排序与分治思想详解

归并排序：分治思想的完美演绎

基本思想

归并排序（Merge Sort）是分治法（Divide and Conquer）的经典应用，由计算机科学先驱约翰·冯·诺依曼于 1945 年提出。其核心逻辑非常直观：将大问题分解为小问题，解决小问题后合并结果。

算法流程主要包含两个阶段：

1. 分（Divide）：递归地将当前数组分割成两个子数组，直到每个子数组只包含一个元素（此时天然有序）。
2. 治（Conquer）：将两个有序子数组合并成一个新的有序数组。

归并的核心操作是合并两个有序数组。简单来说，就是每次比较两个数组的首元素，将较小者放入新数组，直到所有元素合并完成。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 辅助函数：合并两个有序区间 [begin, mid] 和 [mid+1, end]
void _MergeSort(int* a, int* tmp, int begin, int end) {
    // 递归终止条件：当子数组只有一个元素时，无需再分
    if (begin == end) {
        return;
    }

    // 计算中间点
    int mid = (begin + end) / 2;

    // 注意：这里区间分为 [begin, mid] 和 [mid+1, end]
    // 如果分为 [begin, mid-1] 和 [mid, end] 会出现死循环或越界问题
    _MergeSort(a, tmp, begin, mid);
    _MergeSort(a, tmp, mid + 1, end);

    // 开始归并
    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int i = begin;

    // 只要两边都有元素，就继续比较
    while (begin1 <= end1 && begin2 <= end2) {
        if (a[begin1] < a[begin2]) {
            tmp[i++] = a[begin1++];
        } else {
            tmp[i++] = a[begin2++];
        }
    }

    // 处理剩余元素：其中一个区间结束后，将另一个区间的剩余元素全部拷贝
    while (begin1 <= end1) {
        tmp[i++] = a[begin1++];
    }
    while (begin2 <= end2) {
        tmp[i++] = a[begin2++];
    }

    // 将合并结果复制回原数组
    memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

// 归并排序入口函数
void MergeSort(int* a, int n) {
    // 分配临时数组空间
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL) {
        perror("malloc failed");
        return;
    }

    // 调用递归函数
    _MergeSort(a, tmp, 0, n - 1);

    // 释放临时数组
    free(tmp);
    tmp = NULL;
}

// 测试案例
int main() {
    int a[] = {2, 3, 5, 4, 7, 1};
    MergeSort(a, 6);
    for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

为什么区间划分要注意？

在递归拆分时，我们通常使用 [begin, mid] 和 [mid+1, end]。如果错误地写成 [begin, mid-1] 和 [mid, end]，在某些情况下会导致死循环。

假设数组有 10 个数据，下标从 0 到 9。如果取 mid = 4，按错误写法分成 [0, 3] 和 [4, 9]。在 [0, 3] 中 mid-1=1，分成 [0, 1] 和 [2, 3]。看似没问题，但在某些边界条件下，比如 [2, 3] 再次拆分时，若 mid 计算导致区间重叠或无法收敛，就会出问题。最稳妥的方式始终是让中间点归属左半部分，右半部分从 mid+1 开始。

操作	时间复杂度	说明
分解数组	O(log n)	递归深度
合并子数组	O(n)	每层需要遍历所有元素
总复杂度	O(n log n)	稳定的高效率排序

空间复杂度

归并排序需要 O(n) 的额外空间来存储合并过程中的临时数组。虽然递归调用栈占用 O(log n)，但通常临时数组的空间需求占主导地位。

非递归实现

除了递归，归并排序也可以用迭代方式实现。这可以理解为：先进行 1+1 归并，再进行 2+2 归并，以此类推。

void MergeSortNonR(int* a, int n) {
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL) {
        perror("malloc failed");
        return;
    }

    // gap 是当前归并子数组的大小，从 1 开始，每次翻倍
    int gap = 1;
    for (int i = 0; i < n; i += 2 * gap) {
        int begin1 = i, end1 = i + gap - 1;
        int begin2 = i + gap, end2 = i + 2 * gap - 1;

        // 第二组完全越界，跳过本次合并
        if (begin2 >= n) {
            break;
        }

        // 第二组的 begin2 没越界，但 end2 越界了，需要修正边界
        if (end2 >= n) {
            end2 = n - 1;
        }

        int j = i;
        while (begin1 <= end1 && begin2 <= end2) {
            if (a[begin1] < a[begin2]) {
                tmp[j++] = a[begin1++];
            } else {
                tmp[j++] = a[begin2++];
            }
        }

        while (begin1 <= end1) {
            tmp[j++] = a[begin1++];
        }
        while (begin2 <= end2) {
            tmp[j++] = a[begin2++];
        }

        // 将合并结果复制回原数组
        memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));
    }
    free(tmp);
    tmp = NULL;
}

非递归实现要点

1. gap 参数：控制当前归并的子数组大小，初始为 1，每次迭代翻倍。
2. 边界处理：这是最容易出错的地方。数组长度往往不是 2 的幂次方，必须处理以下两种情况：
   • 当第二个子数组完全越界（begin2 >= n），说明没有可合并的数据，直接跳出循环。
   • 当第二个子数组部分越界（end2 >= n），将其右边界修正为 n - 1。
3. 迭代过程：
   • 第 1 轮：1+1 归并 → 每个子数组大小为 1
   • 第 2 轮：2+2 归并 → 子数组大小为 2
   • 第 k 轮：2^k + 2^k 归并 → 子数组大小为 2^k

每一层的时间复杂度都是 O(n)，一共 log n 层，所以总时间复杂度依然是 O(n log n)。空间复杂度同样是 O(n)。

归并排序特性总结

1. 稳定排序：
   • 当两个元素相等时，归并排序优先选择左子数组的元素。
   • 保持相等元素的原始相对位置不变。
   • 适用于对稳定性有要求的场景（如多关键字排序）。
2. 时间复杂度：
   • 最优、平均、最差均为 O(n log n)。
   • 不受输入数据影响，性能非常稳定。
3. 空间复杂度：
   • O(n) 额外空间。
   • 递归实现还需 O(log n) 的栈空间。
4. 外排序优势：
   • 归并排序是少数能高效处理外部存储（如硬盘）数据的排序算法。
   • 特别适合处理超过内存容量的海量数据。
   • 工作流程：将大文件分割为能放入内存的小块 -> 内存中排序每个小块 -> 合并已排序的小块。

结语

归并排序是分治思想的完美体现，通过'分而治之'的策略达到 O(n log n) 的高效排序。尽管它需要 O(n) 的额外空间，但在现代计算机系统中，这种空间换时间的策略往往是值得的。

它的核心优势在于稳定可靠、性能不受数据分布影响，以及强大的外排序能力。这使得它在数据库系统、大数据处理等场景中发挥着不可替代的作用，是每个程序员必须掌握的经典算法之一。