C++程序合并排序

像快排一样， 合并排序 也是一种分治算法。它将输入数组分成两半，对两半进行排序，然后将两个排序好的半部分合并在一起。 merge()函数 用于合并两个部分。merge(arr,l,m,r)是一个关键的过程，假定arr[l..m]和arr[m+1..r]已经排序好，将两个排序好的子数组合并为一个数组。

伪代码:

• 令left变量为0，right变量为n-1
• 用公式找到中位数。mid = (left+right)/2
• 对 (left,mid)进行合并排序
• 对 (mid+1,rear)进行合并排序
• 处理 left < right 时的情况
• 然后调用merge函数进行合并排序。

算法：

步骤1: 开始
步骤2: 声明一个数组和left、right、mid变量
步骤3: 执行合并函数
mergesort(array,left,right)
mergesort (array, left, right)
如果left>right，则返回
mid= (left+right)/2
mergesort(array, left, mid)
mergesort(array, mid+1, right)
merge(array, left, mid, right)
步骤4: 停止

请查看以下C实现的详细信息。

MergeSort(arr[], l, r)

如果 r > l

找到中心点将数组拆成两半:
- 中心点是 m = l + (r – l)/2
对前半部分进行合并排序:
- 调用 mergeSort(arr, l, m)
对后半部分进行合并排序:
- 调用 mergeSort(arr, m + 1, r)
将步骤2和步骤3排序好的两半合并:
- 调用merge(arr, l, m, r)

合并排序的工作原理是什么？

为了了解合并排序的工作原理，我们可以考虑一个数组 arr [] = {38, 27, 43, 3, 9, 82, 10}。

首先，检查数组的左索引是否小于右索引，如果是，那么计算其中间点。

C++程序合并排序

现在，我们已经知道合并排序是将整个数组迭代地分成相等的两半，并且不能达到原子值的情况下。
在这里，我们看到一个由7个项目组成的数组分成两个分别具有4个和3个大小的数组。

C++程序合并排序

现在，再次查找左索引是否小于两个数组的右索引，如果是，则为两个数组再次计算中点。

C++程序合并排序

现在，进一步将这两个数组继续拆分成更小的单位，直到达到数组的原子单位并且无法进行进一步的拆分。

C++程序合并排序

将数组拆分为最小单位后，开始根据元素大小进行合并。
首先，为每个列表比较元素，然后以排序的方式将它们组合成另一个列表。

C++程序合并排序

最终合并后，该列表如下所示：

C++程序合并排序

有关更进一步的清晰度，请参见下面的插图:

下图显示了一个示例数组{38,27,43,3,9,82,10}的完整合并排序过程。

如果我们仔细观察图表，我们可以看到该数组被递归地分成两半，直到大小变为原子单位，然后再根据元素的大小将它们合并在一起。

一旦大小变为1，合并过程开始运行，并开始合并数组，直到完整数组已合并。

C++程序合并排序

//C ++ Merge Sort程序
#include <iostream>
using namespace std;

//合并数组arr[]的两个子数组。
//第一个子数组为arr[begin..mid]，
//第二个子数组为arr[mid + 1..end]
void merge(int array []， const left，
          const mid， const right)
{
    auto const subArrayOne = mid - left +1;
    auto const subArrayTwo = right - mid;

    //创建临时数组
    auto *leftArray = new int[subArrayOne]，
         * rightArray = new int[subArrayTwo];

    //将数据复制到临时数组leftArray[]和rightArray[]中
    for (auto i = 0; i < subArrayOne; i++)
        leftArray[i] = array[left + i];
    for (auto j = 0; j < subArrayTwo; j++)
        rightArray[j] = array[mid + 1 + j];

    //第一个子数组的初始索引
    //第二个子数组的初始索引
    auto indexOfSubArrayOne = 0，
         indexOfSubArrayTwo = 0;

    //合并临时数组回到array[left..right]
    int indexOfMergedArray = left;

    while (indexOfSubArrayOne < subArrayOne &&
           indexOfSubArrayTwo < subArrayTwo)
    {
        if (leftArray[indexOfSubArrayOne] < =
            rightArray[indexOfSubArrayTwo])
        {
            array[indexOfMergedArray] =
            leftArray[indexOfSubArrayOne];
            indexOfSubArrayOne++;
        }
        else
        {
            array[indexOfMergedArray] =
            rightArray[indexOfSubArrayTwo];
            indexOfSubArrayTwo++;
        }
        indexOfMergedArray++;
    }

    //复制left[]的剩余元素（如果有）
    while (indexOfSubArrayOne < subArrayOne)
    {
        array[indexOfMergedArray] =
        leftArray[indexOfSubArrayOne];
        indexOfSubArrayOne++;
        indexOfMergedArray++;
    }

    //复制right[]的剩余元素（如果有）
    while (indexOfSubArrayTwo < subArrayTwo)
    {
        array[indexOfMergedArray] =
        rightArray[indexOfSubArrayTwo];
        indexOfSubArrayTwo++;
        indexOfMergedArray++;
    }
}

//begin是arr sub-array的左索引，end是arr sub-array的右索引，将对其进行排序*/
void mergeSort(int array[]，
               const begin，
               const end)
{
    //递归返回
    if (begin > = end)
        return;

    auto mid = begin + (end-begin) / 2;
    mergeSort（array，begin，mid）;
    mergeSort（array，mid + 1，end）;
    merge（array，begin，mid，end）;
}

//实用程序函数
//打印数组
void printArray(int A [ ]，int size)
{
    for (auto i = 0; i < size; i++)
        cout << A [i] <<“ ”;
    cout << endl;
}

//驱动程序
int main ()
{
    int arr[] = {12，11，13，5，6，7};
    auto arr_size = sizeof(arr) / sizeof(arr[0]);

    cout <<“给定数组是”<< endl;
    printArray（arr，arr_size）;

    mergeSort（arr，0，arr_size-1）;

    cout <<“排序后的数组是”<< endl;
    printArray（arr，arr_size）;
    return 0;
}

输出：

给定数组是
12 11 13 5 6 7
排序后的数组是
5 6 7 11 12 13

时间复杂度： O（n logn），“不同机器上的数组排序”。 Merge Sort是一种递归算法，时间复杂度可以表示为以下递归关系。

T（n）= 2T（n / 2）+θ（n）

上述递归可以使用递归树方法或主方法解决。它属于主方法的情况II，并且递归的解决方案为θ(nLogn)。Merge Sort的时间复杂度在所有3种情况下（最坏，平均和最好）均为θ(nLogn)，因为merge sort总是将数组分成两半，并花费线性时间将两半合并。

辅助空间： O(n)

空间复杂度：

• 在归并排序中，所有元素都被复制到辅助数组中。

• 所以归并排序需要N辅助空间。

算法思想： 分治

归并排序原地排序吗？

在典型实现中不是

归并排序稳定排序吗？

是的，归并排序是稳定的。

归并排序的应用：

合并排序对于在O(nLogn)时间内对链表进行排序非常有用。对于链表的情况，情况因数组和链表的内存分配差异而不同。与数组不同，链表节点在内存中可能不相邻。与数组不同，在链表中，可以在O(1)额外空间和O(1)时间内在中间插入项目。因此，对于链表，归并排序的合并操作可以在不使用额外空间的情况下实现。
在数组中，我们可以进行随机访问，因为元素在内存中是连续的。假设我们有一个整数(4字节)数组A，并且A[0]的地址为x，那么要访问A[i]，我们可以直接访问(x + i*4)的内存。与数组不同，在链表中我们无法进行随机访问。快速排序需要大量此类访问。在链表中访问i’th索引，我们必须从头部到i’th节点遍历每个节点，因为我们没有连续的内存块。因此，quicksort的开销增加了。归并排序顺序访问数据，随机访问的需求较小。
倒置计数问题
用于外部排序