C语言归并排序详解（手把手教你掌握分治法排序算法）

归并排序的步骤

1. 分解：将待排序的数组从中间一分为二，形成左右两个子数组。
2. 递归排序：对左右两个子数组分别进行归并排序（递归调用自身）。
3. 合并：将两个已排序的子数组合并成一个有序的大数组。

C语言实现归并排序

下面我们用 C 语言完整实现归并排序算法。代码包含两个函数：merge() 负责合并两个有序数组，mergeSort() 负责递归地拆分和调用合并。

// 归并排序的合并函数void merge(int arr[], int left, int mid, int right) {    int i, j, k;    int n1 = mid - left + 1;    int n2 = right - mid;    // 创建临时数组    int L[n1], R[n2];    // 拷贝数据到临时数组    for (i = 0; i < n1; i++)        L[i] = arr[left + i];    for (j = 0; j < n2; j++)        R[j] = arr[mid + 1 + j];    // 合并临时数组回原数组    i = 0; // 左子数组的起始索引    j = 0; // 右子数组的起始索引    k = left; // 原数组的起始索引    while (i < n1 && j < n2) {        if (L[i] <= R[j]) {            arr[k] = L[i];            i++;        } else {            arr[k] = R[j];            j++;        }        k++;    }    // 复制剩余元素（如果有的话）    while (i < n1) {        arr[k] = L[i];        i++;        k++;    }    while (j < n2) {        arr[k] = R[j];        j++;        k++;    }}// 归并排序主函数void mergeSort(int arr[], int left, int right) {    if (left < right) {        int mid = left + (right - left) / 2;        mergeSort(arr, left, mid);       // 排序左半部分        mergeSort(arr, mid + 1, right);  // 排序右半部分        merge(arr, left, mid, right);     // 合并两部分    }}

如何使用这段代码？

你可以在 main() 函数中调用 mergeSort() 来对任意整型数组进行排序：

#include <stdio.h>// 此处插入上面的 merge() 和 mergeSort() 函数int main() {    int arr[] = {38, 27, 43, 3, 9, 82, 10};    int n = sizeof(arr) / sizeof(arr[0]);    printf("排序前: ");    for (int i = 0; i < n; i++)        printf("%d ", arr[i]);    mergeSort(arr, 0, n - 1);    printf("\n排序后: ");    for (int i = 0; i < n; i++)        printf("%d ", arr[i]);    return 0;}

算法复杂度分析

• 时间复杂度：无论最好、最坏还是平均情况，都是 O(n log n)，非常稳定。
• 空间复杂度：O(n)，因为需要额外的临时数组来存储数据。
• 稳定性：归并排序是稳定的排序算法（相等元素的相对位置不会改变）。

总结

通过本教程，你已经掌握了 C语言归并排序 的核心原理与实现方法。归并排序作为经典的 分治法排序 算法，不仅效率高，而且逻辑清晰，非常适合初学者理解递归与分治思想。希望这篇 归并排序算法详解 能帮助你在学习 C语言排序教程 的道路上更进一步！

动手试试吧！修改数组内容，观察排序结果，加深理解。