【基本算法】归并排序

目录

• 归并排序基础思想
• 归并排序求逆序数对
• 代���

  归并排序基础思想

  归并排序主要运用了分治的思想

  我们把归并排序分为两个部分：

  1. 分解：我们把无序的数列分成两个部分，对于每个部分，在分成更小的两个部分，直到数列只有一个元素为止
  2. 合并：我们把两个数列合并起来，成为一个排好序的一个数列

  操作大体如下图

  分解只是把 C C C 数组分成 A , B A,B A,B 两个数组，不用考虑大小关系，所以比较容易

  这里主要讲解一下和并的过程

  合并是把 A , B A,B A,B 两个排好了的数组有序地合并起来

  例如上图中最后一步

  A = A= A= { 2 , 4 , 7 , 8 2, 4, 7, 8 2,4,7,8 }

  B = B= B= { 1 , 3 , 5 , 6 1, 3, 5, 6 1,3,5,6 }

  首先 1