归并排序.md

算法流程

• 从下往上的归并排序：

  • 将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；
  • 得到若干个长度为2的有序数列，再将这些数列两两合并；
  • ...
  • 重复操作直接合并成一个数列为止。这样就得到了我们想要的排序结果。

• 从上往下的归并排序：它与"从下往上"在排序上是反方向的。它基本包括3步：

  • 分解 -- 将当前区间一分为二，即求分裂点 mid = (low + high)/2;
  • 求解 -- 递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1。
  • 合并 -- 将已排序的两个子区间a[low...mid]和 a[mid+1...high]归并为一个有序的区间a[low...high]。

代码

def merge(a, b):
    res = []
    h = j = 0
    while j < len(a) and h < len(b):
        if a[j] < b[h]:
            res.append(a[j])
            j += 1
        else:
            res.append(b[h])
            h += 1
    res.extend(a[j:])
    res.extend(b[g:])
    return res

def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    middle = len(lists) >> 1
    left = merge_sort(lists[:middle])
    right = merge_sort(lists[middle:])
    return merge(left, right)

其他应用

• 逆序对

逆序对数量查找可以通过归并排序的交换次数算出，
在数组a[left...mid]和a[mid+1..right]，left<= i <=mid, mid+1<= j< =right ,
当满足a[i] > a[j]时存在逆序对，
假设a[j]放在a[i]之前，
则a[i]到a[mid](因为a数组为有序数组)的值都大于a[j],
共有mid-i+1个逆序对

• 链表合并 (LeetCode 21)

  给出两个排好序的单向链表，返回合并排序后新的单向链表。
  

def mergeTwoLists(self, l1, l2):
      """
      :type l1: ListNode
      :type l2: ListNode
      :rtype: ListNode
      """

      dummy=res=ListNode(0)
      while l1 and l2:
          if l1.val<l2.val:
              res.next=l1
              l1=l1.next
              print(1)
          else:
              res.next=l2
              l2=l2.next
              print(2)
          res=res.next

      while l1:
          res.next=l1
          res=res.next
          l1=l1.next
      while l2:
          res.next=l2
          res=res.next
          l2=l2.next
      return dummy.next