C++ Mergesort数组代码怎么写？

### 回答1：

归并排序（Merge Sort）是一种分治算法，它将一个数组（array）拆分成两个子数组，然后递归地把子数组拆分成更小的子数组，直到每个子数组只包含一个元素，接着将子数组归并成原来的大小，最后得到排序后的数组。算法的代码如下：def mergesort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:] mergesort(left)
mergesort(right) i = j = k = 0 while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1 while i < len(left):
arr[k] = left[i]
i += 1
k += 1 while j < len(right):
arr[k] = right[j]
j += 1
k += 1arr = [5,1,4,2,8]
mergesort(arr)
print(arr)

### 回答2：
Mergesort（归并排序）是一种经典的排序算法，它采用分治的思想将一个数组分成两半，分别递归地排序，然后再将已排序的两个子数组进行合并。下面是一种用Python编写的Mergesort数组代码示例：

def merge(arr, left, middle, right):
    # 创建临时数组用来存放合并后的结果
    temp = [0] * (right - left + 1)
    i = left  # 左子数组索引
    j = middle + 1  # 右子数组索引
    k = 0  # 临时数组索引

    # 将左右子数组的元素按照升序合并到临时数组中
    while i <= middle and j <= right:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]
            i += 1
        else:
            temp[k] = arr[j]
            j += 1
        k += 1

    # 将剩余的元素依次复制到临时数组中
    while i <= middle:
        temp[k] = arr[i]
        i += 1
        k += 1
    while j <= right:
        temp[k] = arr[j]
        j += 1
        k += 1

    # 将临时数组的元素复制回原数组对应的位置
    for i in range(len(temp)):
        arr[left + i] = temp[i]


def mergeSort(arr, left, right):
    if left < right:
        middle = (left + right) // 2
        # 递归地对左右子数组进行排序
        mergeSort(arr, left, middle)
        mergeSort(arr, middle + 1, right)
        # 合并两个已排序的子数组
        merge(arr, left, middle, right)


# 测试代码
arr = [9, 5, 7, 2, 8]
mergeSort(arr, 0, len(arr) - 1)
print(arr)  # 输出：[2, 5, 7, 8, 9]

以上代码通过递归的方式实现了归并排序算法。merge函数用于合并两个已排序的子数组，mergeSort函数用于递归地对数组进行排序。通过不断地将数组拆分成更小的子数组，并合并已排序的子数组，最终得到了一个排好序的数组。

### 回答3：
Mergesort是一种经典的排序算法，可以对数组进行排序。下面是用C语言编写Mergesort的数组代码。

#include <stdio.h>

// 合并两个已经排序的数组
void merge(int arr[], int start, int mid, int end) {
    int n1 = mid - start + 1;
    int n2 = end - mid;
    int left[n1], right[n2];
    
    // 将元素复制到临时数组
    for (int i = 0; i < n1; i++) {
        left[i] = arr[start + i];
    }
    for (int j = 0; j < n2; j++) {
        right[j] = arr[mid + 1 + j];
    }
    
    // 合并两个临时数组到原数组
    int i = 0, j = 0, k = start;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    
    // 处理剩余的元素
    while (i < n1) {
        arr[k] = left[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = right[j];
        j++;
        k++;
    }
}

// 归并排序函数
void mergeSort(int arr[], int start, int end) {
    if (start < end) {
        int mid = start + (end - start) / 2;
        
        // 递归地对左右两个子数组进行排序
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        
        // 合并两个子数组
        merge(arr, start, mid, end);
    }
}

int main() {
    int arr[] = { 5, 2, 8, 9, 1, 3 };
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    
    mergeSort(arr, 0, size - 1);
    
    printf("\n排序后的数组：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

以上代码实现了Mergesort算法。首先，通过调用`mergeSort`函数对整个数组进行排序，该函数接受数组、起始索引和结束索引作为参数。在递归的过程中，每次将数组分割成两个子数组，然后对这两个子数组进行递归排序。最后，通过调用`merge`函数将两个排序好的子数组合并成一个有序的数组。在`merge`函数内部，首先创建左右两个临时数组，然后将元素复制到临时数组中，最后合并两个临时数组到原数组中。在`main`函数中，展示了对原始数组进行排序的过程。