stackquicksort.cpp

常用算法与数据结构原代码

#define N 10

template <class T>
void StackQuickSort(T elem[],int n)
{
	int i,j,low,high;
	T t;
	int stack[N][2],top;
	top=0;
	stack[0][0]=0;
	stack[0][1]=n-1;
	while (top>=0)
	{
		low=i=stack[top][0];
		high=j=stack[top][1];
		top--;
		t=elem[i];
		while (i<j)
		{
			while (i<j && elem[j]>t) 
				j--;
			if (i<j)
				elem[i++]=elem[j];
			while (i<j && elem[i]<=t)
				i++;
			if (i<j)
				elem[j--]=elem[i];
		}
		elem[i]=t;
		if (i-1>low)
		{
			top++;
			stack[top][0]=low;
			stack[top][1]=i-1;
		}
		if (high>i+1)
		{
			top++;
			stack[top][0]=i+1;
			stack[top][1]=high;
		}		
	}
}