首页 > 代码库 > 快速排序
快速排序
快速排序
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 6 void qs(int *f,int l,int r) 7 { 8 if(l>=r) 9 return ; 10 int k=f[l]; 11 int ll=l,rr=r; 12 while(ll<rr) 13 { 14 while(ll<rr&&f[rr]>=k) 15 rr--; 16 f[ll]=f[rr]; 17 while(ll<rr&&f[ll]<=k) 18 ll++; 19 f[rr]=f[ll]; 20 } 21 f[ll]=k; 22 qs(f,l,ll-1); 23 qs(f,ll+1,r); 24 } 25 26 int main() 27 { 28 int n; 29 while(scanf("%d",&n)!=EOF) 30 { 31 int i; 32 int f[100010]; 33 for(i=1;i<=n;i++) 34 scanf("%d",f+i); 35 qs(f,1,n); 36 for(i=1;i<n;i++) 37 { 38 printf("%d ",f[i]); 39 } 40 printf("%d\n",f[n]); 41 } 42 return 0; 43 }
统计快速排序的交换次数
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 6 int count; 7 void qs(int *f,int l,int r) 8 { 9 if(l>=r) 10 return ; 11 int k=f[l]; 12 int ll=l,rr=r; 13 while(ll<rr) 14 { 15 while(ll<rr&&f[rr]>=k) 16 rr--; 17 f[ll]=f[rr]; 18 if(ll!=rr) 19 count++; 20 while(ll<rr&&f[ll]<=k) 21 ll++; 22 f[rr]=f[ll]; 23 if(ll!=rr) 24 count++; 25 } 26 f[ll]=k; 27 qs(f,l,ll-1); 28 qs(f,ll+1,r); 29 } 30 31 int main() 32 { 33 int n; 34 while(scanf("%d",&n)!=EOF) 35 { 36 int i; 37 int f[100010]; 38 for(i=1;i<=n;i++) 39 scanf("%d",f+i); 40 count=0; 41 qs(f,1,n); 42 for(i=1;i<n;i++) 43 { 44 printf("%d ",f[i]); 45 } 46 printf("%d\n",f[n]); 47 printf("%d\n",count); 48 } 49 return 0; 50 }
快速排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。