这篇博客记录了分治-归并的几道题目，包括排序数组、逆序对、计算右侧小于当前元素的个数、翻转对这几道题目。

//归并排序
class Solution 
{//创建一个全局变量，这样可以提高效率vector<int> tmp;
public:void _sortArray(vector<int>& nums,int left,int right){if(left >= right) return;//1.选择中间点划分区间int mid = left + (right - left)/2;//[left,mid] [mid+1,right]//2.把左右区间排序_sortArray(nums,left,mid);_sortArray(nums,mid+1,right);//3.合并两个有序数组int p1 = left,p2 = mid+1,i=0;while(p1 <= mid && p2 <= right)tmp[i++] = nums[p1]<=nums[p2]?nums[p1++]:nums[p2++];//4.处理没有遍历的数组while(p1 <= mid) tmp[i++] = nums[p1++];while(p2 <= right) tmp[i++] = nums[p2++];//5.还原for(int i = left ; i <= right ; i++){nums[i] = tmp[i-left];}}vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());_sortArray(nums,0,nums.size()-1);return nums;}};

题目分析：我们可以归并排序，归并排序的思想就是先找一个中间值，然后把其左边区间也归并排序，然后其右边区间也归并排序，然后再把两个排序好的左右两个有序数组合并，合并两个有序数组的思路是双指针，分别指向左右区间的起始，另创建一个空数组，比较这两个指针指向的元素大小，小的放进这个空数组，直到遍历完。

所以，归并排序类似二叉树的后序遍历，而快速排序类似二叉树的前序遍历。

class Solution {int v[50001];
public:int MergeSort(vector<int>& nums,int left,int right){if(left >= right) return 0;//1.找中间点，将数组分成两部分//int mid = left+(right-left)/2;int mid = (left + right) >> 1;//[left,mid] [mid+1,right] 升序int ret = 0;//2.左边的个数+排序 右边的个数+排序ret += MergeSort(nums,left,mid);ret += MergeSort(nums,mid+1,right);int cur1 = left,cur2 = mid+1,i=0;//3.一左一右的个数while(cur1 <= mid && cur2 <= right){if(nums[cur1] > nums[cur2]) {   ret += mid - cur1 + 1;v[i++] = nums[cur2++];}else{v[i++] = nums[cur1++];}}// while(cur1 <= mid && cur2 <= right) v[i++] = nums[cur1] < nums[cur2] ? nums[cur1] : nums[cur2];while(cur1 <= mid) v[i++] = nums[cur1++];while(cur2 <= right) v[i++] = nums[cur2++];for(int i = left ; i <= right ; i++){nums[i] = v[i-left];}return ret;}int reversePairs(vector<int>& record) {return MergeSort(record,0,record.size()-1);}
};

题目分析：我们可以使用归并排序解决这道题，将数组分为两部分，左半部分->排序->右半部分->排序->一左一右，其中我们在一左一右中找逆序对时，只需要固定右半部分一个值，然后去左半部分找有多少大于这个值的元素，这种方法要求归并排序是升序。

也可以固定左半部分一个值，然后去右半部分找有多少小于这个值的元素，这种方法要求归并排序是降序。

假设是升序，在将数组分成一左一右后，[left,mid][mid+1,right]，cur1和cur2分别遍历这两部分，nums[cur1]和nums[cur2]的大小关系有两种情况，

1）nums[cur1] <= nums[cur2]，cur1++

2）nums[cur1] > nums[cur2]，ret += mid - cur1+1，cur2++

class Solution {vector<int> ret;vector<int> nums_tmp;int index[500010];int index_tmp[500010];public:void MergeSort(vector<int>& nums,int left,int right){if(left >= right) return;int mid = (left + right) >> 1;MergeSort(nums,left,mid);MergeSort(nums,mid+1,right);int cur1 = left,cur2 = mid+1,i = 0;while(cur1 <= mid && cur2 <= right){if(nums[cur1] > nums[cur2]){ret[index[cur1]] += (right - cur2 + 1);index_tmp[i] = index[cur1];nums_tmp[i++] = nums[cur1++];}else{index_tmp[i] = index[cur2];nums_tmp[i++] = nums[cur2++];}}while(cur1 <= mid){index_tmp[i] = index[cur1];nums_tmp[i++] = nums[cur1++];}while(cur2 <= right){index_tmp[i] = index[cur2];nums_tmp[i++]= nums[cur2++];}for(int i = left; i <= right ; i++){nums[i] = nums_tmp[i-left];index[i] = index_tmp[i-left];}}vector<int> countSmaller(vector<int>& nums) {ret.resize(nums.size());nums_tmp.resize(nums.size());for(int i = 0; i < nums.size() ; i++){index[i]=i;}MergeSort(nums,0,nums.size()-1);return ret;}
};

题目分析：我们要找出之后有多少元素比我小，依照上题思路，需要选择降序，也是采用分支排序的方法，

为了找到对应的下标，刚开始就要创建一个数组index，里面是各个元素下表，在排序过程中，index也要跟着nums元素位置变化而变化。

class Solution {//vector<int> tmp;int tmp[50010];
public:int _reversePairs(vector<int>& nums,int left,int right){if(left >= right) return 0;int ret = 0;int mid = (left + right)>>1;ret += _reversePairs(nums,left,mid);ret += _reversePairs(nums,mid+1,right);int cur1 = left,cur2 = mid+1;//1.先找翻转对的数量while(cur1 <= mid && cur2 <= right){if(0.5*nums[cur1] > nums[cur2]){ret += (right - cur2 + 1);cur1++;}else{cur2++;}}//2.合并两个有序数组cur1 = left,cur2=mid+1;int i = 0;while(cur1 <= mid && cur2 <= right)tmp[i++] = nums[cur1] > nums[cur2] ? nums[cur1++] : nums[cur2++];while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(i = left; i <= right ; i++){nums[i] = tmp[i-left];}return ret;}int reversePairs(vector<int>& nums) {//tmp.resize(nums.size());return _reversePairs(nums,0,nums.size()-1);   }
};

题目分析：这道题我们依然用分治的思想。将一个数组分成两部分，先找左半部分的翻转对，再找右半部分的翻转对，最后再找一左一右的翻转对。

仍然有两个策略

1）计算当前元素后面，有多少元素的两倍比我少，要求数组降序。

if(nums[cur1] > 2*nums[cur2]) ret += right-cur2+1

2）计算当前元素之前，有多少元素的一半比我大，要求数组升序。

if(nums[cur1] > 2*nums[cur2]) ret += mid-left+1