最近在学数据结构，看的那本很垃圾的《数据结构及其应用》，奥赛辅导书。全数都是pascal我就不说了，还好多错误，编排也不合理。讲线性结构的应用竟然出了个用二叉排序树、堆及散列表的例题。
像我这种弱菜也就用用数组吧。学了这么长时间数据结构也不能没点成果吧。于是今天晚上跑到微机室来写了个用栈结构实现的非递归快排。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#define S_MAX 1000//栈深度1000 struct stack{ int top; int tl[S_MAX]; int tr[S_MAX]; } s; void nrqsort(int a[], int l, int r) { int tl=l,tr=r,m=a[(tl+tr)/2],t; s.top=1; s.tl[s.top]=tl; s.tr[s.top]=tr; do{ l=tl=s.tl[s.top]; r=tr=s.tr[s.top]; s.top--; m=a[(tl+tr)/2]; while(tl<tr){ while(a[tl]<m) tl++; while(a[tr]>m) tr--; if(tl<=tr) {t=a[tl]; a[tl]=a[tr]; a[tr]=t; tl++; tr--;} } if(tl<r) {s.top++;s.tl[s.top]=tl; s.tr[s.top]=r;} if(tr>l) {s.top++;s.tl[s.top]=l; s.tr[s.top]=tr;} } while(s.top>0); } |