【Java】归并排序

怼烎@ 2021-12-16 23:31 234阅读 0赞

归并排序是另一类不同的排序方法，这种方法是运用分治法解决问题的典型范例。

归并排序的基本思想是基于合并操作，即合并两个已经有序的序列是容易的，不论这两个序列是顺序存储还是链式存储，合并操作都可以在 Ο(m+n)时间内完成（假设两个有序表的长度分别为 m 和 n）。

归并排序的过程为：

1. 划分：将待排序的序列划分为大小相等（或大致相等）的两个子序列；  
2. 治理：当子序列的规模大于 1 时，递归排序子序列，如果子序列规模为 1 则成为有序序列；  
3. 组合：将两个有序的子序列合并为一个有序序列。

下图显示了归并算法的执行过程。假设待排序序列为\{4, 8, 9, 5, 2, 1, 4, 6\}，归并排序导致了一系列递归的调用，而这一系用过程可以由一个二叉树来表示。树中每个结点由两个序列组成，上端为该结点所表示的递归调用的输入，而下端为相应递归调用的输出。树中的边用表示递归调用方向的两条边取代，边上的序号表示各个递归调用发生的次序。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70]

归并排序中一个核心的操作是将一个序列中前后两个相邻的子序列合并为一个有序序列。

先来一个最简单的归并排序理解过程，代码还可以继续优化~

import java.util.Arrays;
    
    //归并排序
    public class MergeSortTest { 
        public static void main(String[] args){ 
            MergeSortTest sort = new MergeSortTest();
            int[] arr = { 5,2,7,3,9,10,8,6,1,4};
            sort.mergeSort(arr,0,arr.length-1);
            System.out.println(Arrays.toString(arr));
        }
        //将两个有序区间合并为一个有序区间
        private void merge(int[] a,int p,int q,int r){ 
            int[] b = new int[r-p+1];
            int s=p;
            int t=q+1;
            int k=0;
            while(s<=q && t<=r){ 
                if(a[s]<a[t]){ 
                    b[k++]=a[s++];
                }else{ 
                    b[k++]=a[t++];
                }
            }
            while(s<=q){ 
                b[k++]=a[s++];
            }
            while(t<=r){ 
                b[k++]=a[t++];
            }
            for (int i = 0; i < b.length; i++) { 
                a[p+i]=b[i];
            }
        }
    
        //排序
        public void mergeSort(int[] r,int low,int high){ 
            if(low<high){ 
                mergeSort(r,low,(high+low)/2);
                mergeSort(r,(high+low)/2+1,high);
                merge(r,low,(high+low)/2,high);
            }
        }
    
    }

<table> 
 <tbody> 
  <tr> 
   <td align="left"><font><b>时空复杂度<b></b></b></font></td> 
  </tr> 
 </tbody> 
</table>

来张整体图的比较吧~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70]: /images/20211214/fdc054ce87544e54aba9f8ed1cc4615e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70 1]: /images/20211214/fc47dd94fff842e7801d287b4bf3d991.png