用C++写一个归并排序

### 回答1：

我可以给你一个用C语言写的归并排序的实现：#include <stdio.h>

// 合并两个已排序的子数组A[p..q]和A[q+1..r]
void merge(int A[], int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q;

int L[n1], R[n2];

for (int i = 0; i < n1; i++)
L[i] = A[p + i];
for (int j = 0; j < n2; j++)
R[j] = A[q + 1 + j];

int i = 0, j = 0;

int k = p;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
A[k] = L[i];
i++;
}
else
{
A[k] = R[j];
j++;
}
k++;
}

while (i < n1)
{
A[k] = L[i];
i++;
k++;
}

while (j < n2)
{
A[k] = R[j];
j++;
k++;
}
}

// 递归排序数组A[p..r]
void mergeSort(int A[], int p, int r)
{
if (p < r)
{
int q = (p + r) / 2;
mergeSort(A, p, q);
mergeSort(A, q+1, r);
merge(A, p, q, r);
}
}

// 打印排序后的数组
void printArray(int A[], int size)
{
for (int i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

// 测试归并排序
int main()
{
int A[] = {5, 2, 4, 7, 1, 3, 2, 6};
int n = sizeof(A)/sizeof(A[0]);

printf("Given array is \n");
printArray(A, n);

mergeSort(A, 0, n - 1);

printf("\nSorted array is \n");
printArray(A, n);
return 0;
}

### 回答2：
归并排序算法是一种经典的分治算法，它将待排序的数组不断地分割成小的子数组，直到每个子数组中只剩下一个元素，然后再将这些子数组按照顺序进行合并，最终得到一个有序的数组。

以下是用C语言实现归并排序的代码：

#include <stdio.h>

// 合并两个有序数组
void merge(int arr[], int left, int mid, int right) {
    int i = left;  // 左边数组的起始位置
    int j = mid + 1;  // 右边数组的起始位置
    int k = 0;  // 存放合并后的数组的下标
    int temp[right - left + 1];  // 临时数组，用于存放合并后的数组

    // 比较左右两个数组中的元素，较小的放入临时数组中
    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 = 0; i < k; i++)
        arr[left + i] = temp[i];
}

// 归并排序函数
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;  // 计算中间位置

        // 分别对左右两部分进行归并排序
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并两部分有序数组
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {5, 4, 9, 1, 2, 6, 3, 8, 7};
    int length = sizeof(arr) / sizeof(arr[0]);

    printf("排序前的数组：");
    for (int i = 0; i < length; i++)
        printf("%d ", arr[i]);
    printf("\n");

    mergeSort(arr, 0, length - 1);

    printf("排序后的数组：");
    for (int i = 0; i < length; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

通过以上代码可以实现归并排序，该算法的时间复杂度为O(nlogn)，其中n为数组的长度。