登录
  • #刷题
  • #二分/排序/搜索

分享快排的非递归实现

e6175423
1552
4
前几天面试被问到快排的非递归实现了,方法是用栈实现,但实现还是比较繁琐。

#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;

while ( i<j )

{ while ( i < j && r[j] >= rp ) j--;

r = r[j];

while ( i < j && r <= rp) i++;

r[j] = r;

}

r = 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);

printf("\n");

}
4条回复
热度排序

发表回复