Ultra-QuickSort POJ

Ultra-QuickSort

题意：给一个数组，问有多少逆序对

归并排序的时候顺带可以计算一下逆序数。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 #define ll long long
 6 const int maxn=500010;
 7 int a[maxn],t[maxn];
 8 ll cnt;
 9 void merge_sort(int* a,int x,int y,int* t){
10     if(x+1<y){
11         int m=x+((y-x)>>1);
12         int p=x,q=m,i=x;
13         merge_sort(a,x,m,t);
14         merge_sort(a,m,y,t);
15         while(p<m||q<y){
16             if(q>=y||p<m&&a[p]<=a[q]) t[i++]=a[p++];
17             else t[i++]=a[q++],cnt+=m-p;
18         }
19         for(int i=x;i<y;i++) a[i]=t[i];
20     }
21 }
22 int main(){
23     int n;
24     while(scanf("%d",&n)&&n){
25         cnt=0;
26         for(int i=0;i<n;i++) scanf("%d",&a[i]);
27         merge_sort(a,0,n,t);
28         printf("%lld
",cnt);
29     }
30 }

View Code

贴一个归并排序和快速排序，跟本题无关~

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 const int maxn=10010;
 6 int a[maxn],t[maxn];
 7 int cnt;
 8 void merge_sort(int* a,int x,int y,int* t){
 9     if(x+1<y){
10         int m=x+((y-x)>>1);
11         int p=x,q=m,i=x;
12         merge_sort(a,x,m,t);
13         merge_sort(a,m,y,t);
14         while(p<m||q<y){
15             if(q>=y||p<m&&a[p]<=a[q]) t[i++]=a[p++];
16             else t[i++]=a[q++],cnt+=m-p;
17         }
18         for(int i=x;i<y;i++) a[i]=t[i];
19     }
20 }
21 
22 void quick_sort(int x,int y){
23     if(y-x>1){
24         int m=x+(y-x)/2;
25         int p=x,q=y;
26         int rt=a[m];
27         while(1){
28             while(a[p++]<rt);
29             while(a[q--]>rt);
30             if(p>=q) break;
31             swap(a[p],a[q]);
32         }
33         a[q]=rt;
34         quick_sort(x,q-1);
35         quick_sort(q+1,y);
36         return ;
37     }
38 }
39 
40 
41 int main(){
42     int n;
43     while(scanf("%d",&n)&&n){
44         cnt=0;
45         for(int i=0;i<n;i++) scanf("%d",&a[i]);
46         printf("原串:
");
47         for(int i=0;i<n;i++) printf("%d ",a[i]);
48         puts("");
49         merge_sort(a,0,n,t);
50         printf("merge_sort:
");
51         for(int i=0;i<n;i++) printf("%d ",a[i]);
52         puts("");
53         printf("quick_sort:
");
54         for(int i=0;i<n;i++) printf("%d ",a[i]);
55         puts("");
56         printf("逆序数为： %d
",cnt);
57     }
58 }

View Code