归并排序

归并排序（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用于递归调用。

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

最后

以上就是能干鸡翅为你收集整理的十大排序算法之归并排序归并排序的全部内容，希望文章能够帮你解决十大排序算法之归并排序归并排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。