求逆序对的个数

其实就是二路归并排序，排序的同时记录交换次数就行了。
public class ReversalCount {
    private int[] array = null;
    private int[] tempArray = null;
    public ReversalCount(int[] array) {
        this.array = array;
        tempArray = new int[array.length];
    }
    public int calc() {
        return calc(0, array.length - 1);
    }
    private int calc(int l, int r) {
        if (l >= r) { // less than two numbers
            return 0;
        } else if (l + 1 == r) { // two numbers
            return (array[l] <= array[r]) ? 0 : swap(l, r);
        } else { // three or more numbers
            int m = (l + r) / 2;
            return calc(l, m) + calc(m + 1, r) + combine(l, m, r);
        }
    }
    private int combine(int l, int m, int r) {
        for (int idx = l; idx <= r; idx++) {
            tempArray[idx] = array[idx];
        }
        int count = 0, idx = l, lidx, ridx;
        for (lidx = l, ridx = m + 1; lidx <= m && ridx <= r; ) {
            if (tempArray[lidx] > tempArray[ridx]) {
                array[idx++] = tempArray[ridx++];
                count += m - lidx + 1;
            } else {
                array[idx++] = tempArray[lidx++];
            }
        }
        for (; ridx <= r; ++ridx) {
            array[idx++] = tempArray[ridx];
        }
        for (; lidx <= m; ++lidx) {
            array[idx++] = tempArray[lidx];
        }
        return count;
    }
    private int swap(int i, int j) {
        int temp = array;
        array = array[j];
        array[j] = temp;
        return 1;
    }
}
时间复杂度: T(n) = 2 T(n/2) + O(n) --> T(n) = O(n log n)
空间复杂度: S(n) = O(n)

评论

2 楼 yiminghe 2008-10-29  

恩，不错,我也喜欢这种题

1 楼 yiminghe 2008-10-29  

恩，不错,我也喜欢这种题