分治算法——逆序对计数问题

• 案例
• 伪代码
• C语言实现

输入：数组A和下标low,mid,high
输出：非递减数组A[low...high] 及 该区间内的逆序对数量
FindCrossingNum(A,low,mid,high)    //A[low...mid]和A[mid+1...high]均有序
k = 0
num = 0
i = low
j = mid+1
while i<=mid && j<=high
	if A[i]<= A[j]
		res[k] = A[i]
		i = i+1
		k = k+1
	else
		num = num + (mid-i+1)
		res[k] = A[j]
		k = k+1
		j = j+1
A[low...low+k] = res[0...k]     //该函数执行完之后该子数组会发生改变
return num

输入：数组A和下标low,high
输出：A[low...high]中逆序对的个数
FindNum(A, low, high)
if low==high     //递归出口
	num=0
	return num
else
	mid = (low+high)/2     //下取整
    left_num = FindNum(A, low, mid)
    right_num = FindNum(A, mid+1, high)
    cross_num = FindCrossingNum(A, low, mid, high)
    num = left_num + right_num + cross_num
    return num

算法时间复杂度分析：O(nlogn)
空间复杂度：O(n)

#include 
#include 

//函数声明
int FindCrossingNum(int *A, int low, int mid, int high);
int FindNum(int* A, int low, int high);    //求A[low...high]中逆序对的个数

int main()
{
    int A[12] = {13, 8, 10, 6, 15, 18, 12, 20, 9, 14, 17, 19};
    int num = FindNum(A, 0, 11);
    printf("%dn",num);
    return 0;
}

int FindCrossingNum(int* A, int low, int mid, int high){   //A[low...mid] 和 A[mid+1...high]均有序
    int i, j, k=0, num=0;
    int A_length = 12;
    int *res = (int*)malloc(A_length * sizeof(int));
    if(!res) return 0;

    i = low;
    j = mid + 1;
    while(i<=mid && j<=high){
        if(A[i] <= A[j]){
            res[k++] = A[i++];
        } else {
            num += (mid-i+1);
            res[k++] = A[j++];
        }
    }
    for(i=0; i 
程序运行结果：