一、题目描述
设A[1…n]是一个包含n个不同数的数组。如果在i<j的情况下，有A[i]>A[j]，则称（i,
j）为A中的一个逆序对。 例如，A=（2, 3，8, 6, 1）的逆序对有 21 31 81 86 61 共5个。
二、分析
1.读题 2.分析输入样例 3.思考数据类型 4.考虑时间复杂度 5.写程序
可使用冒泡和归并。冒泡时间复杂度O(n^2)~10 ^4 >10 ^5 舍弃，使用归并解决
2.归并排序模板
代码如下（示例）
class Solution { static int count= 0;//逆序对的个数 void start(int [] a, int left,int right) { int n = a.length-1; int tempArr [] = new int [n]; mergeSort(a,tempArr,left,right); } void mergeSort(int a[],int tempArr[], int left, int right) { if(left < right) { int mid = (left+right) / 2; mergeSort(a,tempArr,left,mid); mergeSort(a,tempArr,mid+1,right); merge_together(a, tempArr,left, right,mid); } } void merge_together(int a[],int tempArr[] , int left,int right,int mid) { int l = left;//左指针 int m = mid+1;//右半边数组指针 int k = left; //；临时数组第一个元素表示 while(l<=mid && m<=right) { if(a[l]<a[m]) { tempArr[k++] = a[l++]; }else { tempArr[k++] = a[m++]; **count+=(mid-l)+1;**//**此条即可求出逆序对个数，去掉此条，即为归并模板** } } while(l<=mid) { tempArr[k++] = a[left++]; } while(m<=right) { tempArr[k++] = a[right++]; } while (left <= right) { a[left] = tempArr[left]; left++; } } }
3.代码理解
按照题目求逆序对，只需要在合并时添加count= (mid-l)+1即可。
模板分为进入 分组 合并 三部分，
在分组这一块中，用到了递归，递归讲究的是先递后归，即将整体分为左右，对左递，对右递，最后分为单个为一体的有序数组时停止，开始返回上一层运算。
在合并这一块中，对于所求逆序对为啥是count=mid-l+1，可以这样理解，经过分组后，未经合并前左右都是有序的，如果左边第一个数大于右边第一个数，即左边到分割线的数都大于右边第一个数，然后再执行对右边剩余的数放入临时数组。
如有错误，请及时指出，感谢观看！
