POJ 2299 Ultra-QuickSort

• 这是个解决分治问题的好题目，来看看
• 题目：给出长度为n的序列，每次只能交换相邻的两个元素，问至少要交换几次才使得该序列为递增序列？ n < 500,000

问题本质？找有多少个逆序数对

image.png

• Java算法实现

package someTest;

import java.io.BufferedInputStream;
import java.util.Scanner;

public class MergeSort {
    static long num=0;
    public static void main(String[] args) {
        Scanner scan=new Scanner(new BufferedInputStream(System.in));
        while(scan.hasNext()) {
            int n=scan.nextInt();
            if(n==0) {
                break;
            }
            num=0;
            int[] data=new int[n];
            for(int i=0;i<n;i++) {
                data[i]=scan.nextInt();
            }
            mergeSort(data,0,n-1);
            System.out.println(num);
        }
    }
    static void mergeSort(int[] array,int left,int right) {
        if(left<right) {
            //分治，分治，先分后治
            int center=(left+right)/2;
            mergeSort(array, left, center);
            mergeSort(array, center+1, right);
            Merge(array,left,center,right);
        }
    }
    static void Merge(int[] array,int left,int center,int right) {
        int[] temp=new int[right-left+1];
        int i=left;
        int j=center+1;
        int k=0;
        //开始治，左侧数组和右侧数组依次比较，按大小顺序依次放入临时数组当中
        while(i<=center&&j<=right) {
            if(array[i]>array[j]) {
                temp[k++]=array[j++];
                //因为是分治，之后只要发现有左侧某个数据比右侧大了，那么左侧其他的数据通通比右侧大
                num+=center-i+1;
            }else {
                temp[k++]=array[i++];
            }
        }
        //将左侧未比较完的数据顺次放入临时数组
        while(i<center) {
            temp[k++]=array[i++];
        }
        //将右侧未比较完的数据顺次放入临时数组
        while(j<=right) {
            temp[k++]=array[j++];
        }
        //将临时数组里按大小顺序排好的数据依次放回原数组
        for(i=left,k=0;i<=right;i++,k++) {
            array[i]=temp[k];
        }
    }
}