【数据结构与算法】快速排序的非递归实现方法

void QuickSortNonR(Sdatatype* arr, int left, int right)
{
	ST st;
	Stackinit(&st);
	
	Stackpush(&st, right);
	Stackpush(&st, left);
	while (!Stackempty(&st))   //栈为空时就结束循环
	{
		int begin = Stacktop(&st);   //出一个就要pop掉一个数据
		Stackpop(&st);
		int end = Stacktop(&st);
		Stackpop(&st);
		int keyi = begin;    //以下为快速排序的逻辑，这里用的是前后指针法实现
		int mid = GetMid(arr, begin, end);
		if (mid != keyi)
			Swap(&arr[mid], &arr[keyi]);
		int prev = begin, cur = begin + 1;
		while (cur <= end)
		{
			if (arr[cur] < arr[keyi])
			{
				prev++;
				Swap(&arr[cur], &arr[prev]);
				cur++;
			}
			else
				cur++;
		}
		Swap(&arr[keyi], &arr[prev]);
		keyi = prev;   
		if (keyi + 1 < end)    //不要忘记判断
		{
			Stackpush(&st, end);    //这里是先入的右区间，所以是先排序左区间
			Stackpush(&st, keyi + 1);
		}
		if (keyi - 1 > begin)
		{
			Stackpush(&st, keyi - 1);
			Stackpush(&st, begin);
		}
	}

	Stackdestroy(&st);   //销毁栈
}