Ultra-QuickSort （poj 2002)

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

Sample Output

6
0

这题很简单的样子，就是求冒泡排序的交换次数，but 超时

归并排序，求逆序数，别问我是什么？看着模板写就好

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 int s[500005],temp[500005];
 6 long long cut;//这里害我WA了一次
 7 void merge_sort(int* A,int x,int y,int* T )
 8 {
 9     if(y-x>1)
10     {
11         int m=x+(y-x)/2;//划分
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         {
17             if(q>=y||(p<m&&A[p]<=A[q]))
18                 T[i++]=A[p++];//从左半数组复制到临时空间
19             else
20             {
21                 T[i++]=A[q++];//从右半数组复制到临时空间
22                 cut+= (m-p);//统计逆序数
23             }
24         }
25         for(i=x; i<y; i++)
26             A[i]=T[i];//从辅助数组复制回原数组
27     }
28 }
29 int main()
30 {
31     int n,i;
32     while(scanf("%d",&n)&&n)
33     {
34         cut=0;
35         for(i=0; i<n; i++)
36             scanf("%d",&s[i]);
37         merge_sort(s,0,n,temp);
38         printf("%lld
",cut);
39     }
40     return 0;
41 }

View Code

 1 #include<iostream>
 2 using namespace std;
 3 long long  cnt;
 4 void merge(int array[],int left,int mid,int right)
 5 {
 6     int* temp=new int[right-left+1];
 7     int i,j,p;
 8     for(i=left,j=mid+1,p=0; i<=mid&&j<=right; p++)
 9     {
10         if(array[i]<=array[j])temp[p]=array[i++];
11         else temp[p]=array[j++],cnt+=(mid-i+1);
12     }
13     while(i<=mid)temp[p++]=array[i++];
14     while(j<=right)temp[p++]=array[j++];
15     for(i=left,p=0; i<=right; i++)array[i]=temp[p++];
16     delete temp;
17 }
18 void mergesort(int array[],int left,int right)
19 {
20     if(left==right)array[left]=array[right];
21     else
22     {
23         int mid=(left+right)/2;
24         mergesort(array,left,mid);
25         mergesort(array,mid+1,right);
26         merge(array,left,mid,right);
27     }
28 }
29 int main()
30 {
31     int n,array[500005];
32     while(cin>>n&&n)
33     {
34         cnt=0;
35         for(int i=0; i<n; i++)
36             cin>>array[i];
37         mergesort(array,0,n-1);
38         cout<<cnt<<endl;
39     }
40     return 0;
41 }

View Code

下面这个是网上找的还算好懂得，耗时是我敲得那个的10倍左右