C/C++ 分治法实现合并排序算法

合并排序是一种高效的排序算法，其核心思想是分治法。

算法步骤：

1. 分解: 将待排序数组递归地分成两半，直到每个子数组只包含一个元素。
2. 解决: 对每个子数组进行排序（因为只有一个元素，所以已经有序）。
3. 合并: 将排序后的子数组递归地合并成更大的有序数组，直到得到最终排序后的数组。

代码实现 (C语言):

#include 
#include 

void merge(int arr[], int left, int mid, int right) {
  int i = left, j = mid + 1, k = 0;
  int *temp = (int *)malloc((right - left + 1) * sizeof(int));

  while (i <= mid && j <= right) {
    if (arr[i] <= arr[j]) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
    }
  }

  while (i <= mid) {
    temp[k++] = arr[i++];
  }

  while (j <= right) {
    temp[k++] = arr[j++];
  }

  for (i = left, k = 0; i <= right; i++, k++) {
    arr[i] = temp[k];
  }

  free(temp);
}

void mergeSort(int arr[], int left, int right) {
  if (left < right xss=removed xss=removed xss=removed xss=removed>

代码说明:

• merge() 函数用于合并两个有序子数组。
• mergeSort() 函数递归地对数组进行排序。
• 主函数中定义了一个示例数组，并调用 mergeSort() 函数进行排序，最后输出排序结果。

注意:

• 以上代码使用 C 语言编写，如需使用 C++，只需将 printf 改为 cout，并包含 头文件即可。
• 代码中使用了动态内存分配，记得在使用完后释放内存。