企业官网建设流程全解析

归并排序是C语言算法学习中绕不开的经典，也是很多零基础读者第一次感受到递归威力的地方。这个排序的核心思想并不复杂：如果手上有两个已经排好序的序列，那么只要用一个双指针循环，就能在线性时间内合并出一个新的有序序列；如果一开始没有有序序列，就先把数组拆成单个元素，单元素天然有序，再两两合并。真正让人卡住的部分，通常是递归边界、临时数组管理和合并完成后如何把数据写回原数组。这篇文章从最小的子问题开始讲，逐步写出递归版和非递归版的C语言归并排序代码，并给出调试、验证和进阶练习方法。学完之后，你应该能独立写出稳定、可运行的归并排序代码，也能把它扩展到逆序对统计和链表排序场景。

1. 归并排序要解决什么问题：先看懂合并两个有序数组

1.1 最核心的子问题：两个有序数组合并成一个有序数组

假设手上有两个已经排好序的数组，例如1 3 5和2 4 6，想把它们合并成一个大数组1 2 3 4 5 6。最笨的办法是全部放进一个数组再排序，但这样浪费了“子序列已经有序”这个信息。归并排序的做法是使用两个指针：

• 指针i指向第一个有序序列当前元素。
• 指针j指向第二个有序序列当前元素。
• 比较arr[i]和arr[j]，较小的元素先放入结果数组。
• 放入结果数组后，对应指针向后移动。
• 当其中一个序列被取完，把另一个序列剩余部分直接复制到结果数组。

用 C 语言描述最核心的比较和移动逻辑就是这样：

while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[t++] = arr[i++]; } else { temp[t++] = arr[j++]; } }

这里mid是左半区间的结束位置，j从mid + 1开始；temp是临时数组。比较时写成<=而不是<是有原因的：当两个值相等时，优先取左边序列的元素，这样排序前位于左边的相同值，排序后仍然位于左边，归并排序因此是稳定排序。

1.2 分治思想：把一个无序大数组拆成两个更小的数组

合并两个有序数组本身不能排序，因为原始数组是无序的。这时要用到分治思想：如果数组本身只有一个元素，它天然有序；如果数组有多个元素，就把它从中间切开，递归排序左半部分和右半部分，等左右两部分都有序后再合并。

用一张拆分顺序图可以看得更清楚。假设数组是：

38 27 43 3 9 82 10

拆分过程是：

38 27 43 3 9 82 10 ├── 38 27 43 3 │ ├── 38 27 │ │ ├── 38 │ │ └── 27 │ └── 43 3 │ ├── 43 │ └── 3 └── 9 82 10 ├── 9 82 │ ├── 9 │ └── 82 └── 10

拆分到单元素后，整个数组都是由“天然有序”的单个元素组成的，接下来要做的事情就是不断合并，把有序子数组的长度从 1 变成 2、从 2 变成 4，最终变成整个数组长度。

1.3 复杂度与稳定性：为什么归并排序值得学

归并排序的时间复杂度稳定在O(n log n)，最坏情况也是O(n log n)，这是它比快速排序更可控的地方。递归拆分数组，大约需要log2 n层；每一层合并所有元素的总代价是O(n)，所以总复杂度是O(n log n)。

空间复杂度是O(n)，因为合并时需要一块和原数组等长的临时数组。它也不是原地排序算法。

从学习角度看，归并排序是理解分治、递归调用栈、双指针合并和空间换时间策略的一块很好的跳板。很多初学者觉得它比冒泡排序难，是因为冒泡排序只需要一层循环和一次交换，而归并排序需要拆成“递归函数”和“合并函数”两部分，还要处理临时数组的回写。这篇文章后续的代码会把这两个函数拆得很清楚。

2. 写代码前的准备：区间定义、临时数组和环境

2.1 用命令行编译器跑通最小环境

在学习阶段，不一定要先打开 IDE。使用命令行编译器能让你更清楚地看到编译、运行、报错这一整条链路。推荐安装gcc，装好后先检查版本：

gcc --version

如果能看到类似gcc (GCC) 13.x.x的输出，说明编译器可用。用 VS Code 写代码时，只需要安装 C/C++ 扩展，然后在终端里编译运行。一个最简单的编译命令是：

gcc -Wall -Wextra -o merge_sort merge_sort.c ./merge_sort

-Wall和-Wextra会打开常见警告。初学者写归并排序很容易出现变量声明了但没使用、数组下标可能越界等问题，编译器的警告是第一条防线。

如果本机没有安装gcc，使用在线编译器也能运行本文示例代码，但要注意在线编译器通常对运行内存和时间有限制，验证小数组排序没有问题，做大规模随机测试时还是建议使用本机环境。

2.2 区间定义：选择左闭右闭区间

C 语言数组下标从0开始，归并排序最常见的区间写法是左闭右闭区间[left, right]，意思是数组中第left个元素到第right个元素都参与本次排序。

• 区间长度是right - left + 1。
• 中间位置mid = left + (right - left) / 2。
• 左半部分是[left, mid]。
• 右半部分是[mid + 1, right]。
• 递归终止条件是left >= right，表示当前区间长度不超过 1。

mid的计算建议写成left + (right - left) / 2，而不是(left + right) / 2。如果数组特别大，left + right有可能超过int能表示的范围，导致结果变成负数。虽然普通学习场景不会遇到这种极端情况，但养成这个习惯没有坏处。

区间定义不同会导致后续所有代码边界不同。很多初学者把左闭右闭和左闭右开混着写，结果排序后出现元素丢失或重复。后面排查部分会专门讨论这类问题。

2.3 临时数组只分配一次，不要每层递归都分配

归并排序需要一块临时数组暂存合并结果。一个典型误区是在merge函数内部每次调用malloc，这样虽然代码看起来简单，但每次归并都要申请和释放内存，性能很差，而且如果忘记free还会造成内存泄漏。

推荐做法是在main函数里一次性分配一块长度为数组总长度的临时数组，然后把它的指针传给递归函数和合并函数：

int *temp = (int *)malloc(len * sizeof(int)); if (temp == NULL) { printf("malloc failed\n"); return 1; }

分配失败一定要处理。学习阶段数组比较小，几乎不会失败，但在作业题或竞赛题中，数组可能开到几十万甚至上百万，指针返回NULL后程序继续运行，会直接段错误。

3. 递归版归并排序：C语言完整实现与过程拆解

3.1 第一步：编写 merge 函数，合并两个有序区间

merge函数负责把同一个数组中的两个相邻有序区间合并成一个大的有序区间。两个区间的范围是[left, mid]和[mid + 1, right]。完整实现如下：

#include <stdio.h> #include <stdlib.h> void merge(int arr[], int left, int mid, int right, int temp[]) { int i = left; int j = mid + 1; int t = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[t++] = arr[i++]; } else { temp[t++] = arr[j++]; } } while (i <= mid) { temp[t++] = arr[i++]; } while (j <= right) { temp[t++] = arr[j++]; } int k = left; t = 0; while (k <= right) { arr[k++] = temp[t++]; } }

这段代码里需要注意的点：

• i从left开始，j从mid + 1开始，两个指针分别对应两个有序区间。
• 第一个while是双指针比较，哪个元素小就先把哪个放入temp。
• 第二个和第三个while负责处理剩余元素。因为两个区间长度不一定相等，总有一个区间会先耗尽。
• 最后一步要把temp中的内容回写到arr的对应位置。如果漏掉这一步，排序结果不会出现在原数组中，这也是归并排序最常见的问题之一。

temp的下标直接从 0 开始即可，因为最后回写时是针对[left, right]这段区间，而不是整个数组。

3.2 第二步：编写 mergeSort 递归函数

递归函数负责把数组拆到足够小，再调用merge完成合并。逻辑非常直观：

void mergeSort(int arr[], int left, int right, int temp[]) { if (left >= right) { return; } int mid = left + (right - left) / 2; mergeSort(arr, left, mid, temp); mergeSort(arr, mid + 1, right, temp); merge(arr, left, mid, right, temp); }

递归执行顺序可以描述如下：

1. 先判断区间是否已经不需要排序，也就是区间里只有一个元素或没有元素。
2. 计算出中间位置。
3. 递归排序左半部分。
4. 递归排序右半部分。
5. 左右两部分都有序后，合并它们。

在递归排序左半部分时，程序会一路走到底，直到左半部分也被拆成单元素区间。这个“先拆左边、再拆右边、最后合并”的顺序，可以通过缩进打印递归调用来观察，稍后会给出调试方法。

3.3 完整示例代码与运行结果

把merge、mergeSort和一个简单的main函数组合起来，就是一份最小可运行代码：

#include <stdio.h> #include <stdlib.h> void merge(int arr[], int left, int mid, int right, int temp[]) { int i = left; int j = mid + 1; int t = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[t++] = arr[i++]; } else { temp[t++] = arr[j++]; } } while (i <= mid) { temp[t++] = arr[i++]; } while (j <= right) { temp[t++] = arr[j++]; } int k = left; t = 0; while (k <= right) { arr[k++] = temp[t++]; } } void mergeSort(int arr[], int left, int right, int temp[]) { if (left >= right) { return; } int mid = left + (right - left) / 2; mergeSort(arr, left, mid, temp); mergeSort(arr, mid + 1, right, temp); merge(arr, left, mid, right, temp); } void printArray(int arr[], int len) { for (int i = 0; i < len; i++) { printf("%d ", arr[i]); } printf("\n"); } int main(void) { int arr[] = {38, 27, 43, 3, 9, 82, 10}; int len = sizeof(arr) / sizeof(arr[0]); int *temp = (int *)malloc(len * sizeof(int)); if (temp == NULL) { printf("malloc failed\n"); return 1; } printf("排序前: "); printArray(arr, len); mergeSort(arr, 0, len - 1, temp); printf("排序后: "); printArray(arr, len); free(temp); return 0; }

编译运行后，预期输出：

排序前: 38 27 43 3 9 82 10 排序后: 3 9 10 27 38 43 82

sizeof(arr) / sizeof(arr[0])是 C 语言求数组长度的常见写法。这个写法只在“数组名”还未退化为指针时有效，所以不要在函数内部对一个传入的数组参数执行这一句。

3.4 用手推过程理解每一轮合并

只看代码很难建立直观感受，建议对照下面的拆分表格和合并表格走一遍。

原始数组：

38 27 43 3 9 82 10

拆分过程：

合并过程按递归返回顺序进行：

这个表格本质上是归并排序“文字动画”的关键帧。如果能把每一轮合并后的数组打印出来，你看到的就是一个逐步有序的过程。

4. 非递归归并排序：不写递归也能完成二路归并

4.1 为什么要学非递归版本

递归版归并排序好懂，但有两个问题：一是递归调用栈在极端情况下仍然可能成为限制；二是在某些嵌入式或底层开发中，使用递归需要格外谨慎。非递归版本用循环控制每次合并的区间宽度，逻辑上更能体现归并排序“先相邻合并，再扩大合并范围”的本质。

递归版和非递归版的对比：

4.2 核心流程：宽度从 1 开始成倍增加

非递归归并排序的思路是：一开始把整个数组看成很多个长度为 1 的有序块，然后每两个相邻块合并成长度为 2 的有序块；下一次再把长度为 2 的块两两合并成长度为 4 的块。直到当前块宽度超过数组长度，整个数组就有序了。

用代码描述外层和内层循环：

void mergeSortIterative(int arr[], int len) { int *temp = (int *)malloc(len * sizeof(int)); if (temp == NULL) { return; } for (int width = 1; width < len; width *= 2) { for (int left = 0; left < len; left += 2 * width) { int mid = left + width - 1; if (mid >= len - 1) { continue; } int right = left + 2 * width - 1; if (right >= len) { right = len - 1; } merge(arr, left, mid, right, temp); } } free(temp); }

解释几个关键点：

• width是当前每个有序块的长度，初始为 1。
• 内层循环每次处理两个相邻块，左块范围是[left, mid]，右块范围是[mid + 1, right]。
• mid = left + width - 1，这是左块的结束位置。
• 如果mid >= len - 1，说明当前块已经是数组最后一块，没有右块可以合并，直接跳过。
• 正常的右边界是left + 2 * width - 1，但数组末尾可能凑不齐长度，所以如果越界，要裁剪到len - 1。
• 这里复用了前面的merge函数，因为合并逻辑完全相同。

4.3 非递归版本运行验证

把mergeSortIterative放进之前的测试程序，替换main中的调用：

mergeSortIterative(arr, len);

对{38, 27, 43, 3, 9, 82, 10}运行后的输出与递归版完全一致：

排序前: 38 27 43 3 9 82 10 排序后: 3 9 10 27 38 43 82

非递归版本最容易犯错的地方是最后的边界处理。可以单独打印每一轮的left、mid、right来观察区间是否正确，尤其是数组长度不是 2 的幂时，右边界裁剪那一步不能漏。

5. 排序结果不对怎么办：调试思路和高频错误排查

5.1 用随机数组和 qsort 对比验证正确性

学习算法时，只用一组数据验证远远不够。推荐写一个小测试函数：生成随机数组，用自己写的归并排序排序，再用 C 标准库的qsort对同样数据排序，最后逐个元素比较。

#include <stdlib.h> int compareInt(const void *a, const void *b) { return (*(int *)a - *(int *)b); } void testRandomSort() { for (int n = 1; n <= 1000; n++) { int *arr = (int *)malloc(n * sizeof(int)); int *expected = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) { arr[i] = rand() % 1000; expected[i] = arr[i]; } mergeSort(arr, 0, n - 1, temp); qsort(expected, n, sizeof(int), compareInt); for (int i = 0; i < n; i++) { if (arr[i] != expected[i]) { printf("mismatch at n=%d, index=%d\n", n, i); free(arr); free(expected); return; } } free(arr); free(expected); } printf("all test passed\n"); }

这个测试能覆盖大量随机情况，比人工肉眼检查可靠得多。注意示例中的temp需要在测试前分配，并且长度为n。

5.2 打印递归调用过程，理解程序执行顺序

如果递归逻辑混乱，可以在mergeSort中增加缩进日志，打印每次排序的区间：

void mergeSortDebug(int arr[], int left, int right, int temp[], int depth) { for (int i = 0; i < depth; i++) { printf(" "); } printf("sort [%d..%d]\n", left, right); if (left >= right) { return; } int mid = left + (right - left) / 2; mergeSortDebug(arr, left, mid, temp, depth + 1); mergeSortDebug(arr, mid + 1, right, temp, depth + 1); merge(arr, left, mid, right, temp); }

对长度为 7 的数组调用后，输出大致为：

sort [0..6] sort [0..3] sort [0..1] sort [0..0] sort [1..1] sort [2..3] sort [2..2] sort [3..3] sort [4..6] sort [4..5] sort [4..4] sort [5..5] sort [6..6]

从输出可以清楚看出：程序并不是先处理完整个左半部分再处理右半部分，而是优先递归到最深层，然后逐层返回并合并。理解了递归执行顺序，排查越界问题会容易很多。

5.3 高频错误排查表

5.4 把排序过程变成文字动画

很多人对“动画讲解”没有概念，其实用printf打印关键步骤，就能形成最简单的文字动画。在每次merge结束后调用printArray，可以看到数组逐步变得有序。为了看得更明显，还可以让程序短暂暂停：

#include <unistd.h> // 在 merge 末尾加上： printArray(arr, len); // sleep(1);

输出效果类似：

27 38 43 3 9 82 10 27 38 3 43 9 82 10 3 27 38 43 9 82 10 3 27 38 43 9 82 10 3 27 38 43 9 10 82 3 9 10 27 38 43 82

这种逐行打印的过程，就是理解归并排序执行顺序的关键。如果想做成真正的可视化，可以在此基础上用文件输出或图形库展示，但核心思路仍然是“每轮合并后呈现一次状态”。

6. 归并排序的进阶用法、常见题型与学习建议

6.1 统计逆序对：归并排序最经典扩展

所谓逆序对，是指数组中一对下标i < j，但arr[i] > arr[j]的元素对。求逆序对数量如果暴力两层循环，时间复杂度是O(n^2)；利用归并排序，可以在合并阶段顺便统计，把复杂度降到O(n log n)。

原理是：当合并[left, mid]和[mid + 1, right]时，如果发现arr[i] > arr[j]，说明左区间中从i到mid的所有元素都大于arr[j]。于是：

逆序对数量 += mid - i + 1

示例代码片段：

long long inversion = 0; void mergeCount(int arr[], int left, int mid, int right, int temp[]) { int i = left; int j = mid + 1; int t = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[t++] = arr[i++]; } else { inversion += (mid - i + 1); temp[t++] = arr[j++]; } } while (i <= mid) { temp[t++] = arr[i++]; } while (j <= right) { temp[t++] = arr[j++]; } int k = left; t = 0; while (k <= right) { arr[k++] = temp[t++]; } }

需要注意，逆序对数量可能非常大，使用long long而不是普通的int。

6.2 链表排序：归并排序比快速排序更适合链表

在 C 语言中，对于单向链表做排序，快速排序通常不太方便，因为需要随机访问和中轴值交换；归并排序只需要改指针，非常适合链表。核心思路是：

1. 用快慢指针找到链表中点。
2. 递归排序左半段和右半段。
3. 合并两个有序链表。

具体接口可以设计成：

struct Node { int data; struct Node *next; }; struct Node *getMiddle(struct Node *head); struct Node *mergeList(struct Node *l1, struct Node *l2); struct Node *mergeSortList(struct Node *head);

合并链表的逻辑和数组归并几乎一样，区别是数组用下标访问，链表用next指针访问。练习这个题目能进一步巩固归并排序的分治思想。

6.3 从内存排序到外部排序

当数据量大到无法全部装入内存时，普通排序算法就不能直接使用了。外部排序的基本思想仍然是归并：先把大文件切分成多个能读入内存的块，每块排序后写到磁盘，再用多路归并把多个有序块合并成一个更大的有序块。

归并排序在这里并不只是一个考试知识点，而是一整套“分而治之”方法的源头。理解数组归并后，再理解“多路归并”“败者树”等外部排序优化会有更好基础。

6.4 两小时学习计划与自测清单

如果目标是“零基础 2 小时搞懂归并排序”，可以参考下面这个节奏：

学习过程中可以自测以下问题：

• 归并排序的时间复杂度、空间复杂度、稳定性分别是什么？为什么？
• 如果merge函数最后不回写数组，程序会发生什么？
• 合并时使用<和<=对稳定性有什么影响？
• 数组长度为奇数时，非递归版本的右边界如何处理？
• 为什么临时数组只分配一次而不是每层递归都分配？

归并排序这门功课，最关键的不是把代码背下来，而是把“合并两个有序数组”这个子问题理解透。递归只是让数组能够被拆到符合条件的方式，真正决定排序结果正确性的，是每一个合并步骤里的边界和回写逻辑。把这一步写稳、调通，后续的逆序对、链表排序、外部排序等题目都会迎刃而解。