归并排序之数组的逆序对

小灰灰 2022-08-04 10:41 182阅读 0赞

题意：求出给定的数组中的逆序对的数量，可使用归并排序求解。

import java.util.* ;
    public class Solution {
        
        public int InversePairs(int [] array) {
            if(array.length == 0) {
                return 0 ;
            }
            return mergeInverse(0, array.length - 1, array, 0) ;
        }
        
        public int mergeInverse(int first, int last, int [] array, int iCount) {
        	if(first < last) {
                int mid = first + (last - first) / 2 ;
                int iCount1 = mergeInverse(first, mid, array, iCount) ;
                int iCount2 = mergeInverse(mid+1, last, array, iCount) ;
                
                return mergeArray(first, mid, last, array, iCount1 + iCount2) ;
            }
            return iCount ;
        }
        
        public int mergeArray(int first, int mid, int last, int[] array, int iCount) {
            List<Integer> tmp = new ArrayList<Integer>() ;
            int i = first, m = mid ;
            int j = mid + 1, n = last ;
            
            while(i <= m && j <= n) {
                if(array[i] <= array[j]) {
                    tmp.add(array[i ++]) ;
                } else {
                    for(int k = i; k <= m; k ++) {
                        if(array[k] > array[j]) {
                            iCount ++ ;
                        }
                    }
                    tmp.add(array[j ++]) ;
                }
            }
            
            while(i <= m) {
                tmp.add(array[i ++]) ;
            }
            while(j <= n) {
                tmp.add(array[j ++]) ;
            }
            
            for(i = 0; i < tmp.size(); i ++) {
                array[first + i] = tmp.get(i) ;
            }
            return iCount ;
        }
    }