快速排序的非递归写法

学习了快速排序的递归算法，我们可能会感叹递归真是一个好东西，但是在不同的情况下，我们需要考虑很多东西，如果在大数据的影响下使用递归发生了栈溢出，那我们这时候就应该考虑使用非递归来实现快速排序。

代码实现如下：

//非递归实现快速排序 
void QuickSort3(int*a,int left,int right){
	ST s;
	InitStack(&s);
	StackPush(&s,left);
	StackPush(&s,right);
	while(!StackEmpty(s)){
		int end=StackGet(s);
		StackPop(&s);
		int start=StackGet(s);
		StackPop(&s);
		int pivot=Partition1(a,start,end);
		if(start<pivot-1){
			StackPush(&s,start);
			StackPush(&s,pivot-1);
		} 
		if(pivot+1<end){
			StackPush(&s,pivot+1);
			StackPush(&s,end);
		}
	}
	StackDestory(&s);
}

这里我们使用了栈来帮助我们完成类似递归的效果。

实现步骤：

1. 传入了区间left，right

2. 取出left，right，并且得到基准数的下标

3. 判断区间[left,pivot-1] [pivot+1,end]是否存在，若存在则存入栈

4. 重复上述操作，直到栈中没有元素

 记得使用完了栈要进行销毁。