死磕归并排序算法

关注

发布于: 2021 年 03 月 04 日

本文已被 Github 仓库收录 https://github.com/silently9527/JavaCore
程序员常用的 IDEA 插件：https://github.com/silently9527/ToolsetIdeaPlugin
完全开源的淘客项目：https://github.com/silently9527/mall-coupons-server
微信公众号：贝塔学 Java

前言

在上一篇《常见的初级排序算法，这次全搞懂》，主要谈了常用的初级算法，这些算法的时间复杂度都是 O(n²)，这些算法无法处理大量数据；本篇我们谈一种基于归并操作完成排序的算法。

归并排序算法思路

要将一个数组排序，可以先将数组分为两个数组分别排序，然后再将结果归并在一起，重复递归这个过程，直到数组整体有序，这就是归并排序的算法思路。

归并排序的优点是它能够保证任意长度为 N 的数组排序所需的时间与 NlogN 成正比，这个优点是初级排序无法达到的。

缺点是因为归并操作需要引入额外的数组，额外的空间与 N 成正比

原地归并实现

在实现归并排序之前，我们需要先完成两个有序数组的归并操作，即将两个有序的数组合并成一个有序的数组；

在此过程中我们需要引入一个辅助数组；
定义的方法签名为 merge(a, lo, mid, hi)，这个方法将数组 a[lo..mid]与 a[mid..hi]归并成一个有序的数组，结果存放到 a[lo..mid]中；
该方法中需要使用的上一篇中的公共函数 less ，参考上一篇文章《常见的初级排序算法，这次全搞懂》

public class MergeSort implements SortTemplate {    private Comparable[] aux;
    @Override    public void sort(Comparable[] array) {        //待实现    }
    private void merge(Comparable[] a, int lo, int mid, int hi) {        for (int i = lo; i <= hi; i++) {            aux[i] = a[i];        }        int i = lo, j = mid + 1;        for (int k = lo; k <= hi; k++) {            if (i > mid) {                a[k] = aux[j++];            } else if (j > hi) {                a[k] = aux[i++];            } else if (less(aux[i], aux[j])) {                a[k] = aux[i++];            } else {                a[k] = aux[j++];            }        }    }
}

复制代码

自顶向下的归并排序

基于分而治之的思想，大的数组排序，先递归拆分成小的数组，保证小的数组有序再归并，直到整个数组有序，这个操作就是自顶向下的归并排序

public class MergeSort implements SortTemplate {    private Comparable[] aux;
    @Override    public void sort(Comparable[] array) {        aux = new Comparable[array.length];        doSort(array, 0, array.length - 1);    }
    private void doSort(Comparable[] array, int lo, int hi) {        if (lo >= hi) {            return;        }        int mid = (hi - lo) / 2 + lo;        doSort(array, lo, mid);        doSort(array, mid + 1, hi);        merge(array, lo, mid, hi);    }
    private void merge(Comparable[] a, int lo, int mid, int hi) {        //省略    }
}

复制代码

以上代码是标准的递归归并排序操作，但是经过仔细思考之后，该算法还有可以优化的地方

测试数组是否已经有序；如果 a[mid]<=a[mid+1]，那么我们就可以跳过 merge 方法，减少 merge 操作；修复之后的 doSort 方法

private void doSort(Comparable[] array, int lo, int hi) {    if (lo >= hi) {        return;    }    int mid = (hi - lo) / 2 + lo;    doSort(array, lo, mid);    doSort(array, mid + 1, hi);    if (array[mid].compareTo(array[mid + 1]) >= 0) {        merge(array, lo, mid, hi);    }}

复制代码

对于小规模的数组可以是用插入排序；对于小规模的数组使用归并排序会增加递归调用栈，所以我们可以考虑使用插入排序来处理子数组的排序

private void doSort(Comparable[] array, int lo, int hi) {    if (lo >= hi) {        return;    }
    if (hi - lo < 5) { //测试，小于5就使用插入排序        insertionSort(array, lo, hi);        return;    }
    int mid = (hi - lo) / 2 + lo;    doSort(array, lo, mid);    doSort(array, mid + 1, hi);    if (less(array[mid + 1], array[mid])) {        merge(array, lo, mid, hi);    }}
//插入排序private void insertionSort(Comparable[] array, int lo, int hi) {    for (int i = lo; i <= hi; i++) {        for (int j = i; j > lo && less(array[j], array[j - 1]); j--) {            exch(array, j, j - 1);        }    }}

复制代码

节省复制元素到辅助数组的时间；要实现该操作较麻烦，需要在每一层递归的时候交换输入数据和输出数组的角色；修改之后的完整代码如下：

public class MergeSort implements SortTemplate {    private Comparable[] aux;
    @Override    public void sort(Comparable[] array) {        aux = array.clone();        doSort(aux, array, 0, array.length - 1);    }
    private void doSort(Comparable[] src, Comparable[] dest, int lo, int hi) {        if (lo >= hi) {            return;        }
        if (hi - lo < 5) { //测试，小于5就使用插入排序            insertionSort(dest, lo, hi);            return;        }
        int mid = (hi - lo) / 2 + lo;        doSort(dest, src, lo, mid);        doSort(dest, src, mid + 1, hi);        if (less(src[mid + 1], src[mid])) {            merge(src, dest, lo, mid, hi);        }    }
    //插入排序    private void insertionSort(Comparable[] array, int lo, int hi) {        for (int i = lo; i <= hi; i++) {            for (int j = i; j > lo && less(array[j], array[j - 1]); j--) {                exch(array, j, j - 1);            }        }    }
    private void merge(Comparable[] src, Comparable[] dest, int lo, int mid, int hi) {        int i = lo, j = mid + 1;        for (int k = lo; k <= hi; k++) {            if (i > mid) {                dest[k] = src[j++];            } else if (j > hi) {                dest[k] = src[i++];            } else if (less(src[i], src[j])) {                dest[k] = src[i++];            } else {                dest[k] = src[j++];            }        }    }
}

复制代码

每一层递归操作都会让子数组有序，但是子数组可能是 aux[lo..hi]也有可能是 a[lo..hi]；由于第一次调用 doSort 传入的是 src=aux，dest=array，所以递归最后的结果一定是输入到了 array 中，保证了 array 整体排序完成

自底向上的归并排序

实现归并算法还有另一种思路，就是先归并哪些小的数组，然后再成对归并得到子数组，直到整个数组有序

public class MergeSort implements SortTemplate {    private Comparable[] aux;
    @Override    public void sort(Comparable[] array) {        int length = array.length;        aux = new Comparable[length];        for (int sz = 1; sz < length; sz += sz) {            for (int i = 0; i < length - sz; i += 2 * sz) {                merge(array, i, i + sz - 1, Math.min(i + 2 * sz - 1, length - 1));            }        }    }
    private void merge(Comparable[] a, int lo, int mid, int hi) {        for (int i = lo; i <= hi; i++) {            aux[i] = a[i];        }        int i = lo, j = mid + 1;        for (int k = lo; k <= hi; k++) {            if (i > mid) {                a[k] = aux[j++];            } else if (j > hi) {                a[k] = aux[i++];            } else if (less(aux[i], aux[j])) {                a[k] = aux[i++];            } else {                a[k] = aux[j++];            }        }    }
}

复制代码

最后（点关注，不迷路）

文中或许会存在或多或少的不足、错误之处，有建议或者意见也非常欢迎大家在评论交流。

最后，写作不易，请不要白嫖我哟，希望朋友们可以点赞评论关注三连，因为这些就是我分享的全部动力来源🙏

文中所有源码已放入到了 github 仓库https://github.com/silently9527/JavaCore

发布于: 2021 年 03 月 04 日阅读数: 10

原文链接:【http://xie.infoq.cn/article/ecd63294a2e963ad8b0881bf6】。文章转载请联系作者。

Silently9527

关注

公众号：贝塔学JAVA 2018.05.09 加入

Simple Programmer, Make the complex simple

发布

暂无评论

创作场景

死磕归并排序算法

前言

归并排序算法思路

原地归并实现

自顶向下的归并排序

自底向上的归并排序

最后（点关注，不迷路）

Silently9527

评论