排序算法系列文章

排序（一）：冒泡排序
排序（二）：选择排序
排序（三）：堆排序
排序（四）：插入排序
排序（五）：二分搜索
排序（六）：归并排序
排序（七）：快速排序
排序（八）：希尔排序

归并排序（Merge-Sort）

基本思想

• 归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，与快速排序一样，归并排序也是基于分治法的（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
• 归并排序将待排序的元素序列分成两个长度相等的子序列，为每一个子序列排序，然后再将他们合并成一个子序列。合并两个子序列的过程也就是两路归并。

算法步骤

• 不断将当前序列平均分割成两个子序列，直到不能再分割。（截止条件：序列中只剩 1 个元素）
• 不断地将 2 个子序列合并成一个有序序列，直到最终只剩下 1 个有序序列。

序列合并

合并到新序列

• 将两个序列合并的思路为：左序列和右序列的中元素挨个比较，将较小的放入新序列中，最后新序列中的元素必然升序，也就是每次都是从未比较的两个子序列的最小值中选出一个更小值。
  

原地合并

• 将两个序列合并时，不一定要合并到新空间，可以合理的利用原空间实现 原地合并。

复杂度

• 由于归并排序总是平均分割子序列，最好、最坏时间复杂度都是 O(nlogn)
• 空间复杂度为 O(n)
• 归并排序属于稳定排序

常见的递推式与复杂度查看表

归并序列代码实现

package _01_排序._06_归并排序;

/*
* 归并排序
* */
public class MergeSort {
    private static int[] leftArray;

    public static void main(String[] args) {
        int[] array = {4,3,5,1,9,8,2,0};
        leftArray = new int[array.length >> 1];

        //[begin,end)左闭右开
        divide(0,array.length,array);

        for (int i : array) {
            System.out.println(i + "_");
        }
    }

    //分开
    private static void divide(int begin, int end, int[] array){
        if (end - begin < 2) return;// 数组元素大于2, 才能进行归并排序
        int mid = (begin + end) >> 1;
        //归并排序左子序列
        divide(begin,mid,array);
        //归并排序右子序列
        divide(mid,end,array);
        //合并整个序列
        merge(begin, mid, end,array);
    }

    //合并
    private static void merge(int begin, int mid, int end, int[] array){
        int li = 0, le = mid - begin;//左边数组（基于leftArray）
        int ri = mid, re = end;//右边数组（基于 array）
        int ai = begin;//array 的索引

        //备份左边数组到leftArray
        for (int i = li; i < le; i++) {
            leftArray[i] = array[begin + i];
        }

        //如果左边还没有结束
        while (li < le){// li == le 左边结束, 则直接结束归并
            if (ri < re && array[ri] < leftArray[li]){
                // 拷贝右边数组到array
                array[ai++] = array[ri++];
            }else{
                //拷贝左边数组到array
                array[ai++] = leftArray[li++];
            }
        }
    }
}