C语言归并排序详解：递归与非递归实现对比

归并排序原理概述

归并排序（Merge Sort）的核心在于“归并”。它采用分治策略，将待排序序列不断二分为若干子序列，直到每个子序列仅包含一个元素（自然有序），然后逐步将这些子序列两两合并，最终形成一个完整的有序序列。这种算法保证了极佳的稳定性，且在最坏情况下的性能表现依然优异。

递归实现：自顶向下分治

递归方式的逻辑直观且符合人类认知。它将一个大问题拆解为结构相同的小问题，直至触及基准条件（子序列长度为1），随后在回溯过程中完成合并操作。

第1步：定义数据结构与辅助函数

首先定义顺序表结构 SqList，其中数组索引 0 通常预留或用于特定逻辑，有效数据从索引 1 开始。同时提供基础的交换与打印接口以便观察过程。

#include <stdio.h>
#include <stdbool.h>

#define MAXSIZE 9

typedef struct {
    int r[MAXSIZE+1]; // 索引0暂不存实际数据
    int len;
} SqList;

void swap(SqList *L, int i, int j) {
    int tmp = L->r[i];
    L->r[i] = L->r[j];
    L->r[j] = tmp;
}

第2步：实现核心的 merge 合并函数

merge 函数负责将两个相邻的有序子序列合并为一个有序序列。输入源数组 sr 和目的数组 tr，参数 s、m、t 分别代表左子序列起点、左右分割点、右子序列终点。

void merge(int sr[], int tr[], int s, int m, int t) {
    int j, k, l;
    j = m + 1; // 第二个子序列起始位置
    k = s;     // 目标数组游标

    // 比较两个子序列当前元素，较小者放入目标数组
    while (s <= m && j <= t) {
        if (sr[s] < sr[j]) {
            tr[k++] = sr[s++];
        } else {
            tr[k++] = sr[j++];
        }
    }

    // 处理剩余未比较完的子序列
    while (s <= m) {
        tr[k++] = sr[s++];
    }
    while (j <= t) {
        tr[k++] = sr[j++];
    }
}

第3步：实现 msort 递归拆分与调用

使用 msort 进行递归调用。当区间只有一个元素时直接赋值；否则计算中点 m，先递归处理左半部分和右半部分，最后调用 merge 将结果合并。注意中间结果暂存于 tmpr 临时数组中。

void msort(int sr[], int tr[], int s, int t) {
    int m;
    int tmpr[MAXSIZE+1]; 

    if (s == t) {
        tr[s] = sr[s];
    } else {
        m = (s + t) / 2;
        msort(sr, tmpr, s, m);      // 排左边
        msort(sr, tmpr, m + 1, t);  // 排右边
        merge(tmpr, tr, s, m, t);   // 合并
    }
}

void merge_sort(SqList *L) {
    msort(L->r, L->r, 1, L->len);
}

非递归实现：自底向上迭代

非递归方式避免了函数调用的栈开销。它不再从整体开始分解，而是直接从长度为 1 的子序列开始，依次合并长度为 2、4、8... 的子序列，直到覆盖整个数组长度。这一过程复用了相同的 merge 函数。

第1步：实现单次扫描合并 pass 函数

merge_pass 负责遍历数组，执行相邻子序列的合并。参数 k 代表当前子序列的长度。循环结束后，需处理尾部可能残留的不完整子序列。

void merge_pass(int sr[], int tr[], int k, int len) {
    int i = 1;
    // 只要剩余部分足够构成两个长为k的子序列，就执行合并
    while (i < len - 2 * k + 1) { 
        merge(sr, tr, i, i + k - 1, i + 2 * k - 1);
        i += 2 * k;
    }

    // 处理尾部剩余元素
    if (i < len - k + 1) {
        merge(sr, tr, i, i + k - 1, len);
    } else {
        // 如果只剩不到一个k长度的序列，直接拷贝即可
        while (i < len) {
            tr[i] = sr[i];
            i++;
        }
    }
}

第2步：构建外层循环控制流程

在 merge_sort 中动态申请临时内存 tr，并通过循环递增步长 k。每次循环包含两次 merge_pass 调用，实现数据在源数组和临时数组间的来回传递，直至总长度达到要求。

void merge_sort(SqList *L) {
    int *tr = (int *)malloc(L->len * sizeof(int));
    int k = 1;
    /* 
     * 非递归核心：步长k从1倍增，模拟递归的深度展开
     */ 
    while (k < L->len) {
        merge_pass(L->r, tr, k, L->len); // 长度1->2
        k++;
        merge_pass(tr, L->r, k, L->len); // 长度2->4
        k++;
    }
    free(tr); // 记得释放内存
}

递归与非递归深度对比

虽然两种方法的时间复杂度一致，但在系统资源消耗上存在显著差异，理解这些差异有助于在实际开发中选择更优方案。

时间复杂度

无论是递归还是非递归，归并排序都需要进行 log₂n 层拆分/合并，每层遍历所有 n 个元素进行比较复制。因此，两者的时间复杂度均为 O(nlogn)。

空间复杂度与栈开销

这是两者最大的区别所在：

• 递归方式：由于涉及多层函数调用，需要维护系统调用栈。其递归深度为 log₂n，理论上额外空间为 O(logn)。但实际上，如果递归过深，极易导致栈溢出（Stack Overflow）。
• 非递归方式：完全消除递归调用，不再依赖系统栈。只需分配一个与原数组等大的临时缓冲区，空间复杂度稳定为 O(n)。虽然静态看内存占用略高，但彻底规避了栈溢出的风险，且在大数据量下往往因无函数跳转而表现出更高的执行效率。

运行测试与验证

以下测试使用了初始无序序列 {50, 10, 90, 30, 70, 40, 80, 60, 20}（索引0占位符999不参与排序）。程序编译后运行，两种算法均能将数据正确按升序排列。

递归版本输出结果

➜ c gcc sort_merge.c && ./a.out
after merge_sort:
index: 0, value: 999
index: 1, value: 10
index: 2, value: 20
index: 3, value: 30
index: 4, value: 40
index: 5, value: 50
index: 6, value: 60
index: 7, value: 70
index: 8, value: 80
index: 9, value: 90

非递归版本输出结果

➜ c gcc sort_merge_norecursive.c && ./a.out
after merge_sort2:
index: 0, value: 999
index: 1, value: 10
index: 2, value: 20
index: 3, value: 30
index: 4, value: 40
index: 5, value: 50
index: 6, value: 60
index: 7, value: 70
index: 8, value: 80
index: 9, value: 90

以上就是C语言归并排序递归与非递归实现的详细内容，更多关于C语言排序算法的资料请关注本站其它相关文章！