C++中归并排序算法详细讲解及数据模拟

归并排序是一种基于分治策略的排序算法，它将待排序的序列分成两个子序列，对每个子序列进行递归排序，然后将两个有序的子序列合并成一个有序的序列。归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。

下面是C++中归并排序算法的详细讲解及数据模拟：

1. 归并排序算法的实现

归并排序的主要过程可以分为两个步骤：分割和合并。分割是将待排序的序列分成两个子序列，递归地对每个子序列进行排序；合并是将两个有序的子序列合并成一个有序的序列。

1. 数据模拟

接下来我们用一组示例数据来模拟归并排序的过程。

假设待排序的序列为{49, 38, 65, 97, 76, 13, 27, 49}。

第一次分割后，得到两个子序列：{49, 38, 65, 97}和{76, 13, 27, 49}。

对左子序列继续分割，得到两个子序列：{49, 38}和{65, 97}。对右子序列继续分割，得到两个子序列：{76, 13}和{27, 49}。

然后对每个子序列进行排序，左子序列排序后变为{38, 49, 65, 97}，右子序列排序后变为{13, 27, 49, 76}。

最后将两个有序的子序列合并，得到完整的有序序列{13, 27, 38, 49, 49, 65, 76, 97}。

以下是完整的C++代码和输出结果：

#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    // 合并两个有序子序列，左边子序列是arr[left...mid]，右边子序列是arr[mid+1...right]

    // 计算左右子序列的长度
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建左右子序列的数组
    int L[n1], R[n2];

    // 将左边子序列复制到L数组中
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];

    // 将右边子序列复制到R数组中
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // 将L和R数组中的元素按照顺序合并到arr数组中
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 如果L数组中还有剩余元素，将其全部复制到arr数组中
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 如果R数组中还有剩余元素，将其全部复制到arr数组中
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void merge_sort(int arr[], int left, int right) {
    // 对arr[left...right]进行归并排序

    if (left < right) {
        // 计算中间位置
        int mid = left + (right - left) / 2;

        // 对左半部分进行归并排序
        merge_sort(arr, left, mid);

        // 对右半部分进行归并排序
        merge_sort(arr, mid + 1, right);

        // 合并左右两部分
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 对整个序列进行归并排序
    merge_sort(arr, 0, n - 1);

    // 输出排序后的序列
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}