归并排序

原理(分治的思想)

1-8 归并排序法的复杂度分析【一手微信itit11223344】.mp4_20210929_164226699.jpg

过程

1.递归分治

2.最后通过merge合并（具体操作过程）

  • 定义3个变量 , “ L “ 代表头部 , “ mid “ 代表中间位置(L+R)/2 , “ r “ 代表最后的位置 ， “ arr “ 为要排序的数组
  • 先复制一个相同的数组，被复制的那个数组比原数组多1

  • 每轮为 arr[k] 赋值

    • 前半段已经排完的情况
    • 后半段已经排完的情况
    • 排序的两个数前大后小

    • 排序的两个数前小后大

      3. 代码部分

      ```java public class MergeSort {

      private MergeSort(){ }

      public static > void sort(E[] arr){ sort(arr,0,arr.length-1); } private static > void sort(E[] arr,int l,int r){ if (l >= r) return;

      int mid = (l+r) / 2; sort(arr,l,mid); sort(arr,mid+1,r); merge(arr,l,mid,r); }

  1. //合并两个有序区间 arr[l,mid]  arr[mid+1,r]
  2. private static <E extends Comparable<E>> void merge(E[] arr,int l,int mid,int r){
  3.     //1.先复制一个相同的数组，被复制的那个数组比原数组多1
  4.     E[] temp = Arrays.copyOfRange(arr,l,r+1);
  6.     //前半个从l开始，后半个从mid+1开始
  7.     int i = l, j = mid+1;
  9.     //2.每轮为 arr[k] 赋值
  10.     for (int k = l; k <= r; k++) {
  11.         if (i>mid){
  12.            //前半段已经排完了，可以直接把后半段的赋值给temp
  13.             // 因为temp从0开始，而arr从l开始，因此赋值应该从j-l开始
  14.             arr[k] = temp[j-l]; j++;
  15.         }else if (j>r){
  16.             //后半段已经排完了，直接把前半段的赋值给temp
  17.             arr[k] = temp[i-l]; i++;
  18.         }else if (temp[i-l].compareTo(temp[j-l]) <= 0){
  19.             arr[k] = temp[i-l];i++;
  20.         }else {
  21.             arr[k] = temp[j-l];j++;
  22.         }
  23.     }
  24. }

}

  1. <a name="vIoPP"></a>
  2. ## 微观上的过程
  4. <a name="AarAi"></a>
  5. ## 复杂性
  6. ![1-8 归并排序法的复杂度分析【一手微信itit11223344】.mp4_20210929_163021680.jpg](https://cdn.nlark.com/yuque/0/2021/jpeg/21552184/1633178585810-bd5a58ca-9484-4c01-8d34-c25a8468dc90.jpeg#clientId=u1522c9dd-e46d-4&from=ui&id=ub79dd509&margin=%5Bobject%20Object%5D&name=1-8%20%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E6%B3%95%E7%9A%84%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90%E3%80%90%E4%B8%80%E6%89%8B%E5%BE%AE%E4%BF%A1itit11223344%E3%80%91.mp4_20210929_163021680.jpg&originHeight=1080&originWidth=1728&originalType=binary&ratio=1&size=82399&status=done&style=none&taskId=u2b4a0379-5636-48ed-abd3-11a15ba33ec)
  7. <a name="H1Guy"></a>
  8. # 归并排序优化
  10. <a name="QgReW"></a>
  11. ## 1.先判断再merge
  12. ```java
  13. if(arr[mid].compareTo(arr[mid+1])>0)
  14.    merge(arr,l,mid,r,temp);
  • 如果队列已经有序了就不必要再排队了

2.在一定的区间内使用插入排序法(有时候会翻车)

  1. if (r-l <= 15){
  2.     InsertionSort.sort2(arr,l,r);
  3.     return;
  4. }
  • 在一定范围内使用插入排序

    3.优化每次都创建内存空间这个操作

自底向上的归并排序算法

总结

  • 首先是一个递归算法
  • 是一个典型的分治算法
  • 时间复杂度:O(nlogn)
  • 加入对merge的优化后，对基本有序的数组，O(n)的
  • 优化
    • 判断是否需要merge
    • 对小规模数据使用插入排序
    • 只创建一个临时空间
  • 归并排序不是原地排序算法
  • 还可以实现自底向上
  • 可以用来求解逆序对数问题