归并排序(merge sort)

10大排序算法.png

归并排序：1945年由约翰.冯.诺伊曼首次提出，最好最坏平均时间复杂度都是: O(nlogn) 空间复杂度：O(n)

执行流程： 分隔 + 合并
1.不断的将当前序列平均分隔成2个子序列，直到不能再分割(序列中只剩1个元素)
2.不断的将2个子序列合并成一个有序序列，直到最终只剩下1个有序序列

sort(0,list.length);

//对[begin,end)区间内的元素排序
private void sort(int begin,int end) {
    if(end-begin < 2) return;
   //求出分隔中心位置
    int mid = (begin + end)>>1;
   sort(benin,mid);//左边排序
   sort(mid,end);//右边排序
   merge(begin,mid,end);//合并左边和右边
}

/**
  合并逻辑：
  1. 先把左边部分元素copy一份，放到一个新数组中
  2.定义 li 、le 表示左边开始、结束索引； 定义ri、 re 为右边开始结束索引
     定义ai 为可以存储有序元素的索引
  3.遍历对比两个数组元素大小确定需要存放的元素，然后更新左边或右边索引
  1> 左边先遍历完了，那就结束了
  2> 右边先遍历完了，需要把左边剩余元素合并到数组尾部
 */
private void merge(int begin, int mid,int end) {

   int li = 0, le = mid - begin;
   int ri  = mid, re = end;
  //注意 ai 不能初始化为0，因为begin是不断变化的，区间是[begin,mid ,end)
   int ai = begin;
   //把左边元素放进新数组
   for(int i = li; i < le;i++) {
      leftList[I] = list[begin+i];
   }
   
  //左边还没遍历完，才需要移动
  while(li < le) {
      
    //右边数组还没遍历完 且 右边比较小
     if(ri < re && cmp(list[ri],leftList[li]) < 0) {
        //把右边元素放在ai位置
         list[ai] = list[ri];
        ai++;
        ri++;
    }else { //右边已经遍历完了 左边比较小
        list[ai] = leftList[li];
       ai++;
       li++;
   }
     
  }

}