C语言实现归并排序算法：分治法策略及示例

本教程将使用 C 语言详细讲解如何利用分治法设计归并排序算法。我们将提供完整的代码示例，并用数组 {8, 3, 2, 9, 7, 1, 5, 4} 来验证算法的正确性。

分治法策略

归并排序是一种基于分治法策略的排序算法。分治法是指将一个问题分解成多个规模更小的子问题，解决子问题，最后将子问题的解合并起来得到原问题的解。在归并排序中，我们通过以下步骤进行排序：

分解： 将待排序数组递归地分成两个子数组，直到每个子数组只包含一个元素。
解决： 对每个只包含一个元素的子数组进行排序（默认已排序）。
合并： 将已排序的子数组合并成一个更大的已排序数组。

代码实现

以下是使用分治法设计的归并排序程序的 C 语言实现：

#include <stdio.h>

// 归并两个子数组
void merge(int arr[], int left[], int right[], int leftSize, int rightSize) {
    int i = 0, j = 0, k = 0;
    
    while (i < leftSize && j < rightSize) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    
    while (i < leftSize) {
        arr[k++] = left[i++];
    }
    
    while (j < rightSize) {
        arr[k++] = right[j++];
    }
}

// 归并排序
void mergeSort(int arr[], int size) {
    if (size < 2) {
        return;
    }
    
    int mid = size / 2;
    int left[mid];
    int right[size - mid];
    
    for (int i = 0; i < mid; i++) {
        left[i] = arr[i];
    }
    
    for (int i = mid; i < size; i++) {
        right[i - mid] = arr[i];
    }
    
    mergeSort(left, mid);
    mergeSort(right, size - mid);
    merge(arr, left, right, mid, size - mid);
}

int main() {
    int arr[] = {8, 3, 2, 9, 7, 1, 5, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf('原数组：');
    for (int i = 0; i < size; i++) {
        printf('%d ', arr[i]);
    }
    
    mergeSort(arr, size);
    
    printf('
排序后的数组：');
    for (int i = 0; i < size; i++) {
        printf('%d ', arr[i]);
    }
    
    return 0;
}

输出结果

原数组：8 3 2 9 7 1 5 4 
排序后的数组：1 2 3 4 5 7 8 9

可以看到，归并排序算法成功地对输入的数组进行了排序。

代码解释

merge(int arr[], int left[], int right[], int leftSize, int rightSize) 函数用于合并两个已排序的子数组 left 和 right 到 arr 中。
mergeSort(int arr[], int size) 函数是归并排序的递归函数，它将数组 arr 分解成子数组，递归地对子数组进行排序，最后合并子数组。
main() 函数用于测试 mergeSort 函数，并打印排序结果。

总结

归并排序是一种稳定、高效的排序算法。它适用于各种数据类型和规模的排序问题。尽管其时间复杂度为 O(n log n)，但由于其递归的本质，它可能在较大的数据集中占用较多的内存。

希望本教程可以帮助您理解和实现归并排序算法。如果您有任何问题或建议，请随时在评论区留言。