【排序算法】归并排序

目录

一.基本思想

二.递归版本

三.非递归版本

四.特性总结

1.时间复杂度：O(N*logN)

2.空间复杂度：O(N)

3.稳定性：稳定

一.基本思想

归并排序是采用分治法的一个非常典型的应用。它将已经有序的序列合并为完全有序的序列，即先使得每一个子序列有序，再让子序列之间有序。归并排序建立在归并操作上，以下动图能很好的演示归并排序中归并的过程：

但上图只展示了归并排序中归并的过程，没有对拆分过程的展示，接下来我将具体介绍归并排序的核心步骤。

已知对于两个已经有序的序列而言，使用p1和p2来比较，p1和p2中较小的一个一定就是当前最小的，放入临时数组tmp中，随后指向的p向后移动，再次进行比较，如此就能将两个有序的序列合并为一个有序序列，这就做到了排序。

然而，如何得到两个已经有序的序列呢？这是类似问题，与排序整个序列的主问题是类似的，很明显，已经可以猜到要使用递归来实现了，那么只需要将两个无序序列进行再次拆分，直到序列中仅剩一个数据，那么此时就可以看作是有序的了，这就是拆分过程。 

拆分结束后，就进行归并，每两个已有序的序列合并到一起，再和其他已合并的序列进行合并，最终合并为一个序列，这就是排序后得到的最终结果，下图展示了整个过程：

 具体应该如何拆分？拆分也是有讲究的，不注意会产生问题。一般都会想到取中分割，取序列左端为begin,右端为end,mid自然等于(begin+end)/2，那么就可以围绕mid拆分为左右两个序列，其中mid应该包含在左端，否则会造成死循环，也就是应该分为[begin,mid]和[mid+1,end]，证明如下：

二.递归版本

//归并排序-主体
void _Merge(int* a, int* tmp, int begin, int end)
{
	//结束条件
	if (begin >= end)
		return;
	//拆分
	int mid = (begin + end) / 2;
	_Merge(a, tmp, begin, mid);
	_Merge(a, tmp, mid + 1, end);
	//归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1