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

  • 分解：待排序的区间为[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=[]

  1. L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = []
  2.      |                          |
  3.    lPtr                       rPtr
  4. --> 此时发现L[lPtr]<R[rPtr],把左元素放入M中，并前进一步
  5. L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = [8]
  6.         |                       |
  7.       lPtr                     rPtr
  8. --> 此时8位于M中，且发现右边没有数比8小，即8对逆序【贡献】为0。接着把9并入M，右指针后移。
  9. L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = [8, 9]
  10.         |                          |
  11.        lPtr                       rPtr
  12. --> 此时有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]合并起来

    实现

    1. int mergeSort(vector<int>& nums,vector<int>& tmp,int l,int r){
    2.   if(l>=r){
    3.       //仅有1个元素时，逆序贡献0
    4.       return 0;
    5.   }
    6.   int mid=l+((r-l)>>1);
    7.   //总逆序数=左区间逆序数+右区间逆序数+左右区间之间的逆序数
    8.   int ans=mergeSort(nums,tmp,l,mid)+mergeSort(nums,tmp,mid+1,r);
    9.       int pos=l,i=l,j=mid+1;
    10.       while(i<=mid && j<=r){
    11.           if(nums[i]<=nums[j]){
    12.               tmp[pos++]=nums[i++];
    13.               ans+=j-(mid+1);
    14.           }
    15.           else{
    16.               tmp[pos++]=nums[j++];
    17.           }
    18.       }
    19.       while(i<=mid){
    20.           tmp[pos++]=nums[i++];
    21.           ans+=j-(mid+1);
    22.       }
    23.       while(j<=r){
    24.           tmp[pos++]=nums[j++];
    25.       }
    26.       copy(tmp.begin()+l,tmp.begin()+r+1,nums.begin()+l);
    27.       return ans;
    28.   }
    29. }

    复杂度分析

  • 时间复杂度:归并排序-数组中的逆序对 - 图1

  • 空间复杂度:归并排序-数组中的逆序对 - 图2

排序链表（自顶向下、自底向上）

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶： 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

算法（归并排序，自顶向下）

  • 分解：待排序的区间为[head,nullptr),通过快慢指针寻找中点，即mid=slow(when fast==nullptr),子序列分别为[head,slow],[slow->next,nullptr)
  • 解决：使用归并排序递归地排序两个子序列
  • 合并：把两个已经排好序的子序列[head,slow],[slow->next,nullptr)合并起来

实现

  1. /* Merge */
  2. ListNode* merge(ListNode* lhs,ListNode* rhs){
  3.     /* merge two sorted list*/
  4.     ListNode* dummyHead=new ListNode(0);
  5.     auto tmp=dummyHead,tmp1=lhs,tmp2=rhs;
  6.     while(tmp1!=nullptr && tmp2!=nullptr){
  7.         if(tmp1->val<=tmp2->val){
  8.             tmp->next=tmp1;
  9.             tmp1=tmp1->next;
  10.         }else{
  11.             tmp->next=tmp2;
  12.             tmp2=tmp2->next;
  13.         }
  14.         tmp=tmp->next;
  15.     }
  16.     if(tmp1){
  17.         tmp->next=tmp1;
  18.     }else{
  19.         tmp->next=tmp2;
  20.     }
  21.     return  dummyHead->next;
  22. }
  24. /* divide and solve */
  25. ListNode* sortList(ListNode* head){
  26.     if(head==nullptr ||head->next==nullptr)
  27.         return head;
  28.     auto slow=head,fast=head;
  29.     while(fast!=nullptr){
  30.         fast=fast->next;
  31.         if(fast!=nullptr){
  32.             fast=fast->next;
  33.         }
  34.         if(fast==nullptr) break;    /* important !*/
  35.         slow=slow->next;
  36.     }
  37.     auto next_head=slow->next;
  38.     slow->next=nullptr;
  39.     return merge(sortList(head),sortList(next_head));
  40. }

复杂度分析

  • 时间复杂度:归并排序-数组中的逆序对 - 图3

  • 空间复杂度:归并排序-数组中的逆序对 - 图4，即递归栈的长度

    算法（归并排序，自低向顶，主动分解）

  • 分解：将待排序的区间主动分解，按sublen逐渐以2指数递增

  • 解决：使用归并排序递归地排序两个子序列（即当前节点数为1或0时，直接返回）

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

    实现

    1. ListNode* sortListBottom2Up(ListNode* head) {
    2.   int len=0;
    3.   auto tmp=head;
    4.   while(tmp!=nullptr){
    5.       tmp=tmp->next;
    6.       len++;
    7.   }
    8.   auto assi_node=new ListNode(0,head);
    9.   for(int sublen=1;sublen<len;sublen<<=1){
    10.       auto head_tmp=assi_node->next,assi_node_tmp=assi_node;
    11.       while(head_tmp!=nullptr){
    12.           /* get first head of first segment, len = sublen */
    13.           auto first=head_tmp,tmp1=first;
    14.           for(int i=1;i<sublen && tmp1->next!=nullptr;i++){
    15.               tmp1=tmp1->next;
    16.           }
    17.           /* get second head of second segment, len = sublen*/
    18.           auto second=tmp1->next,tmp2=second;
    19.           tmp1->next=nullptr;        /* need to cut first's relation from all*/
    20.           for(int i=1;i<sublen && tmp2!=nullptr && tmp2->next!=nullptr;i++){
    21.               tmp2=tmp2->next;
    22.           }
    23.           /* ready to get next part(next first and next second)*/
    24.           if(tmp2!=nullptr){
    25.               head_tmp=tmp2->next;
    26.               tmp2->next=nullptr;
    27.           }else{
    28.               /* important! */
    29.               head_tmp=nullptr;
    30.           }
    31.           /* merge first and second segment */
    32.           auto newhead=merge(first,second);
    33.           /* IMPORTANT! head insert way!*/
    34.           assi_node_tmp->next=newhead;
    35.           while(assi_node_tmp->next!=nullptr){
    36.               assi_node_tmp=assi_node_tmp->next;
    37.           }
    38.       }
    39.   }
    40.   return assi_node->next;
    41. }

    复杂度分析

  • 时间复杂度:归并排序-数组中的逆序对 - 图5

  • 空间复杂度:归并排序-数组中的逆序对 - 图6
星级 题目难度
☆ 简单
☆☆ 中等
☆☆☆ 困难

算法掌握难度程度划分

星级 掌握难度
无 普通
❤ 经典，易掌握
❤❤ 经典，略难掌握
❤❤❤ 困难