快排的递归和非递归
常用的快排都是用递归写的,因为比较简单,但是可以用栈来实现非递归的快排。
竹溪ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为创新互联建站的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:028-86922220(备注:SSL证书合作)期待与您的合作!
第一种是递归的快排
#include#include #include int quick(int a[],int i ,int j) { int tmp=0,key,b=0; int im,jm; im=i; jm=j; key=a[i]; if(i>j) return ; while(i < j){ while(a[j] > key && i< j) j--; a[i]=a[j]; while(a[i] <= key && i < j) i++; a[j]=a[i]; } //这块和非递归是不同的,这里用的是覆盖。 a[i]=key; quick(a,im,i-1); quick(a,i+1,jm); return 0; } int *rand_list(int *nums, int len, int range) //产生随机数 { srand(time(NULL)); int i = 0; for(i = 0; i< len; i++) nums[i] = rand()%range; return nums; } int main() { int a[100]; rand_list(a,100,100); int i=0; quick(a,0,99); for(i=0;i<100;i++) printf("%d ",a[i]); printf("\n"); }
第二种是非递归
#include#define max 20 int sl[max]; int sr[max]; int top =0; void push(int a, int b) { sl[top] = a; sr[top] = b; top++; } void pop(int* p1, int* p2) { top--; *p1 = sl[top]; *p2 = sr[top]; } void quick(int* a ,int l,int r) { int al,ar,point,tmp; push(l,r); while(top){ pop(&l,&r); al = l; ar = r; point = a[(al+ar)/2]; while(al point && al < ar) ar--; if(al <= ar){ tmp = a[al]; a[al] = a[ar]; a[ar] = tmp; al++; ar--; } } if(l < ar) //这块和递归是不同的,要注意,这里用的是相互交换 push(l,ar); if(al < r) push(al,r); } } int main() { int a[10] ={2,4,1,8,3,5,9,7,6,0}; quick(a,0,9); int i; for(i=0;i<10;i++) printf("%d ",a[i]); printf("\n"); return 0; }
文章名称:快排的递归和非递归
URL地址:http://myzitong.com/article/jgijdg.html