归并排序及其分析

归并排序

该排序的算法思想基于这样一个事实——不断将两个「小的」「有序的」的数组归并成一个「大的」「有序的」的数组，这是分治思想的一个典型应用

可以看到，该排序可以通过递归来实现，并且它一定会有两种基本实现：自顶向下、自底向上

​

原地归并的抽象方法

由于需要将两个小的、有序的数组合并成一个大的、有序的数组，那么我们就必须要一个 merge 函数来实现这个过程。通过递归地不断调用该函数进而实现整体的归并函数

我们设计这样一个函数签名 merge(vector<int>& a, int lo, int mid, int hi) 来实现将两个有序子数组 a[lo, mid] 和 a[mid + 1, hi] 归并成一个大的有序的数组 a[lo, hi] （其中 hi > lo）。其实现如下：

class Merge
{
public:
	static bool less(int v, int w)
	{
		return v < w;
	}

	static void exch(vector<int>& a, int i, int j)
	{
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	static void merge(vector<int>& a, int lo, int mid, int hi)//[lo, mid], [mid+1, hi]
	{
        //aux不在该函数内部初始化
		int i = lo, j = mid + 1;
		for (int k = 0; k <= hi; k++)
			aux[k] = a[k];
		for (int k = 0; k <= hi; k++)
		{
			if (i > mid)
				a[k] = aux[j++];
			else if (j > hi)
				a[k] = aux[i++];
			else if (less(aux[j], aux[i]))
				a[k] = aux[j++];
			else a[k] = aux[i++];
		}
	}
private:
	static vector<int>aux;//辅助数组
};

该方法先将 a[] 数组复制到 aux[] 数组当中，然后再归并回 a[] 中

lo 与 hi 均表示对数组进行界限，mid 将一个数组分割成两个小数组，i 与 j 用来遍历这两个小数组

在对 a[] 进行归并时，有：

• 如果左半边元素用完时（if(i > mid)），选择右半边元素（a[k] = aux[j++]）

• 如果右半边元素用完时（if(j > mid)），选择左半边元素（a[k] = aux[i++]）

• 右半边当前元素小于左半边当前元素（if(less(a[j], a[i]))），选择右半边元素（a[k] = aux[j++]）

• 左半边当前元素小于等于右半边当前元素（else 部分），选择左半边元素（a[k] = aux[i++]）

​

自顶向下的归并

我们的目的是，将所有数组分割到不能再分割时（数组大小为 2 ），再对各个数组进行归并.也就是说，归并是发生在叶子节点的，因此需要用后续遍历来实现

class Merge
{
public:
	static bool less(int v, int w)
	{
		return v < w;
	}

	static void exch(vector<int>& a, int i, int j)
	{
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	static void sort(vector<int>& a)
	{
		aux.assign(a.size(), 0);
		sort(a, 0, a.size() - 1);
	}

	static void sort(vector<int>& a, int lo, int hi)
	{
		if (lo >= hi)//区间端点相等，该区间就一个数，无法归并
			return;
		int mid = hi + (lo - hi) / 2;
		sort(a, lo, mid);
		sort(a, mid + 1, hi);
		merge(a, lo, mid, hi);//后序遍历
	}

	static void merge(vector<int>& a, int lo, int mid, int hi)//[lo, mid], [mid+1, hi]
	{
		int N = a.size();
		aux.assign(N, 0);
		int i = lo, j = mid + 1;
		for (int k = 0; k <= hi; k++)
			aux[k] = a[k];
		for (int k = 0; k <= hi; k++)
		{
			if (i > mid)
				a[k] = aux[j++];
			else if (j > hi)
				a[k] = aux[i++];
			else if (less(aux[j], aux[i]))
				a[k] = aux[j++];
			else a[k] = aux[i++];
		}
	}
private:
	static vector<int>aux;//辅助数组
};

​

分析

由于归并排序是通过辅助数组与主数组相互赋值来实现的，因此归并排序不需要交换元素，只需要比较元素。因此宏观上，我们从比较次数来分析整个归并排序的时间复杂度；微观上，我们从访问数组次数来分析单次归并排序的时间复杂度

• 在比较次数方面：

我们用 \(C(N)\) 来表示将一个大小为 \(N\) 的数组进行归并所需要的比较次数。显然，\(C(0)=C(1)=1\) ，当我们通过 sort 递归调用时，比较次数的上限是： \[ C(N)\le C(\lfloor N/2 \rfloor)+C(\lceil N/2 \rceil)+N \] 式中第一项为对左半边进行归并所需的比较次数，第二项为对右半边进行归并所需的比较次数，第三项为对整个数组进行归并所需的比较次数。由于归并所需的最小比较次数为 \(\lfloor N/2 \rfloor\) （只需要比较一半的元素，另一半自动归位），因此 \(C(N)\) 的下限为： \[ C(N)\ge C(\lfloor N/2 \rfloor)+C(\lceil N/2 \rceil)+\lfloor N/2 \rfloor \] 取最极端的情况（考虑上限），令 \(N=2^n\) 。因为 \(\lfloor N/2 \rfloor=2^{n-1}\) ，\(\lceil N/2 \rceil=2^{n-1}\) 有： \[ C(2^n)= 2\cdot C(2^{n-1})+2^{n} \] 同时除以 \(2^n\) ，有： \[ C(2^n)/2^n=C(2^{n-1})/2^{n-1}+1 \] 迭代一次，有： \[ C(2^n)/2^n=C(2^{n-2})/2^{n-2}+1+1 \] 迭代 \(n-1\) 次，有： \[ C(2^n)/2^n=C(2^0)/2^0+n \] 同时乘以 \(2^n\) ，有： \[ C(N)=NlogN \] 也就是说，对于任意长度为 \(N\) 的数组，最多需要有 \(NlogN\) 次比较就可以完成排序

• 在访问数组方面：

对于长度为 \(N\) 的数组，单次归并最多会访问 \(6N\) 次数组，整体会访问 \(6NlogN\) 次数组

这个的证明很简单。在对 aux 数组进行复制时，有 \(N\) 次数组读取和 \(N\) 次数组写入，在对 a 进行归并时，有 \(N\) 次数组读取和 \(N\) 次数组写入

在比较方面，对长度为 \(N\) 的数组，对数的比较最多为 \(N/2\) 次，但由于我们第二个 for 有四次比较，因此比较的总次数为 \(2N\)

总和就是 \(6N\)

​

自底向上的归并

我们首先对数组实行两两归并（单个小数组大小为 1 ，归并后大数组大小为 2 ），四四归并（两个大小为 2 的小数组进行归并），八八归并，如此这般

class Merge
{
public:
	static bool less(int v, int w)
	{
		return v < w;
	}

	static void exch(vector<int>& a, int i, int j)
	{
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	static void sort(vector<int>& a)
	{
		int N = a.size();
		for (int sz = 1; sz < N; sz = sz + sz)//小数组大小不能比N大
			for (int inx = 0; inx + sz < N; inx += sz + sz)//inx为数组开始下标，每次递增两个小数组的大小
				merge(a, inx, inx + sz - 1, min(inx + sz + sz - 1, N - 1));//我们考虑的是数组下标，因此需要减1
	}


	static void merge(vector<int>& a, int lo, int mid, int hi)//[lo, mid], [mid+1, hi]
	{
		int N = a.size();
		aux.assign(N, 0);
		int i = lo, j = mid + 1;
		for (int k = 0; k <= hi; k++)
			aux[k] = a[k];
		for (int k = 0; k <= hi; k++)
		{
			if (i > mid)
				a[k] = aux[j++];
			else if (j > hi)
				a[k] = aux[i++];
			else if (less(aux[j], aux[i]))
				a[k] = aux[j++];
			else a[k] = aux[i++];
		}
	}
private:
	static vector<int>aux;//辅助数组
};

无论是自顶向下还是自底向上，比较次数和数组访问次数都一样

​

最后

书中证明了所有基于比较的算法的比较次数的下限为 \(\sim NlogN\) ，而归并排序只需要比较，不需要移动

所以归并排序是一种渐进最优的基于比较的算法