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。

另一个错误是只完成临时数组的合并,却忘记写回原数组。这样上层递归看到的子区间仍然无序,后续合并会立刻失效。归并排序的关键不是“递归调用了几次”,而是保证每次返回前,当前区间已经真正变成有序区间。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

归并排序怎样合并有序区间

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通