「归并排序」是分治思想的典型应用，它包含这样三个步骤：

• 分解：待排序的区间为[l,r]，令m=l+((r-l)>>1),将区间分为[l,m],[m+1,r]
• 解决：使用归并排序递归地排序两个子序列
• 合并：把两个已经排好序的子序列[l,m]和[m+1,r]合并起来

在带排序序列长度为1的时候，递归开始【回升】，即默认长度为1时，序列时排好的。

剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1: 输入: [7,5,6,4] 输出: 5

❤❤❤归并排序

思路

那么求逆序对和归并排序又有什么关系呢？关键就在于「归并」当中「并」的过程。我们通过一个实例来看看。假设已有2个排序序列待合并，分别为L=={8,12,16,22,100} 和 R={9,26,55,64,91}，令lPtr=0,rPtr=mid+1,设已经合并好的部分为M=[]

L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = []
     |                          |
   lPtr                       rPtr
--> 此时发现L[lPtr]<R[rPtr],把左元素放入M中，并前进一步
L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = [8]
        |                       |
      lPtr                     rPtr
--> 此时8位于M中，且发现右边没有数比8小，即8对逆序【贡献】为0。接着把9并入M，右指针后移。
L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = [8, 9]
        |                          |
       lPtr                       rPtr
--> 此时有L[lPtr]<R[rPtr],把12并入M，此时其对逆序的贡献为M中的9，即rPtr相对于首位置偏移了1.

基于上述推导，发现仅在并入L侧元素（即lPtr右移）时，才计算贡献，其规律是基于如下事实：

• 当L[lPtr]<R[rPtr]，但是比R中[mid+1...rPtr-1]的数字均大，故此时【逆序贡献】为rPtr-(mid+1)

  算法

• 分解：待排序的区间为[l,r]，令m=l+((r-l)>>1),将区间分为[l,m],[m+1,r]

• 解决（递归）：使用归并排序递归地排序两个子序列

• 合并：把两个已经排好序的子序列[l,m]和[m+1,r]合并起来

  实现

  int mergeSort(vector<int>& nums,vector<int>& tmp,int l,int r){
    if(l>=r){
        //仅有1个元素时，逆序贡献0
        return 0;
    }
    int mid=l+((r-l)>>1);
    //总逆序数=左区间逆序数+右区间逆序数+左右区间之间的逆序数
    int ans=mergeSort(nums,tmp,l,mid)+mergeSort(nums,tmp,mid+1,r);
        int pos=l,i=l,j=mid+1;
        while(i<=mid && j<=r){
            if(nums[i]<=nums[j]){
                tmp[pos++]=nums[i++];
                ans+=j-(mid+1);
            }
            else{
                tmp[pos++]=nums[j++];
            }
        }
        while(i<=mid){
            tmp[pos++]=nums[i++];
            ans+=j-(mid+1);
        }
        while(j<=r){
            tmp[pos++]=nums[j++];
        }
        copy(tmp.begin()+l,tmp.begin()+r+1,nums.begin()+l);
        return ans;
    }
  }

  复杂度分析

• 时间复杂度:

• 空间复杂度:

算法2

思路

算法

实现

复杂度分析

• 时间复杂度:
• 空间复杂度:

题目标题难度划分

算法掌握难度程度划分