【数据结构与算法】(15)：归并排序的递归和非递归方式

🤡博客主页：Code_文晓

🥰本文专栏：数据结构与算法

😻欢迎关注：感谢大家的点赞评论+关注，祝您学有所成！

✨✨💜💛想要学习更多数据结构与算法点击专栏链接查看💛💜✨✨

归并排序，英文名称是Merging Sort。归并排序里的“归并”，也叫合并，其实就是把两个或者多个已经有序的序列合并成一个。简而言之，归并排序采用的是一种分而治之的思想，将待排序的序列不断二分，直到每个子序列只有一个元素，然后将相邻的子序列两两归并，最终得到一个有序的序列。

下面，我们就一起看一看归并排序都涉及到哪些基本概念。

1. 概念和实例

图1是两个有序序列（数组），现在我们希望利用归并排序把这两个数组合并成一个元素按从小到大排序的数组。

既然要合并，那么首先必然要分配一个足以容纳两个有序数组中所有元素的内存空间，也就是一个新数组，然后进行下面的操作。

针对每个数组都设置一个指向当前位置的指针（pi、pj、pk），初始状态时，这三根指针都指向数组的起始位置，如图2中的子图1。
每一次都会对比pi和pj位置所指向的元素值到底哪个更小，把更小的元素放入到pk所指向的位置处。因为1<2，所以把1放入到pk指针所指向的位置处，同时，把pk指针后移一个位置。当然，因为元素1已经被放入到了新数组中，自然pi指针也要后移一个位置，结果如图2中的子图2。
重复上面第二个步骤，有那么一个时刻，有序序列1中的pi指针已经指向了最后一个元素后面的位置，这意味着有序序列1中的所有元素都被放入到了新数组中，只剩下有序序列2中还有没排好序的元素了，如图2中的子图3所示。
此时，就不再需要元素大小的对比，直接把有序序列2中剩余的2个元素放入到新数组中，最终归并排序结果如图2中的子图4。

图2其实是一个“2路”归并排序。因为图中是把两个有序序列合并成一个有序序列。在2路归并排序中，每次需要从两个元素中选出一个更小的元素，这只需要对比pi和pj所指向的元素就可以了。或者你可以理解为，只需要对比一次关键词。

既然有2路归并排序，那么自然可以有多路归并排序，比如3路归并排序、4路归并排序等等。这里注意，多路归并排序一般用于外部排序。图3展示的就是4路归并排序的初始状态。

针对图3，如果进行4路归并排序（对4个有序序列进行归并排序），那么每选出一个最小元素放入新数组中需要进行3次关键字比较——比如第1次需要比较元素1和2看谁比较小，选择出较小的元素继续与元素42相比看谁比较小，再选出较小的元素与元素28相比。推而广之，对于m路归并排序，每选出一个元素需要进行m-1次关键字的对比。内部排序中通常使用的是2路归并排序。

那么，回头就要说一说如何对一个具有n个记录的初始序列进行排序了。

首先，把这个初始序列看成是n个有序的子序列（n路），每个子序列的长度为1。
其次，两两合并（“2路”归并排序），得到 $\left \lceil \frac{n}{2} \right \rceil$ 个长度为2或1的有序子序列，然后再两两合并……直至得到一个长度为n的有序序列为止。

如图4所示，将16、1、45、23、99、2、18共7个数字进行归并排序：

第一趟归并排序，将相邻部分两两归并，即16和1归并，45和23归并，99和2归并，18由于只剩下自己了所以不做归并操作。经过这趟归并，得到了4个有序的子序列。
第二趟归并排序，对第一趟归并排序的结果再次进行两两归并，即[1,16]和[23,45]归并，[2,99]和[18]归并。经过这趟归并，得到了两个有序的子序列。
第三趟归并排序，对第二趟归并排序的结果再进行两两归并，最终得到了一个排好序的序列。

2. 递归实现代码

void _MergeSort(int* myarray, int begin, int end, int* tmp)
{
	if (begin == end)  // 如果起始位置和结束位置相同，表示只有一个元素，已经有序，直接返回
	{
		return;
	}

	int mid = (begin + end) / 2;  // 计算中间位置

	_MergeSort(myarray, begin, mid, tmp);  // 对左半部分进行递归排序
	_MergeSort(myarray, mid + 1, end, tmp);  // 对右半部分进行递归排序

	int begin1 = begin, end1 = mid;  // 第一组的起始索引和结束索引
	int begin2 = mid + 1, end2 = end;  // 第二组的起始索引和结束索引
	int i = begin;  // 临时数组的索引

	while (begin1 <= end1 && begin2 <= end2)  // 当两组都还有元素时进行比较
	{
		if (myarray[begin1] <= myarray[begin2])  // 如果第一组的元素小于等于第二组的元素
		{
			tmp[i++] = myarray[begin1++];  // 将第一组的元素放入临时数组中，并增加相应的索引
		}
		else
		{
			tmp[i++] = myarray[begin2++];  // 将第二组的元素放入临时数组中，并增加相应的索引
		}
	}

	while (begin1 <= end1)  // 如果第一组还有剩余元素，则将剩余元素依次放入临时数组中
	{
		tmp[i++] = myarray[begin1++];
	}

	while (begin2 <= end2)  // 如果第二组还有剩余元素，则将剩余元素依次放入临时数组中
	{
		tmp[i++] = myarray[begin2++];
	}

	/*
	为什么要使用 myarray+begin 和 tmp+begin 作为参数呢？
	这是因为在归并排序的过程中，我们只对数组的一个区间进行排序，而不是整个数组。
	起始位置 begin 表示排序区间的起始位置，所以我们需要将起始位置对应的内存块复制回原数组的相应位置。
	*/
	memcpy(myarray + begin, tmp + begin, sizeof(int) * (end - begin + 1));  // 将临时数组中归并后的结果拷贝回原数组中，从起始位置开始

}

void MergeSort(int* myarray, int length)
{
	int* tmp = (int*)malloc(sizeof(int) * length);  // 创建临时数组用于存储归并结果
	_MergeSort(myarray, 0, length - 1, tmp);  // 进行递归排序
	free(tmp);  // 释放临时数组的内存空间
}

3. 归并排序复杂度分析

图4所示的2路归并排序过程看起来是一棵倒着的二叉树，因此又被称为“归并树”。如果要对n个元素进行排序，把二叉树的高度看成是h，则归并排序的趟数是h-1趟。而二叉树的第h层最多有 $2^{h}-1$ 个节点。因为所有待排序列的节点都会出现在第h层，所以这也是待排序列的节点总数，即 $h-1=\left \lceil log^{n}_{2} \right \rceil$ 。也就是说，n个元素进行2路归并排序的趟数是 $\left \lceil log^{n}_{2} \right \rceil$ 。每一趟归并操作的时间复杂度是多少呢？观察一下图2、图4，不难发现是需要将所有n个元素都扫描一次并进行相应对比，所以每一趟归并操作的时间复杂度是 $O(n)$ ，最后得出结论——归并排序算法的时间复杂度是 $O(nlog^{n}_{2})$ 。

此外，从上述代码可以看到，归并排序需要额外的辅助空间，辅助空间的大小和原来保存数据的数组大小相同，所以这部分的空间复杂度是O(n)。算法中还用到了递归调用，但递归调用的深度不会超过 $log^{n}_{2}$ 。所以归并排序算法的空间复杂度是 $O(n+log^{n}_{2})$ = $O(max(n,log_{2}^{n}))$ = $O(n)$ 。

归并排序算法的稳定性受编写代码的影响，上述的代码实现方式得到的归并排序算法是稳定的。

4. 非递归实现代码

在归并排序的非递归版本中，我们使用了一个临时数组来存储归并的结果。初始时，我们将步长设置为1，然后进行多轮的迭代，每轮迭代都将步长翻倍。在每轮迭代中，我们以两倍步长的间隔遍历数组，将数组分为多个小组，每个小组的长度为步长。对于每个小组，我们会比较并归并相邻的两个子序列。

具体而言，我们使用四个指针来标记两个子序列的起始和结束位置。在每次归并操作中，我们将两个子序列的元素进行比较，并按照从小到大的顺序依次放入临时数组中。如果其中一个子序列的元素已经全部放入临时数组中，而另一个子序列还有剩余元素，则直接将剩余元素放入临时数组中。最后，我们将临时数组中的归并结果拷贝回原始数组的相应位置。

随着迭代的进行，步长逐渐增加，小组的长度逐渐变大，直到整个数组被归并排序为止。最后，我们释放临时数组的内存空间。

// 归并排序非递归版
void MergeSortNonR(int* myarray, int length)
{
    int* tmp = (int*)malloc(sizeof(int) * length);  // 创建临时数组用于存储归并结果
 
    int gap = 1;  // 初始步长为1
    while (gap < length)  // 当步长小于数组长度时
    {
        int j = 0;  // 临时数组索引
        for (int i = 0; i < length; i += 2 * gap)  // 每次以两倍步长遍历数组
        {
            int begin1 = i, end1 = i + gap - 1;  // 第一组的起始索引和结束索引
            int begin2 = i + gap, end2 = i + 2 * gap - 1;  // 第二组的起始索引和结束索引
 
            if (end1 >= length || begin2 >= length)  // 如果某一组的索引超出数组范围，则跳出循环
            {
                break;
            }
 
            if (end2 >= length)  // 如果第二组的结束索引超出数组范围，则修正为数组最后一个元素的索引
            {
                end2 = length - 1;
            }
 
            while (begin1 <= end1 && begin2 <= end2)  // 当两组都还有元素时进行比较
            {
                if (myarray[begin1] < myarray[begin2])  // 如果第一组的元素小于第二组的元素
                {
                    tmp[j++] = myarray[begin1++];  // 将第一组的元素放入临时数组中，并增加相应的索引
                }
                else
                {
                    tmp[j++] = myarray[begin2++];  // 将第二组的元素放入临时数组中，并增加相应的索引
                }
            }
 
            while (begin1 <= end1)  // 如果第一组还有剩余元素，则将剩余元素依次放入临时数组中
            {
                tmp[j++] = myarray[begin1++];
            }
 
            while (begin2 <= end2)  // 如果第二组还有剩余元素，则将剩余元素依次放入临时数组中
            {
                tmp[j++] = myarray[begin2++];
            }
 
            memcpy(myarray + i, tmp + i, sizeof(int) * (end2 - i + 1));  // 将临时数组中归并后的结果拷贝回原数组中
        }
    
        gap *= 2;  // 增加步长为原来的两倍
    }
 
    free(tmp);  // 释放临时数组的内存空间
}

归并排序的特性总结：