C 语言实现归并排序

归并排序简介

归并排序（Merge Sort）是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序的基本思想是将一个序列分成两个子序列，对这两个子序列分别进行排序，然后将排好序的子序列合并成一个最终的有序序列。

归并排序的原理

分解阶段：将待排序的数组不断地进行二分，直到每个子数组只包含一个元素。因为单个元素的数组天然就是有序的。例如，对于数组[5, 2, 9, 1, 5, 6]，首先会将其分成两个子数组[5, 2, 9]和[1, 5, 6]，然后[5, 2, 9]又会被分成[5]和[2, 9]，[2, 9]继续分成[2]和[9]。同理，[1, 5, 6]也会不断二分。
合并阶段：将两个已排序的子数组合并成一个更大的已排序数组。例如，假设有两个已排序的子数组[2]和[9]，合并后得到[2, 9]。然后[5]和[2, 9]合并，因为2 < 5，先将2放入新数组，接着5 < 9，将5放入新数组，最后放入9，得到[2, 5, 9]。同样的方式处理[1, 5, 6]的合并过程，最终将[2, 5, 9]和[1, 5, 6]合并成一个完整的有序数组[1, 2, 5, 5, 6, 9]。

函数声明

// 合并两个子数组
void merge(int arr[], int l, int m, int r);
// 归并排序主函数
void mergeSort(int arr[], int l, int r);

合并函数实现

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    // 创建临时数组
    int L[n1], R[n2];

    // 将数据复制到临时数组 L[] 和 R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // 合并临时数组回到原数组
    i = 0; // 初始化第一个子数组的索引
    j = 0; // 初始化第二个子数组的索引
    k = l; // 初始化合并子数组的索引

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 复制 L[] 中剩余的元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 复制 R[] 中剩余的元素
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

在这个merge函数中，我们首先计算两个子数组的长度n1和n2，然后创建两个临时数组L和R来存储这两个子数组的内容。接着，通过一个while循环比较L和R中的元素，并将较小的元素放入原数组arr中。最后，将L和R中剩余的元素也放入原数组，完成合并操作。

归并排序主函数实现

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // 找到中间位置
        int m = l + (r - l) / 2;

        // 对左半部分进行排序
        mergeSort(arr, l, m);
        // 对右半部分进行排序
        mergeSort(arr, m + 1, r);

        // 合并两个已排序的子数组
        merge(arr, l, m, r);
    }
}

mergeSort函数是归并排序的核心。它首先检查l是否小于r，如果是，则说明数组中不止一个元素，需要进行排序。通过计算中间位置m，将数组分成两部分，然后递归地对这两部分进行排序。最后，调用merge函数将两个已排序的子数组合并成一个有序数组。

完整代码示例

#include <stdio.h>

// 合并两个子数组
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    // 创建临时数组
    int L[n1], R[n2];

    // 将数据复制到临时数组 L[] 和 R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // 合并临时数组回到原数组
    i = 0; // 初始化第一个子数组的索引
    j = 0; // 初始化第二个子数组的索引
    k = l; // 初始化合并子数组的索引

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 复制 L[] 中剩余的元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 复制 R[] 中剩余的元素
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序主函数
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // 找到中间位置
        int m = l + (r - l) / 2;

        // 对左半部分进行排序
        mergeSort(arr, l, m);
        // 对右半部分进行排序
        mergeSort(arr, m + 1, r);

        // 合并两个已排序的子数组
        merge(arr, l, m, r);
    }
}

// 打印数组
void printArray(int A[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("给定的数组是 \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\n排序后的数组是 \n");
    printArray(arr, arr_size);

    return 0;
}

在main函数中，我们定义了一个数组，并调用mergeSort函数对其进行排序，最后通过printArray函数打印出排序前后的数组，以便直观地看到排序效果。

归并排序的时间复杂度和空间复杂度

时间复杂度

分解阶段：归并排序将数组不断二分，每次二分操作的时间复杂度是常数级别的，设为$O(1)$。对于长度为$n$的数组，需要进行$log_2n$次二分才能将其分解为单个元素的子数组。所以分解阶段的总时间复杂度为$O(log_2n)$。
合并阶段：在合并阶段，每次合并操作需要遍历两个子数组，假设两个子数组的长度分别为$n_1$和$n_2$，则合并操作的时间复杂度为$O(n_1 + n_2)$。在整个归并排序过程中，每一层的合并操作所涉及的元素总数都是$n$（因为是将所有元素进行合并），而总共有$log_2n$层。所以合并阶段的总时间复杂度为$O(nlog_2n)$。综合分解和合并阶段，归并排序的时间复杂度为$O(nlog_2n)$，这是一个非常高效的时间复杂度，特别是对于大规模数据的排序。

空间复杂度

归并排序在合并过程中需要使用额外的临时数组来存储子数组的内容。在最坏情况下，即需要合并两个长度为$n/2$的子数组时，需要额外的$O(n)$空间。同时，由于归并排序是递归实现的，递归调用栈也需要占用空间，递归深度为$log_2n$，每一层递归需要的额外空间为$O(1)$，所以递归调用栈占用的空间为$O(log_2n)$。综合起来，归并排序的空间复杂度为$O(n)$，主要是由于合并过程中临时数组的使用。

优化与变体

优化

减少临时数组的分配次数：在上述实现中，每次合并都分配新的临时数组。可以通过预先分配足够大的临时数组，并在合并过程中重复使用来减少内存分配的开销。这样做虽然不会改变空间复杂度，但在实际运行中可以提高效率，特别是在对大量数据进行排序时。
使用插入排序作为子问题的解决方案：当子数组的长度较小时，归并排序的递归调用和合并操作的开销相对较大。此时可以切换到插入排序，因为插入排序在小规模数据上表现良好，其时间复杂度接近$O(n)$。通过这种方式，可以在一定程度上提高归并排序的整体性能。

变体

自底向上的归并排序：上述实现是自顶向下的归并排序，即从整个数组开始不断二分。自底向上的归并排序则是从单个元素的子数组开始，逐步合并成更大的有序数组。这种变体不需要递归调用，避免了递归调用栈的开销，在空间复杂度上略有优势，特别适用于对链表进行排序。
稳定归并排序和不稳定归并排序：上述实现的归并排序是稳定的，即相同元素在排序前后的相对顺序不变。如果在合并过程中不严格保持相同元素的顺序，就可以得到不稳定的归并排序。不稳定的归并排序在某些场景下可以通过简化合并操作来提高效率，但需要根据具体需求来选择是否使用。

应用场景

外部排序：当数据量非常大，无法一次性加载到内存中时，归并排序可以用于外部排序。通过将数据分块读入内存，在内存中进行归并排序，然后将排序后的结果写回磁盘，最后再进行合并操作，从而完成对大规模数据的排序。
链表排序：归并排序对于链表的排序非常有效。由于链表的结构特点，随机访问困难，而归并排序的分治思想和合并操作可以很好地适应链表的顺序访问特性。自底向上的归并排序在链表排序中尤为常用，因为它不需要递归调用，避免了栈溢出的风险。
数据预处理：在一些需要对数据进行预处理的场景中，例如在进行数据分析之前对数据进行排序，归并排序的稳定性和高效性使其成为一个不错的选择。稳定排序可以保证相同数据的相对顺序不变，这在某些数据分析场景中非常重要。

通过以上详细的介绍，你应该对 C 语言实现归并排序有了全面的了解，包括其原理、实现细节、复杂度分析、优化方式以及应用场景。归并排序作为一种经典的排序算法，在计算机科学领域有着广泛的应用，掌握它对于提升编程技能和解决实际问题都具有重要意义。