分治法求逆序对数目
（题目出自算法导论第二章思考题2-4）
设A[1..n]是一个包含n个不同整数的数组。如果在i<j的情况下，有A[i]>A[j]，则(i,j)就称为A中的一个逆序对（inversion）。
给出一个算法，确定n个元素的任何排列中逆序对的书目。时间复杂度为o(nlgn)。
分治法求解：将数组A[1..n]分为两个子序列A[1..p]和A[p+1,n]，子序列的数目等于A[1..p]和A[p+1,n]中逆序对数目之和，加上这两个子序列合并后的逆序对。根据合并排序的思想，在合并过程中，计算逆序对。假如两个子序列为X={4,5}和Y={2,3}，则XY的逆序对为X中元素大于Y中元素的数目。
#include <iostream>using namespace std;/********************************************功能：求arr[]逆序对数输入：arr，iLow，iMid,iHigh。子序列为arr[iLow..iMid],arr[iMid+1,iHigh]输出:iCount 逆序对的数目。*********************************************/void MergeCount(int* arr,int iLow,int iMid,int iHigh,int& iCount){ if (NULL == arr) { return; } int lLen = iMid - iLow + 1; int hLen = iHigh - iMid; int *lArray = new int[lLen];//未对lArray，hArray进行NULL判断 int *hArray = new int[hLen]; int i = 0; int j = 0; int k = 0; for (;i < lLen; ++i) { lArray[i] = arr[iLow + i]; } for (;j < hLen; ++j) { hArray[j] = arr[iMid + 1 + j]; } i = 0; j = 0; for (k = iLow; i < lLen && j < hLen; ++k) { if (lArray[i] > hArray[j]) { arr[k] = hArray[j++]; iCount += lLen -i; } else { arr[k] = lArray[i++]; } } delete[] lArray; delete[] hArray;}/********************************************功能：求逆序对数输入：arr，iLow，iHigh。数组序列为arr[iLow..iHigh]输出:iCount 逆序对的数目。此处增加参数iCount,使用尾递归返回逆序对*********************************************/void InversionCount(int* arr,int iLow,int iHigh,int& iCount){ int iMid = 0; if (iLow < iHigh) { iMid = iLow + ((iHigh - iLow)>>1); InversionCount(arr,iLow,iMid,iCount); InversionCount(arr,iMid +1,iHigh,iCount); MergeCount(arr,iLow,iMid,iHigh,iCount); }}int main(int argc,char* argv[]){ int arr[] = {5,15,3,2,4}; int sum = 0; InversionCount(arr,0,4,sum); cout << sum << endl; return 0;}