逆序数

分析

逆序数的意义：就是选择排序中对元素交换的次数。
普通的比较时间复杂度都是O(N^2)，肯定是不能通过的。
需要一种O(NlgN)的排序算法

利用归并排序

import java.io.*;
import java.util.*;

public class modp {
    public static int sum =0;
    public static int a[] = new int[50010];
    public static int b[] = new int[50010];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = 0;
        n = in.nextInt();
        for(int i=0;i<n;i++) {
            a[i] = in.nextInt();
        }
        merge_sort(0, n-1);
        out.println();
        out.flush();
    }
    public static void merge_sort(int low, int high) {
        if(low >= high)
            return ;
        int mid = (low + high) / 2;
        merge_sort(low, mid);
        merge_sort(mid+1, high);
        merge(low, mid, high);
    }
    public static void merge(int low, int mid, int high) {
        int i = low;
        int j = mid+1;
        for(int k=low;k<=high;k++) {
            b[k] = a[k];
        }
        for(int k=low;k<=high;k++) {
            if(i > mid)
                b[k] = a[j++];
            else if(j > high)
                b[k] = a[i++];
            
            else if(a[i] <= a[j])
                b[k] = a[i++];
            else {
                b[k] = a[j++];
                sum += mid-i+1;  //from i to mid,all numbers are bigger than j.
            }
        }
        for(int k=low;k<=high;k++) {  //error1:忘记对原数组重新赋值
            a[k] = b[k];
        }
    }
}
/*
4
2
4
3
1 
 */

代码的效率还是不高