归并排序基本知识介绍

前言

归并排序稍微有那么些些的麻烦，归并排序中会涉及到递归算法。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

1、首先考虑下如何将两个有序数列合并。这个非常简单，只要比较的两个数列的第一个数，谁小就先取谁，取了后移动索引。然后再进行比较，如果有任何一个数列为空，那直接将另一个数列的数据依次取出即可。

public static void mergeArray(int[] a,int[] b,int[] c){
        int i = 0;
        int j = 0;
        int m = 0;
        while(i<a.length && j<b.length){
            c[m++] = a[i] < b[j] ? a[i++] : b[j++];
        }
        while(i<a.length){
            c[m++] = a[i++];
        }
        while(j<b.length){
            c[m++] = b[j++];
        }
    }

可以看出合并有序数列的效率是比较高的，可以达到O(n)。

2、解决了上面的合并有序数列问题，再来看归并排序

其基本思路就是将任意一个数组分成两组A，B，如果这两组组内的数据都是有序的，那么就可以很方便的将这两组数据进行排序。如何让这两组组内数据有序了？
可以将A，B组各自再分成两组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的两个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

• 归并排序的代码如下：

public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {2,3,6,4,9,7,8,5,1,0,12,87,34,23,11,10};
        mergeSort(arr);
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
    
    public static void mergeSort(int[] arr){
        if(arr==null||arr.length<2){
            return;
        }
        sortProcess(arr,0,arr.length-1);
    }
    
    public static void sortProcess(int[] arr,int L,int R){
        if(L == R){
            return;
        }
        int mid = L + ((R - L) >> 1);//L和R的中点位置
        sortProcess(arr,L,mid);
        sortProcess(arr,mid+1,R);
        merge(arr,L,mid,R);
    }
    
    public static void merge(int[] arr,int L,int mid,int R){
        int[] help = new int[R-L+1];
        int i = 0;
        int p1 = L;
        int p2 = mid+1;
        while(p1 <= mid && p2 <= R){
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        //两个必有且只有一个越界
        while(p1 <= mid){
            help[i++] = arr[p1++];
        }
        while(p2 <= R){
            help[i++] = arr[p2++];
        }
        for(i=0;i<help.length;i++){
            arr[L+i] = help[i];
        }
    }

}

输出结果：

0 1 2 3 4 5 6 7 8 9 10 11 12 23 34 87 

上述代码核心为后两个方法sortProcess完成递归分组，merge完成排序。整体上代码不太复杂，其中有一处解释一下:
int mid = L + ((R - L) >> 1);//L和R的中点位置
这句代码等同于(L+R)/2
但是比这个代码要好L+R假如数据特别大，那么L+R可能会造成溢出，这样一来就出错了，但是如果是L/2+R/2这样就不会溢出了，而表达式可以变为L+（R-L）/2====》 L + ((R - L) >> 1)，虽然说这样做都是常量操作，时间复杂度的指标是一样的，但是移位运算比算数运算的操作时间常量还是要小的多的，关于移位运算可以看这里

归并排序的时间复杂度

归并排序的效率是比较高的。
1、设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(NlogN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(NlogN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。
2、还可以通过master公式来套用一下，得出归并排序的时间复杂度，master公式可以看这里，文末有