Poj 2299 Ultra-QuickSort(归并排序求逆序数)

一、题意

给定数组，求交换几次相邻元素能是数组有序。

二、题解

刚开始以为是水题，心想这不就是简单的冒泡排序么。但是毫无疑问地超时了，因为题目中n<500000,而冒泡排序总的平均时间复杂度为，显然不满足要求。还有就是数组中的元素0 ≤ a[i] ≤ 999,999,999，要用long long或_int64,在java中要用long。再一想用最快的快速排序，发现也不行。快排基于二分查找，交换次数很定要比题目要求的少。在想就是归并排序了，我们可以用归并排序求数组的逆序数。逆序数就等于冒泡排序的交换次数。

三、java代码

//Memory 9068K
//Time 2766MS
import java.util.Scanner;

public class Main {
	static int  MAX =500010;
	static int [] a=new int[MAX];  
	static int[] tb=new int[MAX/2];
	static int [] te=new int[MAX/2];
	static long sum;
	private static void Merge(int[] a ,int beg,int mid,int end) {
        int k;
        int n1=mid-beg+1;
        int n2=end-mid;
		int i = 0, j = 0;
        for(k=beg;k<=mid;k++){
        	tb[i++]=a[k];
        }
        tb[n1]=Integer.MAX_VALUE;
        for(k=mid+1;k<=end;k++){
        	te[j++]=a[k];
        }
        te[n2]=Integer.MAX_VALUE;
        i = j = 0;  
        
        for(k=beg; k<=end; k++)  
            if( tb[i] <= te[j] )  
                a[k] = tb[i++];  
            else{  
                sum += ( n1 - i );  
                a[k] = te[j++];  
            }  
    }
	
	 private static void  MergeSort(int[] a,int beg,int end) {
		 	if(beg<end){
		 		int mid =(end+beg)/2;
		 	    MergeSort(a,beg,mid);
		 	    MergeSort(a,mid+1,end);
		 	    Merge(a,beg,mid,end);
		 	}
	    }
	    
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n,i;
		while((n=sc.nextInt())!=0){
			sum=0;
			for(i=0;i<n;i++){
				a[i]=sc.nextInt();
			}
			MergeSort(a,0,n-1);
			System.out.println(sum);
		}
	}
}