数据结构与算法（第二季）：归并排序（Merge Sort）

归并排序（Merge Sort）

一、概念

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

image

二、divide（划分）

• 递归调用，将数据递归划分到最小，然后再合并。

public class MergeSort<T extends Comparable<T>> extends Sort<T> {
    private T[] leftArray;

    /**
     * 对 [begin, end) 范围的数据进行归并排序
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) return;

        int mid = (begin + end) >> 1;
        sort(begin, mid);
        sort(mid, end);
        merge(begin, mid, end);
    }
}
复制代码

三、merge（合并）

1、概念

• 两个数组都有一个指向头节点的指针。
• 比较两个指针对应值的大小，将小的值取出，并将其指针向后移动一位。
• 黑色代表已填入的数据，黄色代表这一轮比较较小的值。

image

2、细节

• 需要merge的2组序列存在于同一个数组中，并且是挨在一起的。

image

• 如果我们将3和8比较的结果放入数组左侧，那么8的值就会被覆盖。
• 为了更好的完成merge操作，最好将其中一组序列备份出来，比如[begin, mid)
• 我们将左侧数组复制一份出来，然后进行merge操作。

image

3、实例

• 黑色代表已填入的数据，黄色代表这一轮比较较小的值。

image

• 左边先结束，右边剩下的无需再排序，可结束排序。

image

• 右边先结束，左边剩下的可直接搬到右边，结束排序。

image

4、代码实现

public class MergeSort<T extends Comparable<T>> extends Sort<T> {
    private T[] leftArray;

    @Override
    protected void sort() {
        leftArray = (T[]) new Comparable[array.length >> 1];
        sort(0, array.length);
    }

    /**
     * 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
     */
    private void merge(int begin, int mid, int end) {
        int li = 0, le = mid - begin;
        int ri = mid, re = end;
        int ai = begin;

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

        // 如果左边还没有结束
        while (li < le) { 
            if (ri < re && cmp(array[ri], leftArray[li]) < 0) {
                array[ai++] = array[ri++];
            } else {
                array[ai++] = leftArray[li++];
            }
        }
    }
}
复制代码

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