编写 快速排序的非递归算法

用循环,和一个中间变量.

正好以前写过，现在找出来贴上
#define Maxsize 50000

void quicksort(int a[],int n)
{
int i,j,low,high,temp,top=-1;

struct node
{
int low,high;
} st[Maxsize];

top++;
st[top].low=0;st[top].high=n-1;
while(top>-1)
{
low=st[top].low;high=st[top].high;
top--;
i=low;j=high;
if(low<high)
{
temp=a[low];
while(i!=j)
{
while(i<j&&a[j]>temp)j--;
if(i<j)
{
a[i]=a[j];i++;
}
while(i<j&&a[i]<temp)i++;
if(i<j)
{
a[j]=a[i];j--;
}
}
a[i]=temp;
top++;st[top].low=low;st[top].high=i-1;
top++;st[top].low=i+1;st[top].high=high;
}
}
}

终于编写出来了，我写了两种，你看看：下面是代码：

/*非递归算法1
??递归算法的开销很大，所以在下编了一个非递归的，算法描述如下：
??A non-recursive version of quick sort using stack:
?? There are 2 stacks, namely one which stores the start of
??a subarray and the other which stores the end of the
??subarray.
??STEP 1: while the subarray contains more than one element
??,i.e. from?? Do {
?? SUBSTEP 1. pivot=Partion(subarray);
?? SUBSTEP 2. keep track of the right half of the current
??subarray i.e. push (pivot+1) into stackFrom, push (to) into stackTo
?? SUBSTEP 3. go on to deal with the left half of
??the current subarray i.e. to=pivot-1
?? }
??STEP 2: if(neither of the stacks is empty)
?? Get a new subarray to deal with from the stacks.
?? i.e. start=pop(stackFrom); to=pop(stackTo);
??STEP 3: both stacks are empty, and array has
??been sorted. The program ends.
??
??*/*/
??void UnrecQuicksort(int q[],int low,int high)
??{stack s1;<br/>??stacks2;<br/>?? s1.push(low);<br/>?? s2.push(high);<br/>?? int tl,th,p;<br/>?? while(!s1.empty() && !s2.empty())<br/>?? {tl=s1.top();th=s2.top();<br/>?? s1.pop();s2.pop();<br/>?? if(tl>=th) continue;<br/>?? p=partition(q,tl,th);<br/>?? s1.push(tl);s1.push(p+1);<br/>?? s2.push(p-1);s2.push(th);<br/>?? }
??}
??
??/*非递归算法2
??要把递归算法改写成非递归算法，可引进一个栈，这个栈的大小取决于递归调用的深度，最
??多不会超过n，如果每次都选较大的部分进栈，处理较短的部分，递归深度最多不超过log2n
??，也就是说快速排序需要的附加存储开销为O（log2n）。
??*/
??void UnrecQuicksort2(int q[],int low,int high)
??{int *a;<br/>?? int top=0,i,j,p;<br/>?? a=new int[high-low+1];<br/>?? if(a==NULL) return;<br/>?? a[top++]=low;<br/>?? a[top++]=high;<br/>?? while(top>0)<br/>?? {i=a[--top];<br/>?? j=a[--top];<br/>?? while(j?? {p=partition(q,j,i);<br/>?? if(p-j?? {//先分割前部,后部进栈<br/>??a[top++]=p+1;<br/>?? a[top++]=i;<br/>?? i=p-1;<br/>?? }
?? else
?? {//先分割后部,前部进栈
??a[top++]=j;
?? a[top++]=p-1;
?? j=p+1;
?? }
?? }
?? }
??}
??
??/*打印输出*/
??void display(int p[],int len)
??{for(int i=0;i?? cout<??}
??
??
??/*测试*/
??int _tmain(int argc, _TCHAR* argv[])
??{int a[]={49,65,97,12,23,41,56,14};
??quicksort(a,0,7);
??//UnrecQuicksort(a,0,7);
?? //UnrecQuicksort2(a,0,7);
??display(a,8);
??return 0;
??}
??

-------------------------

quicksort没有必要费递归的吧