优化以及排序的效率分析

排好0-1这个区间后，因为其左右区间都为最小子区间，一个是只有单个元素和空元素，所以我们不将其区间下标压入栈中不进行单趟排序。代码的具体实现

挖坑法单趟排序代码

//单趟 快速排序挖坑法int PartSort2(int* a, int left, int right){	//最小子问题 :	//区间内只有一个值(left == right)或者为空(left >= right)	if (left >= right)		return left;	//先从右边往左找比key值小的数填到坑里 然后right指向的地方就变成了新坑	int end = right;	//一开始坑是最左边的元素。
单趟排序存在的问题思考：
  这个时候我们就会思考这样一个问题：最后一次交换为什么能保证比key小的值换到了前面，如果与key交换的值是大于key的，那不就出问题了吗？但其实我们发现这种情况是不存在的，交换后的结果仍然是符合左边值的比key小，右边的值比key大。
  在一个理想的均匀二叉树中，我们知道最后一层的叶子个数占据整个二叉树节点个数的一半，二叉树最后三层的节点个数加起来差不多接近整个二叉树的节点个数，最后这几层的二叉树要排序的区间较小，如果我们可以让最后这几层节点不进行递归排序，而是使用别的排序方法排序，就可以减少递归的次数，这个时候我们可以通过在小区间内使用插入排序来减少递归次数，插入排序适合排序元素个数较少的数组。但是有一点要注意：这两种方法对同一个数组进行一次单趟排序后的数组元素位置不一定对应相同。
 我们将下面这个1-9乱序数组进行递归，每次递归进行一次单趟排序排好key的位置
如果是hoare法，排好6后元素的顺序是这样：
如果是挖坑法，排好6后元素的顺序是这样：
我们可以发现这两种单趟排序后6的左右区间的元素顺序不是一一对应的，但是都符合快速排序的思想，即6的左边元素都小于6，6的右边的元素都大于6。
（二）挖坑法
1、在这个过程中，左右区间的下标是单趟排序所需要的关键信息，这个时候我们就需要用到栈的后进先出的特性来模拟递归来实现非递归的快速排序。代码的具体实现
霍尔法单趟排序代码
// 快速排序hoare版本 单趟排序int PartSort1(int* a, int left, int right){	if (left >= right)		return 0;	//最小子问题 :	//区间内只有一个值(left == right)或者为空(left >= right)	int end = right;//先从右边往左找比key值小的数丢到前面	int begin = left;//从左边下标从右找比key大的数丢到后面	int key = left;//要排序的下标	while (begin < end)//当左右指针相遇时结束	{		//从右往左找比key小的数		while (begin < end && a[end] >= a[key])		{			end--;		}		//找到比key小的数后就从左往右找比key大的数		while (begin < end && a[begin] <= a[key])		{			begin++;		}		//交换这两个数		MySwap(&a[begin], &a[end]);//功能相当于swap	}	//出来后说明begin和end相遇了，此时该下标位置就是key值排序后所在的位置	MySwap(&a[key], &a[begin]);//将key换到相应的位置	key = begin;//更新key的下标	return key;//返回排好了的元素的下标}
霍尔法递归代码
void QuickSort(int* a, int left, int right){	if (left >= right)//当只有一个元素时是最小子问题		return;	//此区间执行单趟排序	 	//hoare法	int key = PartSort1(a, left, right);//接收已经排好了的元素下标	//递归子区间   [left,key - 1]key[key + 1,right]	QuickSort(a, left, key - 1);	QuickSort(a, key + 1, right);	return;}
  写完后我们可以随机生成一个数组来测试一下写的代码是否有问题。优化以及排序的效率分析。
其递归展开图
  我们发现这个二叉树的形状极其不均匀，每次递归只有右区间而没有左区间。
1、我们首先把第一个元素的值用key保存下来，并且在第一个位置挖个坑，然后定义左右指针，像hoare版本的方法一样右指针先从右到左遍历数据，当右指针遍历到比key值小的数就停下来，并且将右指针指向的值赋值给坑位，也就是填到坑里，然后右指针就变成了新的坑位。本篇文章将介绍通过递归的不同写法的方法和非递归的方法来实现简单的快速排序。快速排序的优化算法
1、这样我们就排好了key这个元素。
2、
四、每次取栈顶的区间进行单趟排序，单趟排序完成后又将其左右区间的下标压入栈中，直到栈为空为止结束。
  其原因是，我们是先让右指针先向左遍历找比key小的值，找到后才让左指针向右遍历，这样可以保证相遇的时候指向的值比key小。单趟排序方法动图
单趟排序后的结果：
  这里的key不再表示要排序的值的下标，而是用来存储key的值。三数取中和随机取数优化算法
  在上面的快速排序中，如果排序的数是极其混乱的，那么在效率上看不出什么问题，但如果我们排序的一组数据是下面这组数据的话,就会发现很明显的问题。
一、
我们将下面这个1-9乱序数组进行递归，每次递归进行一次单趟排序排好key的位置
下面是递归展开图：
3、
代码实现：
void QuickSort(int* a, int left, int right){	if (left >= right)//当只有一个元素时是最小子问题		return;	//优化算法	//随机取数优化算法	int rand_index = left + rand() % (right - left + 1);//在区间内随机选一个元素	MySwap(&a[left], &a[rand_index]);//将随机选到的元素与最左边的元素交换作为要排序的key值	//此区间执行单趟排序	//hoare法	//int key = PartSort1(a, left, right);//接收已经排好了的元素下标	//挖坑法	//int key = PartSort2(a, left, right);//接收已经排好了的元素下标	//左右指针法	int key = PartSort3(a, left, right);//接收已经排好了的元素下标	//递归子区间   [left,key - 1]key[key + 1,right]	QuickSort(a, left, key - 1);	QuickSort(a, key + 1, right);	return;}
三数取中法
  顾名思义就是在三个数中找一个中间值作为key值来排序，也就是在区间中选三个数，分别是左边界下标、右边界下标、
  
  第二种情况是：左指针先前发生过与右指针的交换，交换后左指针指向的值一定是小于key的，这个时候右指针与左指针相遇后指向的值与key值交换，可以保证交换的值比key小。快速排序的时间和空间复杂度分析
  虽然快速排序的实现方法有很多种，但是其时间复杂度和空间复杂都是不变的。相遇的情况有两种：
 第一种情况是：当右指针停下了，左指针向右遍历时没找到比key大的值，左指针与右指针相遇，这个时候指向的值一定是比key小的。
（三）前后指针法
1、快速排序是托尼·霍尔（Tony Hoare）在1962年提出来的，我们学习快排算法思想，可以提高我们的思考能力。
代码实现：
三个数中得到中间数的函数
//三数取中优化代码int GetMidIndex(int*a,int left,int right)//传入数组和区间的左右下标{	int mid = (left + right) / 2;	if (a[left] <= a[right])// left right 	{		if (a[mid] >= a[right])			return right;		else if (a[mid] <= a[left])			return left;		else			return mid;	}	else//right left	{		if (a[mid] >= a[left])			return left;		else if (a[mid] <= a[right])			return right;		else			return mid;	}}
具体优化代码:
void QuickSort(int* a, int left, int right){	if (left >= right)//当只有一个元素时是最小子问题		return;	//随机取数优化算法	//int rand_index = left + rand() % (right - left + 1);//在区间内随机选一个元素	//MySwap(&a[left], &a[rand_index]);//将随机选到的元素与最左边的元素交换作为要排序的key值	//三数取中优化算法	int mid_index = GetMidIndex(a, left, right);//得到三个数中的中位数	MySwap(&a[left], &a[mid_index]);	//此区间执行单趟排序	//hoare法	//int key = PartSort1(a, left, right);//接收已经排好了的元素下标	//挖坑法	//int key = PartSort2(a, left, right);//接收已经排好了的元素下标	//左右指针法	int key = PartSort3(a, left, right);//接收已经排好了的元素下标	//递归子区间   [left,key - 1]key[key + 1,right]	QuickSort(a, left, key - 1);	QuickSort(a, key + 1, right);	return;}
  上面的这两种优化算法都是针对这种顺序不是很乱而比较接近有序的数组的优化，可以减少出现最坏的情况的几率。
3、非递归代码
// 快速排序 非递归实现 利用栈保存左右下标的值进行快排void QuickSortNonR(int* a, int left, int right){	//下面用到的栈是自己手搓的	//建立栈	Stack stack;	//初始化栈	StackInit(&stack);	//将一组左右下标压入栈	//先将右下标压入栈再压入左下标  先压入右区间再压入左区间	//由于后进先出的关系，这样可以保证先取到的栈顶元素是对应左下标 先递归的区间是左区间的	StackPush(&stack, right);	StackPush(&stack, left);	//这三个变量和上面的霍尔单趟排序的变量作用相同	int begin;//从左边开始往右遍历找比key值大的元素	int end;//从右边开始往左遍历找比key值小的元素	int key;//要排序的值的下标	while (!StackEmpty(&stack))//当栈为空时结束循环	{			begin = StackTop(&stack);//得到要排序左下标		left = begin;//保存左边界下标		StackPop(&stack);		end = StackTop(&stack);//得到要排序右下标		right = end;//保存右边界下标		StackPop(&stack);		key = left;//要排序的下标		//这里和上面写的霍尔单趟排序相同，进行单趟排序将key排到对应位置		while (begin < end)//当左右指针相遇时结束		{			//从右往左找比key小的数			while (end > begin && a[end] >= a[key])			{				end--;			}			//找到比key小的数后就从左往右找比key大的数			while (end > begin && a[begin] <= a[key])			{				begin++;			}			//交换这两个数			MySwap(&a[begin], &a[end]);		}		//出来后说明begin和end相遇了，此时该下标位置就是key值排序后所在的位置		MySwap(&a[key], &a[begin]);		key = begin;//将key的下标更新到排好了的位置的下标		//将要递归排序的区域压入栈		//[left,key - 1] key [key + 1,right]		//如果区间内只有一个元素或没有元素就不压入栈		//将分成的两个子区间的右区间压入栈中		if (key + 1 < right)//由于后进先出的关系，这样可以让先递归的区间是左区间的		{			StackPush(&stack, right);			StackPush(&stack, key + 1);		}		//将分成的两个子区间的左区间压入栈中		if (left < key - 1)		{			StackPush(&stack, key - 1);			StackPush(&stack,left);		}	}	return;}
  写完后我们可以随机生成一个数组来测试一下写的代码是否有问题。同理，如果排序1-4时，我们排序的key是2而不是1，这个区间分成的子区间就可以变得均匀。然后右指针再次向左遍历，重复该过程，直到左右指针相遇，这个时候相遇的地方形成的坑位就是key值的位置，我们再把key填入左右指针相遇的坑里，这样key的位置就排好了。空间复杂度(log(n))
  不管我们使用递归的方法实现快排还是栈非递归的方式模拟递归，都占用了一定的空间。我们用栈存储下标也需要开辟这么多空间，所以空间复杂度为log(n)。和区间的中间下标这三个数进行比较，将数值大小介于两者之间的数作为key值排序，这样可以保证让key值排好后的位置靠近中间。