分治算法解决归并排序问题

分治算法定义：分治算法是一种问题解决方法，它将一个大问题划分为多个相同或相似的子问题，然后递归地解决这些子问题，最后将子问题的解合并得到原问题的解

作用：

排序算法分治算法在排序算法中得到广泛应用。例如，归并排序和快速排序都是基于分治思想的经典排序算法。

图算法许多图算法可以使用分治思想进行求解。例如，图的最小生成树问题可以使用分治算法解决。

矩阵操作矩阵乘法、矩阵求逆和矩阵分解等操作中，分治算法可以将矩阵划分为子矩阵，并递归地进行计算。

代码实现

#include <stdio.h>// 合并两个有序数组
void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {int i = 0, j = 0, k = 0;// 将较小的元素逐个放入原数组while (i < leftSize && j < rightSize) {if (left[i] <= right[j]) {arr[k++] = left[i++];} else {arr[k++] = right[j++];}}// 将剩余的元素放入原数组while (i < leftSize) {arr[k++] = left[i++];}while (j < rightSize) {arr[k++] = right[j++];}
}// 归并排序
void mergeSort(int arr[], int size) {if (size <= 1) {return;  // 数组已经有序或为空，无需排序}int mid = size / 2;int left[mid];for (int i = 0; i < mid; i++) {left[i] = arr[i];}int right[size - mid];for (int i = mid; i < size; i++) {right[i - mid] = arr[i];}mergeSort(left, mid);  // 对左半部分进行归并排序mergeSort(right, size - mid);  // 对右半部分进行归并排序merge(arr, left, mid, right, size - mid);  // 合并左右两个有序数组
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {9, 5, 7, 1, 3};int size = sizeof(arr) / sizeof(arr[0]);printf("原始数组：");printArray(arr, size);mergeSort(arr, size);printf("排序后数组：");printArray(arr, size);return 0;
}