快速排序

 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
",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
",f[n]);
47         printf("%d
",count);
48     }
49     return 0;
50 }