基础算法-归并排序

今天学习相时间复杂度为O(nlogn)的排序算法：归并排序。

题目介绍

题目内容还是没变：给定一个数组，将数组按从小到大顺序排序。题目理解起来也是很容易的，就不再画图介绍了。

归并排序

归并排序的核心思想是，将数组一分为二，先将左边的排序，然后将右边的排序，最后两个数组进行合并则得到有序数组。
继续沿用递归的思想，基于上述描述的基础之上，将两个数组拆分为四个，以此类推，直到待排序的只有一个元素时返回。然后逐次进行合并。

实现代码

因在之前文章实现过排序抽象类，因此归并排序类只要继承抽象类即可。

public class merge extends AbstractSort {

    private Comparable[] tmp;

    @Override
    public void sort(Comparable[] a) {
        tmp = new Comparable[a.length];
        sort(a, 0, a.length - 1);
    }

    /**
     * 对给定数组的下标 lo到hi之间的元素进行排序
     *
     * @param a
     * @param lo
     * @param hi
     */
    private void sort(Comparable[] a, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2; //以中间下标为分割
        sort(a, lo, mid); //对左侧数组进行排序
        sort(a, mid + 1, hi);//对右侧数组进行排序
        merge(a, lo, mid, hi);//将排好序的左右两个数组归并
    }

    private void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;

        //临时数组lo至hi之间的元素赋值
        for (int k = lo; k <= hi; k++) {
            tmp[k] = a[k];
        }

        //归并回a数组
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = a[j++];
            else if (j > hi) a[k] = a[i++];
            else if (less(tmp[j], tmp[i])) a[k] = tmp[j++];
            else a[k] = tmp[i++];
        }
    }

}

算法相关实现源码地址：https://github.com/xiekq/rubs-algorithms