【排序 - 归并排序】

归并排序（Merge Sort）是一种高效的排序算法，基于分治（Divide and Conquer）策略。它将待排序数组分成两个较小的子数组，分别对它们进行排序，然后将排好序的子数组合并成一个整体有序的数组。归并排序的时间复杂度为O(n log n)，在大多数情况下是最佳选择之一。

归并排序的原理

归并排序的过程可以分为两个主要步骤：分解和合并。

1. 分解：将原始数组递归地分解为较小的子数组，直到每个子数组只有一个元素。
2. 合并：将两个已排序的子数组合并成一个有序的数组，不断重复这个过程直到整个数组排序完成。
   

归并排序的算法步骤

1. 分解：

   • 将待排序数组分为两个大致相等的子数组。
   • 递归地对每个子数组进行归并排序，直到子数组长度为1。

2. 合并：

   • 合并两个已排序的子数组为一个新的有序数组。
   • 将两个子数组的元素逐个比较，依次放入新数组中，直到将两个子数组全部合并。

3. 递归结束条件：

   • 当子数组长度为1时，递归结束。

归并排序的C语言实现

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

#include <stdio.h>
#include <stdlib.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];

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

    // 归并临时数组到 arr[left..right]
    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++;
    }

    // 复制 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 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 arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[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");
    printArray(arr, arr_size);
    return 0;
}

总结

归并排序是一种效率高且稳定的排序算法，适用于大规模数据集的排序需求。通过递归地分解和合并数组，归并排序可以在O(n log n)的时间复杂度内完成排序，因此在实际应用中被广泛使用。通过本文的介绍和C语言实现示例，读者可以更深入地理解归并排序的工作原理和实现方式。