排序（三）——快速排序（递归以及栈和队列实现非递归）超详细

1.hoare法

2.挖坑法

3.前后指针法

4.快排的非递归

4.1 栈实现快排非递归

4.2 队列实现快排非递归

快排我们之前在学习通讯录的时候就用了，那时候我们知道快排是一个很牛逼的排序算法，那他到底是怎么实现的呢？

1.hoare法

快速排序是很久之前一个叫hoare的大佬最先提出来的，他提出来的快速排序的单趟排序思路就是： 1.选一个key（一般是第一个或者最后一个）

2.把比key小的值排在左边，比key大的值排在右边。

第一步：选定一个key，初始化 L 和 R

第二步：R从右往左找比 key 小的值，找到之后就停下来。

第三步：L从左往右找比key大的值，找到之后停下来

第四步：L和R位置的数据交换

第五步：R继续从右往左找小

然后L继续从左往右找大

继续交换

最后R和L相遇

第五步：R和L相遇之后，key 与相遇位置的数交换。

相遇有两种情况，一种是 R 移动与 L 相遇，一种时 L 移动与 R 相遇，他们相遇点的数据一定是比key小的值，第一种情况 R 移动与 L 相遇说明 R 走过的都是比key大的值，而 L 的位置要不就是key，要不就是上一次交换完的比key小的值。第二种情况 L 移动与 R 相遇，L 走过的都是比 key 小的值，L 在移动说明 R 已经停在了比 key 小的值上了，这时候像雨点也是比key小的值了。

当然我们也可以选择右边做 key ，这时候就是 L 先走，同样是 L 找大， R 找小。

单趟排序的意义是什么呢？

1.把 key 排到了他的最终位置上，后续的操作都不用修改key的位置了

2.以 key 为中心分割出了两个区间，左区间比 key 小，有区间都比 key 大。如果左右两个区间都有序的话，整个数组就是有序的。

单趟排序的实现：要注意的是，单趟排序的区间必须要有数据，如果单趟排序的得区间不合法就返回，或者只有一个数据的时候，也不用进行排序了，只有一个数据算有序。


//快排
void QuickSort(int *a, int begin,int end)
{
	assert(a);
	PartSort(a, begin,end);
}

//单趟排序实现
void PartSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int keyi = begin;
	int key = a[keyi];
	int Left = begin;
	int Right = end;
	while (Left < Right)
	{
		while (Left<Right && a[Right]>=key)//R找小，同时相遇的时候要结束循环.注意R找的是比key小的值，相等的值不停
		{
			Right--;
		}
		while (Left < Right && a[Left] <= key)//L找大，同时相遇要退出循环
		{
			Left++;
		}
		Swap(&a[Left], &a[Right]);
	}
	Swap(&a[keyi], &a[Left]);//key与相遇点交换
}

单趟排序完之后，以 key 为基准为成了左右两个区间

这时候如果左区间和右区间有序的话，整个数组就是有序的了。这时候有没有发现这里的解决方案和二叉树的遍历有点像。

我们让整个数组有序这个问题划分为让左区间和右区间有序这两个子问题，而子问题在单趟排序之后又划分为更小的子问题，最终的最小子问题就是区间只有一个数据或者区间非法。这不就是二叉树的前序遍历吗？

对于上面的简单例子，我们能直接画出它的递归图，与二叉树的前序遍历一模一样。注意简单了，我们直接递归就能解决了，而递归的结束条件就是区间非法和一个值的区间。

假设相遇点时meet，左子区间就是 [begin,meet-1]，右子区间就是[meet+1,end]

这时候我们就要修改一下上面的单趟排序了，因为我们需要用到 meet，所以把返回值类型改为int。


//快排
void QuickSort(int *a, int begin,int end)
{
	assert(a);

	if (begin >= end)//最小子问题返回条件
		return;
	//划分子问题
	int meet=PartSort(a, begin,end);
	QuickSort(a,begin, meet - 1);
	QuickSort(a,meet + 1, end);

}

//单趟排序实现
int PartSort(int* a, int begin, int end)
{
	int keyi = begin;
	int key = a[keyi];
	int Left = begin;
	int Right = end;
	while (Left < Right)
	{
		while (Left<Right && a[Right]>=key)//R找小，同时相遇的时候要结束循环.注意R找的是比key小的值，相等的值不停
		{
			Right--;
		}
		while (Left < Right && a[Left] <= key)//L找大，同时相遇要退出循环
		{
			Left++;
		}
		Swap(&a[Left], &a[Right]);
	}
	Swap(&a[keyi], &a[Left]);//key与相遇点交换

	return Left;//返回相遇点
}

这就是快排的递归实现。

而这种实现快排的时间复杂度是多少呢？

最好的情况就是meet每次都是在区间的中心点，每一次划分子问题都是分成左右两个相同大小的区间，这时候递归深度就是logN, 而每一层递归都比上一层要排序的数据少1第一层排序N个，最后一层的排序的数量是N-logN+1，我们就把每一层都看成 N 个数单趟排序，这时候他的时间复杂度就是O(NlogN).

最坏的情况就是每一次选key都是选到最小值或者最大值，这时候递归的深度就是N-1，而每一层的单趟排序的数据个数依次减一，第一层为N，最后一层为1，这就是一个等差数列求和的问题，他的时间复杂度就是O(N^2).

如此一来，当数据量很大且接近有序是，快排递归的深度太深，可能会导致栈溢出。debug版本下每一层函数栈帧都会加一系列的调试信息，如果栈溢出了，可以切换release版本，release版本下函数栈帧会小的多。但是如果还是栈溢出的话，那就只能优化 key 的选择或者用非递归实现了。

如何优化选key呢？

第一种方案就是随机选 key ，我们可以随机选一个区间中的位置，将其与左边界值或者右边界调换，然后做key，进行单趟排序。这样一来，即使是有序的数据也不会出现最坏的情况了。但是这样一来不确定性就变大了，我们也不能很好的调试或者读代码。

我们知道，快排只在有序的时候会出现问题，那么能不能针对有序来优化选key呢？

第二种方案就是每一次选key都选区间的中间位置的值做key，将其与左边界或右边界调换之后单趟排序。

这种方案虽然随机序列和有序序列都能处理，但是如果数据是部分有序呢？如果最小的数或者最大的数据都在中间呢？如何才能更搞笑呢？

第三种方案就是第二种方案的优化，我们选取左边界值，中间位置值，右边界值之中的中间数做key。这时候key最坏的情况也是次大或者次小的数。

我们为什么要把key放在最左边或者最右边，而不是在中间呢？

如果key在中间位置的话，是让 L 先走呢还是 R 先走呢？相遇点在key的左边或者在key的右边要不要分情况讨论呢？这样一来就会麻烦很多，而我们将key放到左右边界上就不会有这么多麻烦。

我们将 key 的选值优化，可以用一个函数来求这三个位置中的中间属的位置。

//求中间数位置
int GetMidPos(int* a, int begin, int end)
{
	assert(a);
	int mid = begin + (end - begin) / 2;

	if (a[begin] > a[mid])
	{
		if (a[mid] >= a[end])//等于的时候返回谁都是一样的    begin  mid >= end
			return mid;
		else
		{
			if (a[begin] > a[end])//   begin  end  mid
				return end;
			else				 //  end  begin  mid
 				return begin;
		}
	}
	else						//mid >= begin
	{
		if (a[end] >= a[mid])	   // end   mid  begin
			return mid;
		else                     
		{
			if (a[end] > a[begin])	//  mid  end   begin
				return end;
			else                   //mid    begin  end
				return begin;
		}
	}
}

这时候我们就可以优化QuickSort的keyi了

//快排
void QuickSort(int *a, int begin,int end)
{
	assert(a);

	if (begin >= end)//最小子问题返回条件
		return;
	//划分子问题
	int meet=PartSort(a, begin,end);
	QuickSort(a,begin, meet - 1);
	QuickSort(a,meet + 1, end);

}

//单趟排序实现
int PartSort(int* a, int begin, int end)
{
	int keyi = GetMidPos(a,begin,end);
	Swap(&a[keyi], &a[begin]);//左边界做key
	keyi = begin;
	int key = a[keyi];
	int Left = begin;
	int Right = end;
	while (Left < Right)
	{
		while (Left<Right && a[Right]>=key)//R找小，同时相遇的时候要结束循环.注意R找的是比key小的值，相等的值不停
		{
			Right--;
		}
		while (Left < Right && a[Left] <= key)//L找大，同时相遇要退出循环
		{
			Left++;
		}
		Swap(&a[Left], &a[Right]);
	}
	Swap(&a[keyi], &a[Left]);//key与相遇点交换

	return Left;//返回相遇点
}

//求中间数位置
int GetMidPos(int* a, int begin, int end)
{
	assert(a);
	int mid = begin + (end - begin) / 2;

	if (a[begin] > a[mid])
	{
		if (a[mid] >= a[end])//等于的时候返回谁都是一样的    begin  mid >= end
			return mid;
		else
		{
			if (a[begin] > a[end])//   begin  end  mid
				return end;
			else				 //  end  begin  mid
 				return begin;
		}
	}
	else						//mid >= begin
	{
		if (a[end] >= a[mid])	   // end   mid  begin
			return mid;
		else                     
		{
			if (a[end] > a[begin])	//  mid  end   begin
				return end;
			else                   //mid    begin  end
				return begin;
		}
	}
}

这时候我们就可以对比快排和其他几种排序算法的效率了

在十万级别这个赛道快排和堆排和希尔排序是差不多的。而另外两位就不要再就进入下一个测试了

再测试百万数据

我们发现他们还是拉不开什么差距的

再测试千万数据

从这里我们也发现了，快排和堆排是一个级别的，希尔排序稍微差一些，但是它有它所擅长的领域。而快排和堆排怎么评价优劣呢？我还是认为对适合用来解决topk问题，而单纯的排序的话，既然快排和堆排是差不多的，我更推荐快排，因为堆排毕竟要建堆，实现起来更复杂一些。总结还是要看场景来选择排序算法。

2.挖坑法

前面我们讲的单趟排序的思路是hoare最初提出的思路，但是那种实现有很多细节或者说坑要注意，比如L和R移动的时候也要判断是否相遇，这些在实现的时候我们很容易忽略。

我们这里要学习的一种方法就是挖坑法，快排的主框架是不变的，还是前序遍历的实现，变的是单趟排序的思路。

首先挖坑法的精髓就是坑（hole）

第一步：起始状态基本与hoare发差不多，但是这里我们要用一个变量来保存key的值，而key的位置就变成了一个坑

第二步：R从右向左找比key小的值，找到之后停下来，把这个值填到坑里，同时，这个位置就成了一个新坑。

第三步：L从左往右找比key大的值，找到之后L停下来，把L所知的值填到坑里，同时这个位置就成了新坑。

第四步：重复R找小填坑，L找大填坑直到相遇。

第五步：把key填到相遇点的坑里。相遇点一定是坑，以为像雨点是L或者R上次挖的坑或者key留下的坑

我们这里说的坑并不是说把原来的数据给删除了，而是因为这个值已经被复制到了上一个坑，这个位置等着被下一个数据覆盖。

挖坑法的单趟排序实现起来比hoare发简单，细节更少而且更好理解。

//快排单趟实现 挖坑法
int QuickPastSort2(int* a, int begin, int end)
{
	assert(a);
	int keyi = GetMidIndex(a, begin, end);
	int key = a[keyi];
	Swap(&a[keyi], &a[begin]);
	keyi = begin;
	//新坑
	int hole = begin;
	int left = begin;
	int right = end;

	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		//填坑换坑
		a[hole] = a[right];
		hole = right;
		
		while (left < right&&a[left]<=key)
		{
			left++;
		}
		a[hole] = a[left];//就算已经相遇了也没有影响，key最后会覆盖
		hole = left;
	}
	a[hole] = key;
	//相遇点就是最后的这个坑
	return hole;
}

这个方法和hoare法其实基本都是一样的，还是选左边做可以就R先走，如果选右边做key就L先走

3.前后指针法

前后指针的核心思想还是用 prev 找大，用cur找小，找到之后交换，但是与上面的两种方法还是有很大的区别的。

初始状态，首先我们还是选左边做key，prev指针停留在key上面，cur指针指向key的下一个位置。

第一步：prev和cur同时往前走，直到 prev 的下一个位置是比key大的数

第二步：prev停在比key大的数前面，cur往后走找比key小的数。

第三步：cur找到比key小的值后，prev先++，然后prev和cur的位置的数交换。

然后cur继续找比key小的值，找到之后就停下来。然后prev先++，然后prev与cur的位置的值交换。

最后cur 越界了，然后 key 与prev指向的位置交换

这个方法的精髓就是当prev停下来之后，往后 prev 与cur中间的数都是比key大的数。

最后，cur越界，prev 指向的就是最后一个比key小的值，然后key与其交换，这时候就跟前面的思路一样了，开始划分子问题递归。

代码有两种写法，一种是过程稍微详细一点的，把prev的移动分情况写出来

//快排单趟实现    前后指针法
int QuickPartSort3(int* a, int begin, int end)
{
	assert(a);
	//选key
	int keyi = GetMidIndex(a, begin, end);
	Swap(&a[keyi], &a[begin]);
	int key = a[begin];
	keyi = begin;
	//初始化
	int prev = begin;
	int cur = begin + 1;
	while (cur <= end)
	{
		if (a[prev + 1] <= key)
		{
			prev++;
			cur++;
		}
		else if(a[cur]>=key)
		{
			cur++;
		}
		else
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}
	}
	Swap(&a[begin], &a[prev]);
	return prev;
}

这种是把所有的情况都分情况来执行。

还有一种十分简洁的代码

//快排单趟实现    前后指针法
int QuickPartSort3(int* a, int begin, int end)
{
	assert(a);
	//选key
	int keyi = GetMidIndex(a, begin, end);
	Swap(&a[keyi], &a[begin]);
	int key = a[begin];
	keyi = begin;
	//初始化
	int prev = begin;
	int cur = begin+1;
	
	while (cur <=end)
	{
		if (a[cur] < key && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		//不管什么情况cur++
		cur++;
	}
	Swap(&a[begin], &a[prev]);
	return prev;
}

这中代码的思路就是，因为初始cur九千prev前一位，当cur遇到比key小的值时，prev往前走一位，这时候当 prev 与cur相等的话，说明 cur 还没有遇到比key大的值，不用交换，然后cur++。

当cur的值比key小，且 prev++ 之后比cur小，说明之前cur走的时候遇到了比key大的值，遇到的比key大的值的个数就是他们之前间隔的数据个数。也就是说，这种写法也是 prev 与 cur 中间间隔的值都是比key大的值。

4.快排的非递归

前面都是递归的玩法，但是我们前面说过，快排最坏的情况可能会遇到递归层次太深的情况，这时候可能会导致栈溢出，当栈溢出时我们如何解决呢？这就要求我们还要掌握快排的非递归写法。

我们前面说过，快排其实相当于二叉树的前序遍历，先对自身单趟排，然后再划分子问题，其实他又与前序遍历有所区别，前序遍历是要先遍历完左子树在去遍历右子树，而快排则不一样，

虽然我们在上面都是用前序遍历来实现的，但是我们观察其递归展开图，我们就会发现，他的左右的谁先递归的顺序其实并不是很重要，所以我们其实也可以用之前学二叉树时的层序遍历来解决快排的非递归，这时候我们是一层一层排序的，不会影响下一层的子问题，用队列来实现，不过要记住实现的时候出栈入栈都是一次插入或者删除两个数据，这两个数据就是子问题的区间。

层序遍历的思想我们之前已经学习过了，而对于快排，我们也可以严格按照前序遍历来实现他的非递归，就是用栈。我们都知道栈有后入先出的特点，那么我们是不是可以把右区间先入栈，然后再入左区间（区间的两个值也要注意顺序，特别是是拿出来的时候不要搞反了），这样我们拿区间的时候也是先拿左区间，然后再入左区间的子区间………这样一来就和递归的顺序完全一致了。

我们先将之前实现的栈的代码拷贝一份过来

4.1 栈实现快排非递归

然后就按照上面的思路实现代码


void StackQuickSort(int* a, int n)
{
	assert(a);
	//左边界0 ，右边界n-1
	ST st;
	STInit(&st);
	//先入区间右边界
	StackPush(&st, n - 1);
	//再入区间左边界
	StackPush(&st, 0);
	//栈不为空就循环
	while (!StackEmpty(&st))
	{
		int begin = StackTop(&st);
		StackPop(&st);
		int end = StackTop(&st);
		StackPop(&st);

		//最小子问题
		if (begin >= end)
			continue;
		//非最小子问题
		else
		{
			//先单趟排序区间
			int meet=QuickPastSort1(a, begin, end);
			//子区间入栈
			//先入右子区间
			StackPush(&st, end);
			StackPush(&st, meet + 1);
			StackPush(&st, meet - 1);
			StackPush(&st, begin);
		}
	}
	STDestroy(&st);
}

4.2 队列实现快排非递归

用队列来实现层序遍历的代码如下：

void QueueQuickSort(int* a, int n)
{
	assert(a);
	Queue q;
	QueueInit(&q);
	//左右边界按顺序入队列
	QueuePush(&q, 0);
	QueuePush(&q, n - 1);
	while (!QueueEmpty(&q))
	{
		int begin = QueueFront(&q);
		QueuePop(&q);
		int end = QueueFront(&q);
		QueuePop(&q);
		if (begin >= end)
			continue;
		
		int meet=QuickPastSort1(a, begin, end);
		QueuePush(&q, begin);
		QueuePush(&q, meet-1);
		QueuePush(&q, meet+1);
		QueuePush(&q, end);
	}

	QueueDestroy(&q);
}

用栈和队列来实现快排的非递归的话，我们最多只额外调用了两层栈帧，空间复杂度就是O(1)。

不过我们正常使用的时候还是用递归更加方便，只有再递归实现不了的时候，我们再想办法用非递归来实现