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

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

作用：

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

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

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

代码实现

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