c++实现二路归并排序的示例代码

C++实现二路归并排序是一种常用的排序算法，本文将介绍该算法的详细实现过程，并提供一些示例说明。

一、简述二路归并排序的原理

二路归并排序是一种基于分治思想的排序算法。核心思想是把一个待排序的序列，不断地拆分为两个子序列，直至每个子序列只剩下一个元素，然后利用递归思想将这些子序列不断地两两合并，最终得到一个有序的序列。

二、C++实现二路归并排序的示例代码

代码如下：

#include <iostream>

using namespace std;

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

    int L[n1], R[n2];

    for(int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for(int i = 0; i < n2; i++)
        R[i] = arr[m + 1 + i];

    int i = 0, j = 0, k = l;
    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 l, int r)
{
    if(l < r)
    {
        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

void printArray(int arr[], int size)
{
    for(int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, size);

    mergeSort(arr, 0, size - 1);

    cout << "Sorted array: ";
    printArray(arr, size);

    return 0;
}

三、示例说明

示例一

输入： {38, 27, 43, 3, 9, 82, 10}

输出： {3, 9, 10, 27, 38, 43, 82}

解释：将元素依次分割为： {38, 27, 43, 3}, {9, 82, 10}，继续分割为 {38, 27}, {43, 3}, {9, 82}, {10}，分割完成后，开始将元素进行排序合并。第一次合并为 {27, 38}, {3, 43}, {9, 82}, {10}，第二次合并为 {3, 27, 38, 43}, {9, 10, 82}，最后一次合并为 {3, 9, 10, 27, 38, 43, 82}，得到了一个有序的数组。

示例二

输入： {7, 5, 9, 3, 1, 4, 6, 8, 2}

输出： {1, 2, 3, 4, 5, 6, 7, 8, 9}

解释：将元素依次分割为： {7, 5, 9, 3, 1}, {4, 6, 8, 2}，继续分割为 {7, 5}, {9, 3, 1}, {4, 6}, {8, 2}，分割完成后，开始将元素进行排序合并。第一次合并为 {5, 7}, {1, 3, 9}, {4, 6}, {2, 8}，第二次合并为 {1, 3, 5, 7, 9}, {2, 4, 6, 8}，最后一次合并为 {1, 2, 3, 4, 5, 6, 7, 8, 9}，得到了一个有序的数组。

综上所述，通过归并排序，可以将一个无序的数组转换为一个有序的数组，其时间复杂度为O(nlogn)。