//hoare版本
int PartSort1(int* a, int head, int end)
{
	int target = head;
	int left = target + 1;
	int right = end;

	while (right > left)
	{
		//右边先找，找到比target处的数字小的停下   下面经过画图分析，如果不加等号的话，就会陷入死循环~
		while (right > left && a[right] >= a[target])
		{
			right--;
		}

		while (right > left && a[left] <= a[target])
		{
			left++;
		}

		if (right > left)
			Swap(&a[right], &a[left]);
	}
	if (a[right] < a[target])//防止传入的两个数，一次也不进入循环，然后无法判断和target位置所在数组元素大小的情况
		Swap(&a[target], &a[right]);
	target = right;
	return target;
}

后续版本在分治那里哦~

二、挖坑版本

1.思想

可能是想让hoare版本看起来更加好懂一些，在基本思想不变的情况下，稍微改进了一下将两者交换变成了填坑。left right 和key keyi均不变，即左边移动部分右边移动部分目标值目标下标。

只不过在一开始，保存key值然后将此时的keyi位置的数组值视为第一个坑，然后右边找小的开始找小，找到小停下或者遇到left停下，左边找也是如此。如果两者相遇，就讲key值填入此时位置。如果没有，一开始的话就是右边找小的位置将其值填入keyi的位置，然后自己形成坑由左边找到大的来填，之后就是左右互填即可，直到两者相遇。

分治的话没有什么可以说的。大致思路如上。

2.代码

//挖坑版本
int PartSort2(int* a, int head, int end)
{
	int keyi = head;
	int left = head + 1;
	int right = end;
	int key = a[keyi];
	while (right > left)
	{
		//首先右边找到比key小的值，然后把坑填上产生新坑
		while (right > left && a[right] >= key)
			right--;
		a[keyi] = a[right];
		keyi = right;

		//左边找到大的然后填坑
		while (right > left && a[left] <= key)
			left++;

		a[keyi] = a[left];
		keyi = left;
	}
	a[keyi] = key;
	return keyi;
}

三、前后指针版本

1.思想

首先，此方法在核心操作步骤上已经和上面两种完全不同。

这里采用的是双指针前后移动，前面的指针从第二个开始，第一个为目标值并且也是后面指针的位置，前指针一直往后移动，遇到比目标值低的时候，后指针往后移动一步，（此时一定是比目标值大的，因为前指针并没有停止）然后此时处于两位置的值进行交换。

直到后指针移出数组的边界后，然后此时后指针的位置处于原位置(出生的位置)或者交换小的后的位置，总之就是此时后指针指向的位置要么就是目标值要么就是比其小的值，所以目标值与其交换，一轮就执行好了，剩下的用分治去解决即可。

*注意，可能会遇到前指针还未移动，然后后指针就移动，此时两者重复，可以不用进行交换，写代码时可以加入减少时间复杂度。

2.代码

?????????

//前后指针版本
int PartSort3(int* a, int head, int end)
{
	int keyi = head;
	int prev = head;
	int cur = head + 1;
	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[cur], &a[prev]);
		cur++;
	}
	Swap(&a[keyi], &a[prev]);
	keyi = prev;
	return keyi;
}

四、分治思想：

这里就是执行每一轮，然后最终完成程序的过程：首先进行第一轮，第一轮排完后，在目标值的位置的左即begin 和目标值下标减一，这一段和目标值加一和end这两段即可。之后的递归同意是这样的原理，直到递归到没有元素或者只要一个的时候就停止了。

代码:

//快速排序：
void QuickSort(int* a, int head, int end)
{
	//结束标志
	if (head >= end)
		return;
	assert(a);

	int target = PartSort(a, head, end);

    //进入递归，分而治之的思想
    //左边
	QuickSort(a, head, target - 1);
	//右边
	QuickSort(a, target + 1, end);

}

五、两种优化

经过上面的几种方法介绍，相信你已经对快排有一定的了解了。那么现在提出一种场景，来看看我们快排的表现。(注上述三种方法实现的快排均一样的效果)

1.三数取中

比如排? ?1 2 3 4 5 6 7....n? 和? ?3 2 5 1 4 6 7....

排第一个时快排排了大概是N*N 而第二种是正常的时间复杂度，这是为什么呢？原因就是根据快速排序的特性，快速排序的快慢取决于目标值的位置一开始要是就排到中间，那么就可以演变为二分法，但是像这种越接近于有序，那么每次目标值都是最边缘的位置，然后分治里面另一端就会没有用处，永远处理一边，效率自然低下。

所以，这就说明了目标值取得好坏。为了避免这种情况的发生，我们可以针对选目标值做上一点手脚，有随机取值，三数取中等.....但是比较好用的是三数取中，随机值毕竟是有一定的随机性的，说不清楚。下面介绍一下三数取中：

传进原始数组，取头，尾，中三个值，然后三个值分别比较，选出中间值，返回。代码很简答，如下：


//三数取中优化key
int TakeMiddle(int* a, int head, int end)
{
	int middle = (head + end) / 2;
	if (a[head] < a[middle])
	{
		if (a[end] > a[middle])
			return middle;
		else if (a[end] > a[head])
			return end;
		else
			return head;
	}
	else
	{
		if (a[middle] > a[end])  //head  > middle
			return middle;
		else if (a[end] > a[head])
			return head;
		else
			return end;
	}
}

之后操作就是选取目标值，在进行循环之前不变(三种方法均是)，然后得出下标后，与其交换即可，就可以不用动下面写好的代码了：

	int keyi = TakeMiddle(a, head, end);
	Swap(&a[target], &a[keyi]);

2.小区间优化

当递归到要排的数比较少的时候，这个时候在进行递归会发现迭代的层数有点多，此时相较于普通的方法比如(插入排序)效率会有那么一点低下，所以，针对分治里面每次传入的head和end，在一定区间内进行划分即可：

	//小区间使用插入排序缓解最后几层递归过多的问题
	if (head - end > 10)
	{
		//进入递归，分而治之的思想
		//左边
		QuickSort(a, head, target - 1);
		//右边
		QuickSort(a, target + 1, end);
	}
	else
	{
		//微量数据利用插入排序即可
		InsertSort(a, end - head + 1);
	}

六、非递归实现快速排序

1.思想

实际上，非递归实现排序理论上和递归排序没有任何区别，只是在分治或者是在储存区间，在分区间进行每一轮的操作时候发生了变化。

首先，这个问题的提出就是因为递归非常容易造成栈溢出，栈的内存很小。所以，这个时候我们能不能不使用递归来进行区间的划分呢？其实，我们发现递归实际上也是相当于每次传进去的区间不同，那么我们使用非递归的时候，就是每次循环进去不同的区间就好了。

那么如何实现每次循环的区间不同呢？

这就需要一个储存的机制。储存？回顾之前的基础数据结构知识，我们只带栈，队列，堆等数据结构。那么栈和队列用到这个里面是不是刚刚好呢？

对的，在实现栈和队列的时候，使用的是堆内存，堆内存很大，不用担心溢出问题。然后利用栈的先进后出，队列的先进先出原则，每次循环就把区间存进去，一轮弄完后就进行存储，这样就可以解决我们的问题。

具体实现的时候，首先将头和尾插入栈或者队列，栈的话先插尾，然后在头，队列正好相反，然后进入循环，先将本次的区间元素弹出，进入一轮循环，循环完后，在目标值的左右两区间均按照上述步骤即可。

注意在循环里插入的时候判断入栈或者入列条件，即区间的左右必须右大于左，否则不进。条件就是栈、队列空间的元素有无进行判断就好了。

2.实现：

//快速排序的非递归版本(递归的问题，深度太深，容易栈溢出)
//之前是利用递归的方法使其控制对应的区间，那么现在利用栈来储存要改变的区间
void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);
	StackPush(&st, end);
	StackPush(&st, begin);

	//当栈内元素为空时停止循环即可
	while (!StackEmpty(&st))
	{
		int left = StackTop(&st);
		StackPop(&st);

		int right = StackTop(&st);
		StackPop(&st);
		int keyi = PartSort(a, left, right);//PartSort用上述三种方法任意一种均可

		if (left < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}

		if (keyi + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}

	}


	//StackDestroy(&st);
}

上面是用栈来进行实验的，也可以利用队列哦~