把快速排序递归算法改成非递归

Question

数组a为线形表内的数据
void qkOne(int a[],int m,int n)//m为起始位置，n为终止位置
{ int x,i,j;
i=m;
j=n;
x=a[i];//将第一个值保存在x中,做基准值。
while(i!=j)
{
while(i<j && a[j]>=x)
; /*自右向左扫描*/
if(i<j)
{
;
i++;
}
while(i<j&&a[i]<=x)
i++; /*自左向右扫描*/
if(i<j)
{ a[j]=a[i];
;
}
}
;
if(m<i) qkOne(a,m,i-1);
if(i<n) qkOne(a,i+1,n);

}

Answer 1

可以用栈把那些要排的东西记下来如，起始位置，结束位置，基准位置，再一个一个的排，直到栈为空
／／还有很多没有写你自己去填上
struct qq{
int frist;
int last;
}QQ[MAXSIZE];

int a[max];
struct qq dd,ff;
while(!empty(QQ)){
dd=pop(QQ);//不为空就出栈

qkOne(a[],dd->frist,dd->last);//把这一部分排好；

if(dd->frist<i){ ff->frist=dd-frist;ff->last=i-1;push(ff,QQ);}//这里改为入栈就可以了，下同
if(i<dd->last){ff->frist=i+1;ff->last=dd->last;push(ff,QQ);}
｝
}

void qkOne(int a[],int frist,int last)；//frist为起始位置，last为终止位置
{ int x,i,j;
i=frist;
j=last;
x=a[i];//将第一个值保存在x中,做基准值。
while(i!=j)
{
while(i<j && a[j]>=x)
; /*自右向左扫描*/
if(i<j)
{
;
i++;
}
while(i<j&&a[i]<=x)
i++; /*自左向右扫描*/
if(i<j)
{ a[j]=a[i];
;
}
}
;本回答被提问者采纳