数据结构与：算法归并排序

归并排序介绍

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

排序过程

将一个数组分解成两个子序列，这两子序列继续分解，直到不能在分解为止；从最小的子序列开始进行归并，形成一个较大的有序子序列，再继续归并直到整个数组有序。该过程我们可以用递归来实现。排序过程如下图所示：

归并排序.png

归并操作的工作原理

将两个分别有序的子序列归并成一个新的较大有序序列，其过程如下：

1.准备一个辅助数组，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2.设定两个指针p1和p2，最初位置分别为两个已经排序序列的起始位置
3.比较指针p1和p2所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4.重复步骤3直到某一指针超出序列尾
5.将另一序列剩下的所有元素直接复制到合并序列尾

算法实现

public class MergeSort {
    
    private static void mergeSort(int[] arr,int left, int right) {
        if(left == right) return;
        
        int mid = left + ((right - left) >> 1);     //int mid = (left + right)/2;
        
        mergeSort(arr,left,mid);    //左侧序列分解
        mergeSort(arr,mid+1,right); //右侧序列分解
        
        merge(arr,left,mid,right);  //归并
        
    }
    
    private static void merge(int[] arr,int left,int mid,int right) {
        int[] help = new int[right - left + 1];     //准备辅助数组
        
        //准备两个指针分别指向两个序列的开始
        int p1 = left;
        int p2 = mid + 1;
        
        int i = 0;
        
        /*
         *  比较指针p1和p2所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置,
         *  直到某一指针超出序列尾
         * */
        while(p1 <= mid && p2 <= right) {
            help[i++] = (arr[p1] < arr[p2])?arr[p1++]:arr[p2++];
        }
        
        //p2指针超出序列尾，将左侧序列继续添加进辅助数组
        while(p1 <= mid) {
            help[i++] = arr[p1++];
        }
        
        //p1指针超出序列尾，将右侧序列继续添加进辅助数组
        while(p2 <= right) {
            help[i++] = arr[p2++];
        }
        
        //拷贝会原数组
        for(int j = 0; j < help.length; j++) {
            arr[left + j] = help[j];
        }
    }
    
    public static void mergeSort(int[] arr) {
        if(arr == null || arr.length < 2) return;
        
        mergeSort(arr,0,arr.length-1);
        
    }
    
    //测试
    public static void main(String[] args) {
        
        int[] arr0= {10,4,6,3,8,2,5,7};
        
        mergeSort(arr0);
        
        for(int i=0; i<arr0.length; i++) {
            System.out.print(arr0[i] + " ");
        }
        //2 3 4 5 6 7 8 10
        
        System.out.println();
        
        int[] arr1 = {10,9,8,7,6,5,4,3,2,1};
        
        mergeSort(arr1);
        
        for(int i=0; i<arr1.length; i++) {
            System.out.print(arr1[i] + " ");
        }
        //1 2 3 4 5 6 7 8 9 10
    }

}

复杂度

在排序中由于我们使用了辅助数组，所以额外空间复杂度为O(n);
由归并排序的递归公式：T(N) = 2T(N/2) + O(N) 可知时间复杂度为O(NlogN)
算法的复杂度与master定理：http://www.gocalf.com/blog/algorithm-complexity-and-master-theorem.html