算法

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

一、题目描述二、分析

2.归并排序模板3.代码理解

设A[1…n]是一个包含n个不同数的数组。如果在iA[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 舍弃，使用归并解决

代码如下（示例）：

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] 
3.代码理解 
按照题目求逆序对，只需要在合并时添加count= (mid-l)+1即可。
 模板分为进入 分组 合并 三部分，
 在分组这一块中，用到了递归，递归讲究的是先递后归，即将整体分为左右，对左递，对右递，最后分为单个为一体的有序数组时停止，开始返回上一层运算。
 在合并这一块中，对于所求逆序对为啥是count=mid-l+1，可以这样理解，经过分组后，未经合并前左右都是有序的，如果左边第一个数大于右边第一个数，即左边到分割线的数都大于右边第一个数，然后再执行对右边剩余的数放入临时数组。
 
如有错误，请及时指出，感谢观看！