C语言归并排序（附带源码和解析）

归并排序是一种高效的排序算法，它采用分治法的思想，将一个大问题分解成若干个小问题来解决。这种算法的核心思想是将两个已排序的子数组合并成一个更大的有序数组。归并排序的时间复杂度为 O(n log n)，这使得它在处理大型数据集时表现出色。

归并排序的基本原理

归并排序的工作原理可以分为以下几个步骤：

1. 将待排序的数组分成两个大小相等（或近似相等）的子数组。
2. 递归地对这两个子数组进行排序。
3. 将两个已排序的子数组合并成一个有序数组。

这个过程会不断重复，直到子数组的大小为 1 或 0，此时认为子数组已经有序。然后，算法会逐步向上合并这些小的有序数组，最终得到一个完全有序的数组。

归并过程的详细说明

让我们通过一个具体的例子来理解归并排序的过程。假设我们有一个包含 8 个元素的数组：

[38, 27, 43, 3, 9, 82, 10, 15]

归并排序会首先将这个数组分成两半：

[38, 27, 43, 3] [9, 82, 10, 15]

然后，递归地分割这些子数组，直到每个子数组只包含一个元素：

[38] [27] [43] [3] [9] [82] [10] [15]

现在，算法开始合并这些单元素数组。在合并过程中，它会比较相邻的元素并按正确的顺序放置它们：

[27, 38] [3, 43] [9, 82] [10, 15]

接下来，这些有序的双元素数组会被合并成有序的四元素数组：

[3, 27, 38, 43] [9, 10, 15, 82]

最后，这两个有序的四元素数组会被合并成一个完全有序的八元素数组：

[3, 9, 10, 15, 27, 38, 43, 82]

C语言实现归并排序

下面是归并排序的 C 语言实现：

#include <stdio.h>

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);
    }
}

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

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10, 15};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组：\n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("排序后的数组：\n");
    printArray(arr, arr_size);
    return 0;
}

运行结果：

原始数组：
38 27 43 3 9 82 10 15
排序后的数组：
3 9 10 15 27 38 43 82

这段代码包含三个主要函数：

• merge 函数：负责合并两个已排序的子数组。
• mergeSort 函数：递归地对数组进行分割和排序。
• printArray 函数：用于打印数组内容。

merge 函数是归并排序的核心。它接收一个数组和三个索引：左边界、中点和右边界。函数首先创建两个临时数组来存储左右两个子数组的元素。然后，它比较这两个子数组的元素，并按正确的顺序将它们放回原数组中。

mergeSort 函数使用递归来实现分治策略。它不断地将数组分成两半，直到子数组的大小为 1。然后，它调用 merge 函数来合并这些已排序的子数组。

归并排序的优缺点

归并排序有以下优点：

• 稳定性：归并排序是一种稳定的排序算法，这意味着相等元素的相对顺序在排序后不会改变。
• 效率：对于大型数据集，归并排序的性能非常好，时间复杂度始终保持在 O(n log n)。
• 适用于外部排序：当数据量非常大，无法全部装入内存时，归并排序仍然可以有效地工作。

然而，归并排序也有一些缺点：

• 空间复杂度：归并排序需要额外的 O(n) 空间来存储临时数组，这可能在处理非常大的数据集时成为一个问题。
• 对于小型数组，归并排序可能不如插入排序等简单算法高效。

归并排序是一种强大而高效的排序算法，特别适合处理大型数据集，它的稳定性和可预测的时间复杂度使其成为许多应用程序的首选排序算法。虽然它在空间复杂度方面有一些限制，但在需要稳定排序或处理外部数据时，归并排序仍然是一个极好的选择。

你可能还想关注其它 9 种排序算法：

1. C语言冒泡排序（附带源码和解析）
2. C语言快速排序（附带源码和解析）
3. C语言选择排序（附带源码和解析）
4. C语言插入排序（附带源码和解析）
5. C语言希尔排序（附带源码和解析）
6. C语言堆排序（附带源码和解析）
7. C语言计数排序（附带源码和解析）
8. C语言桶排序（附带源码和解析）
9. C语言基数排序（附带源码和解析）

声明：《算法系列教程》为本站“54笨鸟”官方原创，由国家机构和地方版权局所签发的权威证书所保护。