C++ 实现合并排序算法：详细代码及解析

以下是使用 C++ 编写的合并排序代码：

#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];

    for (i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

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

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

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

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << 'Original array: ' << endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' '; 
    }
    cout << endl;

    mergeSort(arr, 0, n - 1);

    cout << 'Sorted array: ' << endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' '; 
    }
    cout << endl;

    return 0;
}

输出：

Original array:
12 11 13 5 6 7
Sorted array:
5 6 7 11 12 13

在此代码中，merge() 函数将两个已经排序的数组合并为一个排序数组。mergeSort() 函数使用递归将数组分成两个子数组，然后对每个子数组进行排序，最后使用 merge() 函数将两个已经排序的子数组合并为一个排序数组。在主函数中，我们将数组传递给 mergeSort() 函数进行排序，然后输出排序后的数组。

合并排序的步骤：

递归划分: 将数组递归地划分为两个子数组，直到每个子数组只包含一个元素。
合并排序: 对每个子数组进行排序，然后将排序后的子数组合并为一个更大的排序数组。
重复合并: 重复步骤 2，直到所有子数组都被合并成一个排序的完整数组。

合并排序的优点:

稳定的排序算法：相同的元素在排序后保持其相对顺序。
时间复杂度为 O(n log n)，效率较高。
易于实现。

合并排序的缺点:

需要额外的空间来存储临时数组。

代码解析：

merge(int arr[], int left, int mid, int right) 函数：
- 将 arr 数组从 left 到 mid 的元素复制到 L 数组中。
- 将 arr 数组从 mid + 1 到 right 的元素复制到 R 数组中。
- 比较 L 和 R 数组中的元素，将较小的元素复制回 arr 数组中。
- 将剩余的元素复制回 arr 数组中。
mergeSort(int arr[], int left, int right) 函数：
- 递归地调用自身，将数组划分为两个子数组。
- 当子数组只有一个元素时，递归结束。
- 使用 merge() 函数将两个排序后的子数组合并为一个排序数组。
main() 函数：
- 创建一个数组 arr。
- 使用 mergeSort() 函数对数组进行排序。
- 打印排序后的数组。

总结:

合并排序是一种有效的排序算法，它在时间复杂度和稳定性方面表现出色。该算法易于实现，并广泛用于各种应用程序中。