Non recursive writing of quick sort

Learned the recursive algorithm of quick sorting , We may sigh that recursion is really a good thing , But in different cases , We need to consider a lot of things , If recursion is used under the influence of big data, stack overflow occurs , At this time, we should consider using non recursive to realize quick sorting .

The code implementation is as follows ：

// Non recursive implementation of quick sorting  
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);
}

Here we use the stack to help us achieve a recursive effect .

Implementation steps ：

1. Interval passed in left,right

2. Take out left,right, And get the subscript of the reference number

3. Judge the interval [left,pivot-1] [pivot+1,end] Whether there is , If it exists, it is stored in the stack

4. Repeat the above operation , Until there are no elements in the stack

  Remember to destroy the stack after using it .