【排序篇3】快速排序、归并排序

一、快速排序

1.1 递归

快速排序的递归采用二叉树的前序遍历的思路，单趟排序先确定好一个元素的位置，然后往后递归再确定其他子区域内的某个元素的位置，直到只有一个元素返回。

递归的图示：

代码：

void QuickSort(int* a, int begin, int end)
{
	//区间内小于等于1，就返回
	if (begin >= end)
	{
		return;
	}
	//单趟排序，返回确定位置好的元素下标
	int ki = partsort1(a, begin, end);
	//递归 - 区间：[begin, ki-1]，[ki+1, end]
	QuickSort(a, begin, ki - 1);
	QuickSort(a, ki + 1, end);
}

接下来分析单趟排序的实现。有3种方式：Hoare法、挖坑法、前后指针法。

1??Hoare法
整体思路：

• 通过三数取中获取较靠中间元素的下标mid，然后mid指向的元素与左端的元素进行交换，防止极端情况
• 定义一个变量 ki = left 便于记录左端的值，注意ki是下标
• 先移动右边再移动左边，right指向的元素大于等于ki指向的元素就减1往前走，小于就停下；left指向的元素小于等于ki指向的元素就+1往后走，大于就停下，然后两者停下分别指向的元素进行交换，然后先走右再走左继续移动
• left与right相遇，跳出循环，交换ki指向的元素和left指向的元素，此时left指向的元素就是确定好位置的元素，最后返回下标left

图示：

代码：

//Hoare法
int partsort1(int* a, int left, int right)
{
	//获取较中间的元素的下标
	int mid = getmid(a, left, right);//三数取中
	Swap(&a[left], &a[mid]);//与左端交换，防止极端情况
	int ki = left;//注意ki得到的是下标
	while (left < right)
	{
		//先走右再走左
		while (left < right && a[right] >= a[ki])//是大于等于往前走，小于就停下
		{	// 防止走的过程中越界
			right--;
		}
		while (left < right && a[left] <= a[ki])//是小于等于往前走，大于就停下
		{    // 防止走的过程中越界
			left++;
		}
		Swap(&a[left], &a[right]);//交换两个元素
	}
	Swap(&a[ki], &a[left]);//把ki指向的元素交换到它最终的位置
	return left;//返回确定位置的元素的下标
}

问题1：为什么要三数取中

因为三数取中可以防止出现极端情况，该极端情况指：ki指向的元素本来就应该放在左端，比如：

如果大部分是这种最坏情况，导致快速排序的复杂度为O(N ^ 2)

三数取中可以取到较靠中间位置的元素的下标，尽可能避免了以上情况，就算有个别还是在最左端，但是对整体的效率并没有多大影响。所以三数取中对快速排序的优化有很大的帮助。

代码：

//三数取中
int getmid(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[right] < a[left])
			return left;
		else
			return right;
	}
	else
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[right] > a[left])
			return left;
		else
			return right;
	}
}

问题2：为什么ki取的是下标，不是数组元素

这与最后确定元素位置的交换有关，假设ki是数组元素，交换的是left指向的元素和ki，那么结果是left指向的元素变成了ki这个元素，但是数组左端的元素依旧没变。

ki取的是下标，才能真正交换数组左端和left指向的元素。

问题3：为什么先走右边，再走左边

举个栗子：

2??挖坑法

整体思路：

• 三数取中，与Hoare法的步骤一样
• ki取的是left指向的元素，为后面的填坑作准备
• 定义一个坑hole = left （是下标）
• 先走右边，停下后，将此时right指向的元素覆盖坑位的元素，然后产生新的坑位，right变成坑
• 再走左边，停下后，将此时left指向的元素覆盖坑位的元素，然后产生新的坑位，left变成坑
• 循环全部走完后，最终的hole就是ki要确定的位置，覆盖坑位，然后返回hole

图示：

代码：

//挖坑法
int partsort2(int* a, int left, int right)
{
	//获取较中间的元素的下标
	int mid = getmid(a, left, right);//三数取中
	Swap(&a[left], &a[mid]);//与左端交换，防止极端情况
	int ki = a[left];//注意ki得到的是数组元素
	int hole = left;//初始的坑的位置
	while (left < right)
	{
		//先走右再走左
		while (left < right && a[right] >= ki)//是大于等于往前走，小于就停下
		{	// 防止走的过程中越界
			right--;
		}
		a[hole] = a[right];//覆盖坑位的元素
		hole = right;//产生新的坑位
		while (left < right && a[left] <= ki)//是小于等于往前走，大于就停下
		{    // 防止走的过程中越界
			left++;
		}
		a[hole] = a[left];//覆盖坑位的元素
		hole = left;//产生新的坑位
	}
	a[hole] = ki;//确定元素的位置
	return hole; //返回确定位置的元素的下标
}

3??前后指针法

通过前面的两种方法可以发现：确定好某个元素的位置后，该元素的左右两个区间分别是小于这个元素和大于这个元素（以数组是1,2,3,4,5,6,7,8,9,10为例），也就是说要确定位置的元素是区分两个不同区间的标杆，所以这里可以使用前后指针法，用来区分两块区域。

整体思路：

• 定义前后指针，cur=left+1，pre = left
• 如果cur指向的元素小于等于ki指向的元素，pre先加1，再交换pre和cur分别指向的元素，然后cur++
• cur循环完，交换pre和ki分别指向的元素，pre的位置就是确定好的位置，然后返回pre

图示：

代码：

//前后指针法
int partsort3(int* a, int left, int right)
{
	int mid = getmid(a, left, right);//三数取中
	Swap(&a[left], &a[mid]);//与左端交换，防止极端情况
	int ki = left;//注意ki得到的是下标
	int cur = left + 1, pre = left;//定义前后指针
	while (cur <= right)//范围限制
	{
		if (a[cur] <= a[ki])//如果小于，先++pre再交换分别指向的元素
		{
			Swap(&a[++pre], &a[cur]);
		}
		cur++;//cur都要往后走
	}
	Swap(&a[ki], &a[pre]);//把ki指向的元素交换到它最终的位置
	return pre;//返回确定位置的元素的下标
}

1.2 非递归

快速排序的非递归是用栈模拟递归来实现的，栈的特点是后进先出，递归是先左边再右边的，所以放入栈的数据应该先放右再放左，这样取数据才是先左再右。

图示：

代码：

//快速排序 - 非递归
void QuickSortNoR(int* a, int begin, int end)
{
	stack<int> st;//定义一个栈
	st.push(end);//先放右
	st.push(begin);//再放左
	while (!st.empty())//不为空进入循环
	{
		int left = st.top();//取左值
		st.pop();//删除栈顶元素
		int right = st.top();//取右值
		st.pop();//删除栈元素
		int ki = partsort3(a, left, right);//一趟排序确定某个元素的位置，返回该位置
		if (ki + 1 < right)//整体先放右
		{
			st.push(right);//里面先放右
			st.push(ki + 1);//里面再放左
		}
		if (left < ki - 1)//整体再放左
		{
			st.push(ki - 1);//里面先放右
			st.push(left);//里面再放左
		}
	}
}

快速排序特性总结：

• 时间复杂度：O(N * logN)
• 空间复杂度：O(logN)
• 不稳定

二、归并排序

2.1 递归

归并排序的递归采用二叉树的后序遍历的思想，先分解成小块区间，然后再合并两个小块空间的同时将这两块子区间的元素进行排序。依次类推。这里还要额外开辟一块临时空间，用来对两个子区间排序，在临时空间排完序后，然后把已经排序的元素的拷贝到原数组对应的位置，最终将整个数组排完序。

图示：

代码：

//归并排序-递归
void MergeSort(int* a, int* tmp, int begin, int end)
{
	//区间内元素个数小于等于1返回
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;//取划分区域的下标
	MergeSort(a, tmp, begin, mid);//递归左边
	MergeSort(a, tmp, mid + 1, end);//递归右边
	int begin1 = begin, end1 = mid;//合并的第一块小区间
	int begin2 = mid + 1, end2 = end;//合并的第二块小区间
	int k = begin;//注意k为begin当前区域的初始位置
	while (begin1 <= end1 && begin2 <= end2)
	{   //  谁小谁先放入tmp
		if (a[begin1] <= a[begin2])
		{
			tmp[k++] = a[begin1++];
		}
		else
		{
			tmp[k++] = a[begin2++];
		}
	}
	// 哪块小区间有剩余，直接放入tmp
	while (begin1 <= end1)
	{
		tmp[k++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[k++] = a[begin2++];
	}
	//最后拷贝到原数组对应的位置，完成排序
	memcpy(a + begin, tmp + begin, sizeof(int) * (end2 - begin + 1));
}

2.2 非递归

归并排序的非递归也是模拟递归的过程，只是没有递，只有归，即只有合并的过程，用for循环控制合并区间的大小和范围即可，也要借助临时空间来排序，最后拷贝给原数组。

图示：

代码：

//归并排序-非递归
void MergeSortNoR(int* a, int* tmp, int n)
{
	int gap = 1;//初始合并的子区间大小
	while (gap < n)//范围
	{
		for (int i = 0; i < n; i += gap * 2)
		{
			int begin1 = i, end1 = i + gap - 1;//合并的第一块小区间
			int begin2 = i + gap, end2 = i + gap * 2 - 1;//合并的第二块小区间
			int k = i;
			if (begin2 >= n)//只有第一块小区间，没有第二块小区间
			{
				break;//不能合并，跳出
			}
			if (end2 >= n)//第二块小区间个数较少，但是不影响合并
			{
				end2 = n - 1;//修改end2的值
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[k++] = a[begin1++];
				}
				else
				{
					tmp[k++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[k++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[k++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));//排序+拷贝回原数组
		}
		gap *= 2;//区间增大
	}
}

注意：
上面的代码有两个特殊处理用于非2的次方个元素的数组，如果begin2大于等于n，说明要合并的两个子区间仅仅只有第一块小区间，没有第二块小区间，这时就不需要合并了（第一块小区间在之前已经合并为有序）。如果end2大于等于n，第二块小区间还是存在的，只是元素个数少些，这时就把end2的指向的位置该成第二块小区间内最后一个元素的位置即可。

归并排序特性总结：

• 归并排序要额外开辟一块空间用来处理排序的问题
• 时间复杂度：O(N * logN)
• 空间复杂度：O(N)
• 稳定