用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 (int m = 0; m < k; m++) {
        arr[left + m] = temp[m];
    }
}

// 归并排序
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[] = {10, 2, 8, 4, 6, 3, 7, 5, 1, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

    MergeSort(arr, 0, n - 1);

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

    return 0;
}

以上是一个简单的归并排序的实现，首先定义了两个函数：`Merge`用于合并两个有序数组，`MergeSort`用于归并排序。其中，`MergeSort`函数采用递归的方式对数组进行分割，直到每个子数组只有一个元素，然后通过调用`Merge`函数将这些子数组进行合并。

在主函数中，我们定义了一个待排序的数组`arr`，然后通过调用`MergeSort`函数进行排序，并打印排序后的结果。

这个代码示例展示了用C语言编写归并排序的基本思路和实现方式。

### 回答3：
归并排序是一种基于分治法的经典排序算法。该算法将待排序的序列不断划分为两个子序列，直到每个子序列只剩下一个元素。然后通过合并操作，将这些子序列逐步合并成有序的序列。

要用C语言编写归并排序，我们可以首先定义一个用于合并操作的函数merge。该函数接受两个已排序的子序列和它们的长度作为参数，返回合并后的有序序列。

void merge(int arr[], int left[], int left_len, int right[], int right_len) {
    int i = 0, j = 0, k = 0;
    while (i < left_len && j < right_len) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < left_len) {
        arr[k++] = left[i++];
    }
    while (j < right_len) {
        arr[k++] = right[j++];
    }
}

接下来，我们可以定义一个归并排序的递归函数merge_sort，该函数将待排序序列进行划分和合并操作。

void merge_sort(int arr[], int len) {
    if (len < 2) {
        return;
    }
    int mid = len / 2;
    int *left = arr;
    int *right = arr + mid;
    int left_len = mid;
    int right_len = len - mid;
    merge_sort(left, left_len);
    merge_sort(right, right_len);
    merge(arr, left, left_len, right, right_len);
}

最后，我们只需要在main函数中调用merge_sort函数，并传入待排序序列和其长度即可。

int main() {
    int arr[] = {9, 5, 3, 7, 2};
    int len = sizeof(arr) / sizeof(arr[0]);

    merge_sort(arr, len);

    for (int i = 0; i < len; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

以上便是用C语言写一个归并排序的完整代码。运行该程序，输出将会是从小到大排好序的序列：2 3 5 7 9。归并排序的时间复杂度为O(nlogn)，是一种高效稳定的排序算法。