归并排序及其三道加强习题

归并排序(Merge Sort) 是利用归并的思想实现的排序方法，该算法采用经典的 分治(divide-and-conquer) 策略将问题分成一些小的问题然后递归求解，即分而治之。

递归实现

图解：

先递归将数组一分为二，直到不可再分；然后=依次将两边 合并(merge) ，合并的图解如下（以最后一次合并为例）：

注意，之所以能这样合并，是因为两边的子数组都是已经排好序了的！而子数组最终也是通过该方法从单个元素排序而来 。从图可知，我们需要 new 一个辅助数组来存放左右两边比较后的结果；注意，当 i 移到 7 位置时，7>6，将 6 放入辅助数组，然后 j++，于是 j 超出数组范围，此时就直接将左半边余下的 7、8 放入辅助数组 ，结束。

template<class T, class cmptor>
void merge(T* vec, int l, int m, int r, cmptor cmp)
{
	T* help = new int[r - l + 1];
	int p = 0;             //help[]的pointer
	int lp = l;            //left pointer
	int rp = m + 1;        //right pointer
	while (lp <= m && rp <= r)
		help[p++] = vec[lp] < vec[rp] ? vec[lp++] : vec[rp++];
	while (lp <= m)
		help[p++] = vec[lp++];
	while (rp <= r)           //第10行和第12行的while只可能进入一个
		help[p++] = vec[rp++];
	for (int i = 0; i < r - l + 1; i++)
		vec[l + i] = help[i];
	delete[] help;
}

template<class T, class cmptor>
void process(T* vec, int l, int r, cmptor cmp)
{
		
	if (l >= r)//base case
		return;
	int m = (l+r)/2;
	process(vec, l, m, cmp);
	process(vec, m + 1, r, cmp);
	merge(vec, l, m, r, cmp);
}
template<class T, class cmptor>
void mergeSort(T* vec, int size, cmptor cmp)
{
	if (size == 1)
		return;
	int r = size - 1;
	process(vec, 0, r, cmp);
}

根据代码作如下分析：

归并排序的边界条件很巧妙：[L，M]，[M+1，R] ，分到最后只剩一个元素时，就会有 L>=M，从而结束递归，比如所在区间：[0, 1]，L=0，R=1，M=(0+1)/2=0，左边进入递归 [0, 0]，右边进入递归 [1, 1]，自然就会满足基线条件(base case)，从而 return。对其他区间也同样如此。未来考虑某些边界条件时，这是一个很好的参考
注意 base case 是 l>=r 而非 l==r，左边界在某些情况下可能超过右边界，血的教训…
为什么 $O(N^2)$ 这么 low ？因为它大量浪费了比较行为，前一次比较丝毫不能为以后的比较做出贡献。归并排序为什么好？因为它将每一次的比较结果都往后进行了传递，使后续的递归能够利用之前的比较成果
归并排序的复杂度为什么是 $O(NlogN)$ ：因为最坏情况下，每一个数(即 N 个数)都会被比较 logN 次（递归层数）

迭代实现

归并排序的迭代实现也有较复杂的边界条件，笔者会用代码和示意图对应着解释这些边界。先上图：

void merge(int* arr, int l, int m, int r)
{
	int* help = new int[r - l + 1];
	int p = 0;
	int lp = l;
	int rp = m + 1;
	while (lp <= m && rp <= r)
		help[p++] = arr[lp] < arr[rp] ? arr[lp++] : arr[rp++];
	while (lp <= m)
		help[p++] = arr[lp++];
	while (rp <= r)         //第9行和第10行的while只会进入其中一个
		help[p++] = arr[rp++];
	for (int i = 0; i < r - l + 1; i++)
		arr[l + i] = help[i];
	delete[] help;
}

void mergeSort(int* arr, int N)
{
	if (arr == nullptr || N == 1)
		return;
	int mergeSize = 1, L, M, R;
	while (mergeSize < N)
	{
		L = 0; //极易忽略
		while (L < N)
		{
			M = L + mergeSize - 1;
			if (M >= N-1) //极易忽略
				break;
			R = (M + mergeSize) < (N - 1) ? M + mergeSize : N - 1;
			merge(arr, L, M, R);
			L = R + 1;
		}
		if (mergeSize > N / 2)//防止整形溢出
			break;
		mergeSize *= 2;
	}
}

int main()
{
	int arr[] = { 1,23,24,51,3,56,27,17,10,43,25,36,86 };
	mergeSort(arr, sizeof(arr) / sizeof(int));
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		cout << arr[i] << "  ";
	}
}

迭代实现的 merge() 与递归实现的 merge() 相同
第 25 行极易忽略！
第 28 到 31 行代码的顺序很容易记错，其位置不可颠倒！！！
重点要讨论的边界处理，即第 23、26、29 行代码，其理由已经在图中详细阐述。
第 35 行代码十分容易忽略。当 N 靠近整形边界时，mergeSize×2 就可能发生溢出成为负数，然后回到第 23 行进行比较，又重新进入 while 循环！所以未来在这种作了增加运算后还要和其他数进行比较时，须特别注意这类情况！

归并排序变式：三道面试题

小和问题

问题阐述
在一个给定的数组中，计算出每一个数左边的所有比其小的数的和，并将这些和相加，即得这个数组的小和。距离：对于数组 [6,3,8,9] ，6 的左边没有比 6 小的数；3 的左边没有比 3 小的数；8 的左边，6 和 3 小于 8，其和为 6+3=9；9 的左边，6，3，8 小于 9，其和为 17；故数组的小和为 26。

分析
显然，本问题可以很容易地被暴力破解，对每一个数，遍历之前的所有数，算法复杂度为 $O(N^2)$ 。在暴力破解的基础上，我们会很容易地想到一些优化的方法，比如，当前数字为 7 时，往前挨个比较，当碰上数字 6 时，我们就可以停止遍历，直接将 6 和 6 的小和相加即可，如下图：

可见，当数字 N 左边紧挨着 N-1 时，此方式的效率就能达到最高；但如果碰上 [7,6,5,4,3,2,1] 这样从大到小的数列，复杂度也会回归到 $O(N^2)$ 。那么，如何进一步优化？从以上过程可以隐约感受到，如果在求小和的过程中能够将之前比较过的数字由小到大进行排序，也许就可以充分利用上述优化方式。进一步，我们尝试引入归并排序（别问为什么，问就是不知道，呜呜呜）。仍然拿前文例子进行说明：

取出中间状态，分析步骤：

当有小和时，sum += 左边指向的数 × (右指针及其右边的数字个数) ，也即：sum += arr[lp] * (R - rp + 1) ；这是因为左右两组已经排好序的数组，例如 [2, 3, 4] 与 [3, 5, 9] merge 时，3 > 2 就能直接推出 3 后面的数都 > 2，因此直接 2 *(r-p2+1) 即可。 这是排序的最终用处。
此算法关键问题在于，为什么排序没有影响这些数字的小和？ 这是因为，在归并(merge)前，左组中的每一个数仍然在右组中每一个数的左边，这种状态并没有因为之前的排序而改变，直到本次merge才结束这种状态 。
此算法的代码实现，仅仅只改变了 merge() 函数（下面代码的第17-20行）

另外需要注意，当左边指针指向的数等于右边指针指向的数时，必须先将右边的数放入辅助数组！ 拿如下情况举例讲解：

小和问题分析大致如此。代码如下：

#include<iostream>
#include<cstdlib>//rand()
#include<ctime>//time()
#include<cstring>//memcpy()

int count_1 = 0;

void merge(int* arr, int l, int m, int r)
{
	int* help = new int[r - l + 1];
	int p = 0;             //help[]的pointer
	int lp = l;            //left pointer
	int rp = m + 1;        //right pointer
	while (lp <= m && rp <= r)
	{
		if (arr[lp] < arr[rp])
		{
			count_1 += (r - rp + 1) * arr[lp];//
		}
		help[p++] = arr[lp] < arr[rp] ? arr[lp++] : arr[rp++];
	}
		
	while (lp <= m)
		help[p++] = arr[lp++];
	while (rp <= r)           //第9行和第11行的while只可能进入一个
		help[p++] = arr[rp++];
	for (int i = 0; i < r - l + 1; i++)
		arr[l + i] = help[i];
	delete[] help;
}

void process(int* arr, int l, int r)
{
	if (l == r)//base case
		return;
	int m = l + ((r - l) >> 1);
	process(arr, l, m);
	process(arr, m + 1, r);
	merge(arr, l, m, r);
}

void mergeSort(int* arr, int size)
{
	if (size == 1)
		return;
	int r = size - 1;
	process(arr, 0, r);
}

逆序对问题

问题阐述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
输入: [7,5,6,4]
输出: 5
逆序对：<7,5>,<7,6>,<7,4>,<5,4>,<6,4>

分析

同小和问题类似，都是左边的数比较右边的数，解决思路几乎相同，唯一不同是，需要从大到小排序！

对 merge() 稍作修改即可：

void merge(int* arr, int l, int m, int r)
{
	int* help = new int[r - l + 1];
	int p = 0;             //help[]的pointer
	int lp = l;            //left pointer
	int rp = m + 1;        //right pointer
	while (lp <= m && rp <= r)
	{
		if (arr[lp] > arr[rp])
		{
			count_1 += r - rp + 1;
		}
		help[p++] = arr[lp] > arr[rp] ? arr[lp++] : arr[rp++];
	}
		
	while (lp <= m)
		help[p++] = arr[lp++];
	while (rp <= r)           //第9行和第11行的while只可能进入一个
		help[p++] = arr[rp++];
	for (int i = 0; i < r - l + 1; i++)
		arr[l + i] = help[i];
	delete[] help;
}

两倍大问题

给定一个数组，计算出每个数右侧比自身要小两倍还多的数的累计个数。如数组 [9,5,4,2] ，9 -> 4，9 ->2，5 -> 2，结果为 3。

分析
同逆序对类似，也是关于前面数字大于后面数字的问题，所以也最好使用归并算法的降序方式。 不同的是，此时不能一边 merge 一边比较二倍大 。如果仍按之前的方式边计算边 merge，会出现如下逻辑问题：
右图笔误,应该是5被放入辅助数组第一个位置
所以应该先完成所有计算，再 merge：

代码如下：

void merge(int* arr, int l, int m, int r)
{
	int lp = l;           
	int rp = m + 1;       
	while (rp <= r && lp<=m)
	{
		if (arr[lp] > (arr[rp] * 2))
		{
			count_1 += r - rp + 1;
			lp++;
		}
		else
			rp++;
	}

	int* help = new int[r - l + 1];
	int p = 0;             //help[]的pointer
	lp = l;            //left pointer
	rp = m + 1;        //right pointer
	while (lp <= m && rp <= r)
	{
		help[p++] = arr[lp] > arr[rp] ? arr[lp++] : arr[rp++];
	}
		
	while (lp <= m)
		help[p++] = arr[lp++];
	while (rp <= r)           //第9行和第11行的while只可能进入一个
		help[p++] = arr[rp++];
	for (int i = 0; i < r - l + 1; i++)
		arr[l + i] = help[i];
	delete[] help;
}