【排序 - 归并排序】

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

归并排序的原理

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

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

   

归并排序的算法步骤

1. 分解：

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

   • 合并：

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

     • 递归结束条件：

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

归并排序的C语言实现

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

#include 
#include 
// 归并函数，用于将两个已排序的数组合并为一个有序数组
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