计算逆序数对

python语言：

#-*- coding:utf-8 -*-
#import pdb

def sort_count(data):
    """
    using merge sort and count inversion
    """
    global count
    count = 0
    def merge_sort(data):
        global count 
        if len(data)<2:
            return data
        
        left = merge_sort(data[:(len(data)//2)])
        right = merge_sort(data[(len(data)//2):])
        idx_left = idx_right = 0
        result = []
        while idx_left < len(left) and idx_right < len(right):
            if left[idx_left] <= right[idx_right]:
                result.append(left[idx_left])
                idx_left += 1
            else:
                result.append(right[idx_right])
                idx_right += 1
                count += len(left)-idx_left
        while idx_left < len(left):
            result.append(left[idx_left])
            idx_left += 1

        while idx_right < len(right):
            result.append(right[idx_right])
            idx_right += 1
        return result
    
    sorted_data = merge_sort(data)

    
    return count
        
        
class Ivrs_num(object):
    def __init__(self, filename):
        self.count = 0
        self.filename = filename
        
    def inverse_count(self):
        data = self.load_txt()
        def merge_sort(data):
        
            if len(data)<2:
                return data
        
            left = merge_sort(data[:(len(data)//2)])
            right = merge_sort(data[(len(data)//2):])
            idx_left = idx_right = 0
            result = []
            while idx_left < len(left) and idx_right < len(right):
                if left[idx_left] <= right[idx_right]:
                    result.append(left[idx_left])
                    idx_left += 1
                else:
                    result.append(right[idx_right])
                    idx_right += 1
                    self.count += len(left)-idx_left
            while idx_left < len(left):
                result.append(left[idx_left])
                idx_left += 1

            while idx_right < len(right):
                result.append(right[idx_right])
                idx_right += 1
            return result
        merge_sort(data)
        return self.count
        
    def load_txt(self):
        int_list = []
        with open(self.filename) as f:
            for line in f:
                int_list.append(int(line))
        return int_list
        

    
    


if __name__ == '__main__':

    m = Ivrs_num('IntegerArray.txt')
   
    print(m.inverse_count())
        

#include <iostream>

//Inversion Pair

int merge_sort(int a[], int len)
{
	if(len<2) return 0;
	int left[len/2],right[len-len/2];
	int i,j,index,inver=0;
	for(i=0;i<len/2;i++)
	{
		left[i]=a[i];
	}
	for(i=len/2,j=0;i<len;i++,j++)
	{
		right[j]=a[i];
	}
	inver += merge_sort(left, len/2);
	inver += merge_sort(right, len-len/2);
	index=0;
	i=0;
	j=0;
	while(i<len/2 && j<(len-len/2))
	{
		if(left[i] <= right[j])
		{
			a[index]=left[i];
			index++;
			i++;
		}
		else
		{
			a[index]=right[j];
			j++;
			index++;
			inver += len/2 - i;
		}
	}
	while(i<len/2)
	{
		a[index]=left[i];
		index++;
		i++;	
	}
	while(j<(len-len/2))
	{
		a[index]=right[j];
		index++;
		j++;
	}
	return inver;
}


int main()
{
	int len;
	std::cin>>len;
	int array[len],i;
	for(i=0;i<len;i++)
	{
		std::cin>>array[i];
	}
	
	std::cout<<merge_sort(array,len);
	/*
	int array[]={4,2,6,1,5,3,0};
	int count=0;
	std::cout<<merge_sort(array,7)<<std::endl;
	int i=0;
	for(i=0;i<7;i++)
	{
		std::cout<<array[i]<<" ";
	}
	*/
	return 0;
}