C语言递归实现归并排序详解

什么是归并排序？

归并排序 （Merge Sort）是一种比较高效的排序算法，时间复杂度为 O(nlogn)，采用的是分冶策略，将一个数组分成两个数组，递归地对这两个数组分别排序，最终将它们合并成一个有序序列。

归并排序的原理

归并排序采用的是分治策略，主要分为以下三个步骤：

1. 将序列一分为二，对每一部分进行递归排序；
2. 将两个已排好序的数组合并成一个有序的数组；
3. 递归终止条件：序列长度为 1。

C语言递归实现归并排序

实现步骤

1. 定义函数 merge_sort，该函数接收数组的起始位置和结束位置两个参数；
2. 在 merge_sort 函数内部，先判断序列长度是否为 1，如果为 1，则直接返回即可；
3. 利用递归分别对左右两个数组进行排序；
4. 将已排好序的两个数组进行合并，合并后就是有序的数组。

代码实现如下：

void merge(int a[], int left, int mid, int right)
{
    int len = right - left + 1;
    int *temp = (int *)malloc(sizeof(int) * len);
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right)
    {
        temp[k++] = a[i] < a[j] ? a[i++] : a[j++];
    }
    while (i <= mid)
        temp[k++] = a[i++];
    while (j <= right)
        temp[k++] = a[j++];
    memcpy(a + left, temp, sizeof(int) * len);
    free(temp);
}

void merge_sort(int a[], int left, int right)
{
    if (left < right)
    {
        int mid = left + (right - left) / 2;
        merge_sort(a, left, mid);
        merge_sort(a, mid + 1, right);
        merge(a, left, mid, right);
    }
}

示例

给定一个数组 arr，长度为 n，对该数组进行排序，示例如下：

#include <stdio.h>

void merge(int a[], int left, int mid, int right)
{
    // 合并方法实现
}

void merge_sort(int a[], int left, int right)
{
    // 递归实现归并排序
}

int main()
{
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = 7;
    merge_sort(arr, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

输出结果为：3 9 10 27 38 43 82。

另外一个示例，给定一个已排序的数组 arr，长度为 n，对该数组进行排序，示例如下：

#include <stdio.h>

void merge(int a[], int left, int mid, int right)
{
    // 合并方法实现
}

void merge_sort(int a[], int left, int right)
{
    // 递归实现归并排序
}

int main()
{
    int arr[] = {3, 9, 10, 27, 38, 43, 82};
    int n = 7;
    merge_sort(arr, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

输出结果为：3 9 10 27 38 43 82。

总结

通过以上示例，我们可以清楚的了解归并排序的原理以及使用递归方式进行归并排序的实现方法。在实际编程时，我们只需要理解清楚原理，然后按照归并排序的实现步骤进行编程，就可以得到一个高效的排序算法。