Java 求数组逆序对的个数 时间复杂度 NlogN，逆序nlogn,逆序对：设a是一个有n个

Java 求数组逆序对的个数 时间复杂度 NlogN，逆序nlogn,逆序对：设a是一个有n个

逆序对：设a是一个有n个不同元素的数组，，如果在i<j的情况下，a[i]>a[j]，则(i, j)称为a的一个逆序对。

给定一个数组，求逆序对的个数，可以通过做循环，在n^2的时间内求出逆序对数目，但通常用归并排序在nlog(n)的时间内解决，只是当求出逆序对数目后，数组也已经排好序了，如果不想让原数组发生变化，可以把原数组拷贝到另一个数组，对新数组操作就好。整个过程一边排序一边数，递归到最深的地方如果有一个数，那么返回0，如果有两个数，看做有两个元素的子数组，两个子数组都已经排好序，并且左边只有一个元素的子数组的逆序对是0，右边只有一个元素的子数组的逆序对是0，那么两个元素的子数组的逆序对的个数就是1,若这两个数逆序，否则是0对。所以，当递归进行到最后一步，也就是这样的：a[1]到a[n/2]已经排好序，并且逆序对的个数为Inv1，a[n/2+1]到a[n]已经排好序，并且逆序对的个数为Inv2，那么整个数组的逆序对总数就是Inv1+Inv2+最后一步归并过程中的逆序对数。那么在merge这一步的逆序对个数又是怎么计算的呢？若i是左边子数组的下标（i的范围是1到mid），j是右边子数组的下标（j的范围是mid+1到n），假设某对(i,j)，有a[i]>a[j]，那么a[i]到a[mid]都大于a[j]，贡献的逆序对数为mid-i+1。

import java.io.BufferedReader;import java.io.File;import java.io.FileReader;import java.io.IOException;import java.util.ArrayList;public class IntegerArray {    private ArrayList<Integer> assignList(ArrayList<Integer> list, int start,            int end) {        ArrayList<Integer> des = new ArrayList<Integer>();        for (int i = start; i < end; i++) {            des.add(list.get(i));        }        return des;    }    public long mergerTwoList(ArrayList<Integer> list, int start, int half,            int end) {        long count = 0;        ArrayList<Integer> tempLeft = assignList(list, start, half);        ArrayList<Integer> tempRight = assignList(list, half, end);        int leftIndex = 0;        int rightIndex = 0;        int index = start;        while (leftIndex < tempLeft.size() && rightIndex < tempRight.size()) {            int temp1 = tempLeft.get(leftIndex);            int temp2 = tempRight.get(rightIndex);            if (temp1 > temp2) {                count += tempLeft.size() - leftIndex;                list.set(index, temp2);                index++;                rightIndex++;            } else {                list.set(index, temp1);                index++;                leftIndex++;            }        }        for (; leftIndex < tempLeft.size(); leftIndex++) {            list.set(index, tempLeft.get(leftIndex));            index++;        }        for (; rightIndex < tempRight.size(); rightIndex++) {            list.set(index, tempRight.get(rightIndex));            index++;        }        return count;    }    public long getInversions(ArrayList<Integer> list, int start, int end) {        long count = 0;        if ((end - start) <= 1)            return 0;        int half = start + (end - start) / 2;        count += getInversions(list, start, half);        count += getInversions(list, half, end);        count += mergerTwoList(list, start, half, end);        return count;    }    /**     * @param args     */    public static void main(String[] args) {        // TODO Auto-generated method stub        try {            BufferedReader br = new BufferedReader(new FileReader(new File(                    "IntegerArray.txt")));            String line;            ArrayList<Integer> list = new ArrayList<Integer>();            Integer temp;            while ((line = br.readLine()) != null) {                temp = Integer.parseInt(line);                list.add(temp);            }            System.out.println("list size" + list.size());            int i, j;            int size = list.size();            long sum = 0;            int tempFirst;            int tempSecond;            long startTime = System.currentTimeMillis();            for (i = 0; i < size - 1; i++) {                tempFirst = list.get(i);                for (j = i + 1; j < size; j++) {                    tempSecond = list.get(j);                    if (tempFirst > tempSecond)                        sum++;                }            }            long endTime = System.currentTimeMillis();            // Inversions Force:2407905288 time:143172            // Inversions Second:2407905288 time:277            System.out.println("Inversions Force:" + sum + " time:"                    + (endTime - startTime));            startTime = System.currentTimeMillis();            IntegerArray ia = new IntegerArray();            sum = ia.getInversions(list, 0, list.size());            endTime = System.currentTimeMillis();            System.out.println("Inversions Second:" + sum + " time:"                    + (endTime - startTime));        } catch (IOException e) {            // TODO Auto-generated catch block            e.printStackTrace();        }    }}//该片段来自于http://byrx.net