C / C++ / 系统课时
归并排序怎样合并有序区间
归并排序怎样合并有序区间
归并排序真正决定正确性的地方不是“拆成两半”,而是怎样把两个已经有序的区间稳定地合成一个更大的有序区间。本节用 C 语言实现完整归并排序,并重点追踪双指针合并、剩余元素复制以及额外数组的作用。
学习目标
- 理解两个有序区间如何通过双指针线性合并
- 能用 C 语言实现递归拆分与归并过程
- 能解释归并排序的时间复杂度和额外空间来源
合并有序区间的核心
假设数组的 left..mid 和 mid+1..right 已分别有序。合并时分别用指针 i、j 指向两个区间的当前元素,再用 k 指向临时数组的写入位置。
每次比较 a[i] 与 a[j],把较小者写入临时数组并移动对应指针。某一侧耗尽后,另一侧剩余元素已经保持有序,可以直接顺序复制。最后再把临时数组对应范围写回原数组。

完整实现
下面的程序使用一个临时数组贯穿整个递归过程,避免每次合并都重复申请空间。比较时使用 <=,当两个元素相等时优先取左区间元素,因此该实现保持稳定性。
c
#include <stdio.h>
void merge(int a[], int temp[], int left, int mid, int right) {
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (a[i] <= a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
while (i <= mid) {
temp[k++] = a[i++];
}
while (j <= right) {
temp[k++] = a[j++];
}
for (i = left; i <= right; ++i) {
a[i] = temp[i];
}
}
void merge_sort(int a[], int temp[], int left, int right) {
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;
merge_sort(a, temp, left, mid);
merge_sort(a, temp, mid + 1, right);
merge(a, temp, left, mid, right);
}
int main(void) {
int a[] = {8, 3, 6, 2, 7, 1, 5, 4};
int n = (int)(sizeof(a) / sizeof(a[0]));
int temp[8];
merge_sort(a, temp, 0, n - 1);
for (int i = 0; i < n; ++i) {
printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
}
return 0;
}预期输出
text
1 2 3 4 5 6 7 8为什么是 O(n log n)
递归拆分会形成约 log n 层。每一层虽然包含多个子区间,但所有合并操作处理的元素总数仍是 n,因此总时间复杂度为 O(n log n)。
合并阶段需要临时数组保存当前结果。上面的实现一次准备长度为 n 的辅助数组,所以额外空间复杂度为 O(n);递归调用本身还会占用 O(log n) 的栈空间,但主导项仍是辅助数组。
容易出错的边界
最常见的错误是把左右区间边界写乱。若左区间是 left..mid,右区间必须从 mid + 1 开始;循环条件也必须包含端点,即 i <= mid 和 j <= right。
另一个错误是只完成临时数组的合并,却忘记写回原数组。这样上层递归看到的子区间仍然无序,后续合并会立刻失效。归并排序的关键不是“递归调用了几次”,而是保证每次返回前,当前区间已经真正变成有序区间。
按自己的节奏,确认真正理解。