Java归并排序

概要

        归并排序（Merge Sort）是应用分治思想的一个典型例子。把一个待排序序列拆分为两个子序列，分别对两个子序列排序，子序列排序时也采用相同的方法，直至拆分后的两个子序列都是有序的，即长度为1的序列天然有序，这时停止拆分，将两个有序的子序列归并为一个更大的有序序列，与之前拆分时的路径相反，不断的归并有序子序列，最终归并为一个序列。这种将两个有序序列归并为一个有序序列的操作称为二路归并。

二路归并：对比两个有序序列中最小的元素，也就是各自的第一个元素，其中更小的那个就是全局最小的元素，把它移到结果序列中，继续对比两个序列的首元素，得到全局第二小的元素，把它移到结果序列中，接下来的操作也是如法炮制，如此往复，直至其中一个序列为空，则可以把另一个序列剩下的元素直接并入结果序列，二路归并操作就算完成了。

自顶向下的归并排序     

        要对子数组 a[1o，hi)进行排序，先将它分为 a[1o，mid)和 a[mid，hi) 两部分，分别通过递归调用将它们单独排序，最后将有序的子数组归并为最终的排序结果。

自顶向下的归并排序图解

自底向上的归并排序

        想象每个元素都是长度为1的数组，将它们两两归并，得到很多组长度为2的有序数组，然后再四四归并，得到很多组长度为4的有序数组，再八八归并，如此这般，直至最后归为一个数组。

自底向上的归并排序图解

时间复杂度：O(nlogn)

空间复杂度：T(n)

Java实现代码

定义了一个排序接口，后面可用其它算法实现。

public interface Sort {    void sort(int[] array);    //交换数组i和j位置的值    default void exchange(int[] array, int i, int j){        int item = array[i];        array[i] = array[j];        array[j] = item;    }}

自顶向下的归并排序代码

/** * 归并排序 */public class MergeSort implements Sort{    private int[] tem;    @Override    public void sort(int[] arr) {        tem = new int[arr.length];        merge_sort(arr,0,arr.length);    }    /**     * 自顶向下的递归式归并排序     */    public void merge_sort(int[] arr, int lo, int hi) {        if(hi - lo >1;        merge_sort(arr, lo, mid);        merge_sort(arr, mid, hi);        merge(arr,lo,mid,hi);    }    /**     * 二路归并     */    public void merge(int[] arr, int lo, int mid, int hi){        if(hi - lo == 1) return;        int k = lo;        while (k 1;        merge_sort(arr, lo, mid);        merge_sort(arr, mid, hi);        merge(arr,lo,mid,hi);    }    /**     * 插入排序     */    private void insertionSort(int[] array, int lo, int hi){        int lef = lo;        lo++;        while(lo lef;i--){                if(array[i]  
二路归并的一种优化
 
        在备份辅助数组时只备份左子数组，右子数组在结果数组中不动，归并时元素先归并到结果数组的左边lo到mid的位置，当lo到mid的位置填满后，开始填入mid到hi，这时mid到hi也会因为归并时消耗了元素而恰好空出位置来，所以右子数组的元素不会被覆盖，这样能省下一半元素备份的时间。另外一点，当左子数组消耗完，即i==mid时，可以直接退出循环，不需要将右子数组剩余的元素并入结果数组，因为它们原本就在那里。
 
public void merge(int[] arr, int lo, int mid, int hi){        if(hi - lo == 1) return;        int k = lo;        while (k