Ultra-QuickSort 求逆序对归并排序

Problem Description

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

5 9 1 0 5 4 3 1 2 3 0

Sample Output

）））））））））））））））））））））））））））））））））））））））））））））））））））））））））））））））））））））））））））））））

求逆序对归并排序

***************************************************************************************************************************

 1 #include<iostream>
 2 #include<string>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstdio>
 6 #include<queue>
 7 using namespace std;
 8 int a[500001],c[500001];
 9 int n,i,j,k;
10 long long sum;
11 void merge(int le,int m,int ri)//归并
12 {
13     int it,jt;
14     int p=0;
15     it=le,jt=m+1;
16     while(it<=m&&jt<=ri)
17     {
18         if(a[it]>a[jt])
19         {
20             c[p++]=a[jt++];
21             sum+=m-it+1;
22         }
23         else
24         {
25             c[p++]=a[it++];
26         }
27     }
28     while(it<=m) c[p++]=a[it++];
29     while(jt<=ri) c[p++]=a[jt++];
30     for(it=0;it<p;it++)
31     {
32         a[le+it]=c[it];
33     }
34 }
35 void mergesort(int le,int ri)//二分
36 {
37     if(le<ri)
38    {
39     int mid=(le+ri)>>1;
40     mergesort(le,mid);
41     mergesort(mid+1,ri);
42     merge(le,mid,ri);
43    }
44 }
45 int main()
46 {
47     while(scanf("%d",&n)&&n)
48     {
49         for(i=0;i<n;i++)
50          scanf("%d",&a[i]);
51         sum=0;
52         mergesort(0,n-1);
53         printf("%lld
",sum);
54     }
55     return 0;
56 }

View Code

Ultra-QuickSort 求逆序对 归并排序

Ultra-QuickSort 求逆序对归并排序