归并排序

分类 -------------- 内部比较排序
数据结构 ---------- 数组
最差时间复杂度 ---- O(nlogn)
最优时间复杂度 ---- O(nlogn)
平均时间复杂度 ---- O(nlogn)
所需辅助空间 ------ O(n)
稳定性 ------------ 稳定

原理

       归并排序的实现分为递归实现与非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并，一直下去直到归并了整个数组。

步骤

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

代码实现

public class MergeSort {

    // 合并两个已排好序的数组A[left...mid]和A[mid+1...right]
    void merge(Integer a[], int left, int mid, int right)
    {
        int len = right - left + 1;
        // 辅助空间O(n)
        Integer[] temp = new Integer[len];
        int index = 0;
        // 前一数组的起始元素
        int i = left;
        // 后一数组的起始元素
        int j = mid + 1;
        while (i <= mid && j <= right)
        {
            // 带等号保证归并排序的稳定性
            temp[index++] = a[i] <= a[j] ? a[i++] : a[j++];
        }
        while (i <= mid)
        {
            temp[index++] = a[i++];
        }
        while (j <= right)
        {
            temp[index++] = a[j++];
        }
        for (int k = 0; k < len; k++)
        {
            a[left++] = temp[k];
        }
    }
    // 递归实现的归并排序(自顶向下)
    void mergeSortRecursion(Integer a[], int left, int right)
    {
        // 当待排序的序列长度为1时，递归开始回溯，进行merge操作
        if (left == right)
        {
            return;
        }
        int mid = (left + right) / 2;
        mergeSortRecursion(a, left, mid);
        mergeSortRecursion(a, mid + 1, right);
        merge(a, left, mid, right);
    }

    // 非递归(迭代)实现的归并排序(自底向上)
    void mergeSortIteration(Integer a[], int len)
    {
        // 子数组索引,前一个为A[left...mid],后一个子数组为A[mid+1...right]
        int left, mid, right;
        // 子数组的大小i初始为1,每轮翻倍
        for (int i = 1; i < len; i *= 2)
        {
            left = 0;
            // 后一个子数组存在(需要归并)
            while (left + i < len)
            {
                mid = left + i - 1;
                // 后一个子数组大小可能不够
                right = mid + i < len ? mid + i : len - 1;
                merge(a, left, mid, right);
                // 前一个子数组索引向后移动
                left = right + 1;
            }
        }
    }

    public static void main(String[] args){
        Integer[] a = {3,4,1,9,5,2,6,10,20,16,13,11,0};
        Integer[] b = {3,4,1,9,5,2,6,10,20,16,13,11,0};

        MergeSort sort = new MergeSort();
        // 递归实现
        sort.mergeSortRecursion(a, 0, a.length - 1);
        // 非递归实现
        sort.mergeSortIteration(b, b.length);

        System.out.println("a by MergeSort is " + Tool.arrayToString(a));
        System.out.println("b by MergeSort is " + Tool.arrayToString(b));

    }
}

public class Tool {
    public static <T> String arrayToString(T[] array){
        StringBuilder builder = new StringBuilder("[");
        for (int i = 0; i < array.length; i++){
            T item = array[i];
            builder.append(item + "");
            if (i != array.length - 1){
                builder.append(",");
            }
        }

        builder.append("]");
        return builder.toString();
    }

    public static <T> void exchange(T[] array, int i, int j){
        T temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

实现结果：

a by MergeSort is [0,1,2,3,4,5,6,9,10,11,13,16,20]
b by MergeSort is [0,1,2,3,4,5,6,9,10,11,13,16,20]