十大排序算法之归并排序

归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

算法步骤

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

divide实现

private E[] leftArray;

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

    /**
     * 对索引范围为[begin,end)的元素进行拆分
     * @param begin
     * @param end
     */
    private void divide(int begin, int end) {
        if(end - begin < 2) {
            return;
        }

        int middle = (begin + end) >> 1;
        divide(begin, middle);
        divide(middle, end);

        merge(begin, middle, end);
    }

merge实现

private void merge(int begin, int middle, int end) {

        int li = 0;
        int le = middle - begin;
        int ri = middle;
        int re = end;
        int ai = begin;

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

        while (li < le) {

            if(ri < re && cmp(leftArray[li], array[ri]) > 0) {
                array[ai++] = array[ri++];
            } else {
                array[ai++] = leftArray[li++];
            }
        }

    }

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

从代码中不难看出：归并排序的空间复杂度是O(n/2+ logn)= O(n)，其中n/2用于临时存放左侧数组，logn用于递归调用。

更多精彩内容关注本人公众号：架构师升级之路