归并排序

向右看齐 2022-07-12 16:42 30阅读 0赞

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，归并排序将两个已排序的表合并成一个表。

归并排序的操作核心是递归分割而后逐步合并，看下图

假设待排数组为\{14,12,15,13,11,16\}

1.分割的过程是要将数组逐层分成单个数字（单个数字构成的数组一定是有序的）

2.合并前首先要新建一个数组，用来存放合并并且排序后的新数组

3.最后将新数组替换原来的待排数组

![20170228113011590][]

归并排序最难理解的地方是分割后的合并，我们以数组a\{2,4,5,7\}和数组b\{1,3,6,8\}为例来分析

![20170228113729672][]

两者的比较过程就是要将小的数放在前面，排成由小到大的序列，上图中假设指针i和指针j分别在两个数组的起始位置，判断a\[i\]和b\[j\]的大小关系，如果a\[i\]<b\[j\]那么将a\[i\]放入新数组中，指针i后移，相反，则将b\[j\]放入数组中，指针j后移，整个过程通过while循环来实现。

程序（Java）

package guibing;
    
    import java.util.Arrays;
    
    public class Example {
          public static int[] sort(int[] nums, int low,int high){
             
              int mid=(low+high)/2;
              if(low<high){
                  //分割过程
                  sort(nums,low,mid);
                  sort(nums,mid+1,high);
                  //合并过程
                  merger(nums,low,mid,high);
              }
          
            return nums;
              
          } 
          public static void merger(int[] nums,int low,int mid,int high){
              int[] temp=new int[high-low+1];
              int i=low;
              int j=mid+1;
              int k=0;
              while(i<=mid&&j<=high){
                  if(nums[i]<nums[j]){
                      temp[k++]=nums[i++];
                  }else{
                      temp[k++]=nums[j++];
                  }
              }
              //左半部分还有剩余
              while(i<=mid){
                  temp[k++]=nums[i++];
              }
              //右半部分还有剩余
              while(j<=high){
                  temp[k++]=nums[j++];
          }
              //新数组替换待排数组相应位置上的数字元素
              for(int l=0;l<temp.length;l++){
                  nums[low+l]=temp[l];
              }
          }
          public static void main(String[] args) {
               int[] nums={14,12,15,13,11,16};
               Example.sort(nums, 0, nums.length-1);
               System.out.println(Arrays.toString(nums));  
               
        }
    }

![20170228115701219][]

时间复杂度和空间复杂度

时间复杂度：最好O(nlogn)，最差O(nlogn)，平均O(nlogn)

空间复杂度：O(n)

稳定性：稳定

[20170228113011590]: /images/20220709/cee4a75834d14b828e0ba81c967824f9.png
[20170228113729672]: /images/20220709/cfb14823ce2040598e79d8fdd58623c4.png
[20170228115701219]: /images/20220709/48b894e676ee4a15a3464d8c41069028.png