您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
常用的快排都是用递归写的,因为比较简单,但是可以用栈来实现非递归的快排。
第一种是递归的快排
#include<stdio.h> #include <stdlib.h> #include <time.h> 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<stdio.h> #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<ar){ while(a[al] < point && al < ar) al++; while(a[ar] > 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; }
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。