注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
前几天面试被问到快排的非递归实现了,方法是用栈实现,但实现还是比较繁琐。
#include "stdio.h"
#define N 8
int r[N+1] = { 0,49,38,65,97,76,13,27,49 };
void QuickSort(int *r, int n)
{ int i,j,rp,top;
struct
{ int left;
int right;
} stack[100],x,y;
x.left=1; x.right=n; top=1; stack[top]=x;
while(top>0)
{
x=stack[top--];
i=x.left; j=x.right; rp=r[i];
while ( i<j )
{ while ( i < j && r[j] >= rp ) j--;
r[i] = r[j];
while ( i < j && r[i] <= rp) i++;
r[j] = r[i];
}
r[i] = rp;
if ( i < x.right-1) { y.left =i+1; y.right=x.right; stack[++top]=y; }
if ( i > x.left+1) { y.right=i-1; y.left =x.left; stack[++top]=y; }
}
}
void main()
{ int i;
QuickSort(r,8);
for(i=1;i<=8;i++) printf("%d ",r[i]);
printf("\n");
}
|