C++实现自顶向下的归并排序算法

下面是“C++实现自顶向下的归并排序算法”的完整攻略。

归并排序的概念

归并排序是一种分治法排序算法，它将一个大数组分成两个部分，分别对这两个部分进行排序，最后将两个排好序的部分合并起来。归并排序的时间复杂度为O(n log n)。

归并排序的步骤

实现归并排序需要以下三个步骤：

1. 分割 - 将数组分成两个部分，分别对每个部分进行排序。该过程使用二分法来实现。递归调用直到只有一个元素或一个空数组。

2. 合并 - 将两个排好序的部分合并起来。该过程使用两个指针遍历两个数组，并将它们按从小到大的顺序合并。

3. 排序 - 将数组划分为两个部分，分别对每个部分进行排序并合并。递归调用直到只有一个元素或一个空数组。

C++实现自顶向下的归并排序算法

以下是C++实现自顶向下的归并排序算法的完整代码：

#include <iostream>
using namespace std;

void merge(int arr[], int l, int mid, int r) {
    int n1 = mid - l + 1;
    int n2 = r - mid;

    int arr1[n1], arr2[n2];

    for(int i = 0; i < n1; i++)
        arr1[i] = arr[l + i];

    for(int i = 0; i < n2; i++)
        arr2[i] = arr[mid + 1 + i];

    int i = 0, j = 0, k = l;
    while(i < n1 && j < n2) {
        if(arr1[i] <= arr2[j]) {
            arr[k] = arr1[i];
            i++;
        }
        else {
            arr[k] = arr2[j];
            j++;
        }
        k++;
    }

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

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

void merge_sort(int arr[], int l, int r) {
    if(l >= r)
        return;

    int mid = l + (r - l) / 2;
    merge_sort(arr, l, mid);
    merge_sort(arr, mid + 1, r);
    merge(arr, l, mid, r);
}

int main() {
    int arr[] = {5, 4, 3, 2, 1};
    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;
}

在上面的代码中，merge()函数用于将两个已排好序的数组合并到一起。merge_sort()函数实现了整个排序过程，将数组分成两个部分，分别对每个部分进行排序并合并。

示例说明

下面是两个示例来说明归并排序的过程。

1. 对数组{5, 4, 3, 2, 1}进行排序。

2. 输入：{5, 4, 3, 2, 1}

3. 第一次分割：{5, 4, 3} {2, 1}
4. 第二次分割：{5} {4, 3} {2} {1}
5. 第三次分割：{5} {4} {3} {2} {1}
6. 合并：{4, 5} {2, 3} {1}
7. 合并：{2, 3, 4, 5} {1}
8. 合并：{1, 2, 3, 4, 5}

9. 输出：{1, 2, 3, 4, 5}

10. 对数组{45, 23, 11, 89, 77, 98, 4, 28}进行排序。

11. 输入：{45, 23, 11, 89, 77, 98, 4, 28}

12. 第一次分割：{45, 23, 11, 89} {77, 98, 4, 28}
13. 第二次分割：{45, 23} {11, 89} {77, 98} {4, 28}
14. 第三次分割：{45} {23} {11} {89} {77} {98} {4} {28}
15. 合并：{23, 45} {11, 89} {77, 98} {4, 28}
16. 合并：{11, 23, 45, 89} {4, 28, 77, 98}
17. 合并：{4, 11, 23, 28, 45, 77, 89, 98}
18. 输出：{4, 11, 23, 28, 45, 77, 89, 98}

以上就是C++实现自顶向下的归并排序算法的完整攻略和两个示例说明。