Merge Sort 归并排序

什么是归并排序?

归并排序是一种高级排序算法, 时间复杂度为O(NlogN). 归并排序用到了一种重要的算法设计思维: 分治

如下图所示, 归并排序不断地未排序的数组进行二等分, 随后再不断地对一个个子数组进行归并, 归并也就是对两个有序的子数组进行合并, 同时保持合并后的数组有序. 当归并完成时, 整个数组也就有序了.

用代码表示如下:

public class MergeSort {

    //设为private,防止被实例化
    private  MergeSort(){}

    public  static  <E extends Comparable<E> > void sort(E[] arr){
        sort(arr,0,arr.length-1);
    }

    private static  <E extends Comparable<E> > void sort(E[] arr, int l, int r){
        if (l>=r){
            return;
        }
        int mid=l+(r-l)/2; //  等价于(l+r)/2
        sort(arr, l,mid);
        sort(arr,mid+1,r);
        merge(arr,l,mid,r);
    }
}

我们设置了归并排序的接口方法为 sort(E[ ] arr),

设置了归并排序的分治方法为 sort(E[ ] arr, int l, int r) , arr为待处理的数组, l 为数组的左索引, r为数组的右索引. 当数组长度为1时, 说明已经无法继续二等分了, 也就是递归到底了,之间return.

否则继续左右二等分. 当左右数组都已经有序以后, 对两个有序数组进行归并.

归并过程

归并排序最重要的部分就是对两个有序子数组进行归并, 用图表示如下:

我们需要对数组 arr[l, mid] , arr[mide+1, r] 进行归并. 为此我们先复制一份 arr[l, r] 命名为 temp, temp的索引变成从0开始, r-l 结束.

归并的思想也非常简单, 用一句话说就是: 一个个比较两个有序子数组的元素, 将较小的元素归并回原数组, 直到遍历完两个有序子数组的所有元素.

为此,我们在temp中也设置了两个索引指针, i 负责遍历左边的有序子数组, j 负责遍历右边的有序子数组. 在arr 中也设置了一个索引 k, 将归并的元素放入 arr[ k ] 中. 用代码表示如下:

//合并arr[l,mid][,arr[mid+1,r]
private static <E extends Comparable<E> > void merge(E arr[],int l, int mid, int r){
    E[] temp= Arrays.copyOfRange(arr,l,r+1);

    int i=0, j=mid-l+1;

    for (int k = l; k <=r; k++) {
        if (i>mid-l){
            arr[k]=temp[j];
            j++;
            continue;
        }
        if(j>r-l){
            arr[k]=temp[i];
            i++;
            continue;
        }

        //比较arr[i] 和 arr[j]
        if (temp[i].compareTo(temp[j])<=0){
            arr[k]=temp[i];
            i++;
        }else{
            arr[k]=temp[j];
            j++;
        }

    }

}

最后我们在 一百万级别的随机数上 进行测试

public static void main(String[] args) {
        int n =1000000;
        Integer[] arr=ArrayGenerator.generateRandomArray(n,n);//完全随机数据
        //Integer[] arr=ArrayGenerator.generateOrderedArray(n);//完全有序数据
        SortingHelper.sortTest("MergeSort",arr,n);
    }

在我这台八代 i -5 低压的笔记本上, 一百万级别的随机数也仅需0.6秒左右即可完成排序.

性能分析 & 优化

归并排序的时间复杂度为O(NlogN). 这主要是由于, 归并排序不管数据是怎样的,强行将数据进行二等分处理造成的.但实际上, 我们还可以对上面的代码进行优化,使得在一些特殊数据上, 时间复杂度降为O(logN)

对于完全有序的数据

假设数据完全有序, 那么归并的过程是完全没有必要的, 也就是说 temp 数组元素的顺序和 归并后的arr[l, r] 数组的元素顺序是完全相同的. 在这种情况下, 若省略归并过程, 整个排序时间复杂度将只依赖于二分递归的过程, 也就是复杂度降低为O(logN)

代码的修改也非常简单,只需要在进行归并前对两个有序子数组进行简单判断, 若右边子数组的最小值比左边数组的最大值还要大, 则无需归并.

private static  <E extends Comparable<E> > void sort(E[] arr, int l, int r){
    if (l>=r){
        return;
    }
    int mid=l+(r-l)/2; //  等价于(l+r)/2
    sort(arr, l,mid);
    sort(arr,mid+1,r);
    if(arr[mid+1].compareTo(arr[mid])>0){
        return;
    }
    merge(arr,l,mid,r);
}

我们再测试一下完全有序数据

public static void main(String[] args) {
    int n =1000000;
    //Integer[] arr=ArrayGenerator.generateRandomArray(n,n);//完全随机数据
    Integer[] arr=ArrayGenerator.generateOrderedArray(n);//完全有序数据
    SortingHelper.sortTest("MergeSort",arr,n);
}

在我这台八代 i -5 低压的笔记本上, 一百万级别的有序数仅需0.1秒左右即可完成排序.

其他优化

有没有想过我们每一次归并都要一个 复制 临时数组, 而这个临时数组其实是可以复用的, 我们可以用一个与 arr 长度相同的全局数组进行代替, 这样避免了频繁的创建与销毁新数组的开销. 这里的代码就不演示了hhh