死磕归并排序算法

Silently9527
2021-08-14 / 0 评论 / 26 阅读
温馨提示:
本文最后更新于2021-08-14,若内容或图片失效,请留言反馈。

本文已被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) {
        //省略
    }

}

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

  1. 测试数组是否已经有序;如果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);
    }
}
  1. 对于小规模的数组可以是用插入排序;对于小规模的数组使用归并排序会增加递归调用栈,所以我们可以考虑使用插入排序来处理子数组的排序
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);
        }
    }
}
  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