經典算法——數組中的逆序對

經典算法——數組中的逆序對

一、題目描述

在數組中的兩個數字，如果前面一個數字大於後面的數字，則這兩個數字組成一個逆序對。輸入一個數組，求出這個數組中的逆序對的總數。

二、解題方法

class Solution {
public:
    int InversePairs(vector data) {
        int n=data.size();
        return process(data,0,n-1);
    }
    
    int process(vector& data,int start,int end)
    {
        //遞歸終止條件
        if(start>=end)
        {
            return 0;
        }
        
        // 歸並排序，並計算本次逆序對數
	    vector copy(data); // 數組副本，用於歸並排序
        int mid=(start+end)/2;
        int left=process(data,start,mid);
        int right=process(data,mid+1,end);
        
        int p=mid;//p初始化為前半段最後一個數字的下標
        int q=end;//q初始化為後半段最後一個數字的下標
        int index=end;//輔助數組的下標初始化為最後一位
        int count=0;//記錄逆序對的個數
        
        while(p>=start && q>=mid+1)
        {
            if(data[p]>data[q])
            {
                copy[index--]=data[p--];
                count+=q-mid;
            }
            else
            {
                copy[index--]=data[q--];
            }
        }
        
        while(p>=start)   copy[index--]=data[p--];
        while(q>=mid+1)   copy[index--]=data[q--];
        	
        for (int i = start; i <= end; i++)
        {
			data[i] = copy[i];//更新歸並排序後的子數組
	    }

        return (left+right+count);
    }
};