归并排序Java版（图文并茂思路分析）

2023-05-25 12:24 由翰林猿发表于 #其他

归并排序

工作原理:

工作原理是将一个大问题分解成小问题，再将小问题分解成更小的。（乍一看就觉得是像一个递归）就像下图这样。然后不断的将其一份为二，分解成更小的排序。

我们设一个函数叫MergeSort（arr，l，r）意思就是将arr数组下标为[ l ，r ]之间的数进行排序。

那么就开始不断的调用自己，从而不断的将数组一分为二

int mid = ( l + r ) / 2;
MergeSort( arr, l , mid );
MergeSort( arr, mid+1 , r);

其次我们的递归出口应该就是在变化的参数l > r 的时候，由于没有什么返回值，直接return就好了

if (l >= r) return;

最后我们要将分开的数组重新组合起来，所以我们还需要一个函数，我们就叫它merge（arr，l，mid，r）吧，我们来思考一下如何将两个数组合并起来呢

我们先来看一个问题，怎么把ab两个数组合并成有序的？

很简单的思路，从左右遍各拿一个出来对比，把小的放进有序数组就好了。比如先把左边的1和右边的2拿出来对比，发现1小，便把1放入新数组。

然后再将未放入的2和左边的3对比，发现2小，把2放进新数组，以此类推...

所以回到我们的归并排序，我们怎么实现上面的思路呢？

首先我们要先复制一个数组出来，保证有一个数组作为参考，另一个作为上面所谓的新数组，把拿出来的值覆盖掉另一个即可。然后发现我们这只有一个数组啊，怎么变成两个数组呢 —> 用3个点将数组分为2段就好了

所以此时此刻，我们只需要将i和j拿出来进行对比，然后将小的覆盖到传进来的原数组即可（也就是把上图的第一行数组覆盖了）

优化前:

package com.sort;
import java.util.Arrays;

/**
 * @Author: 翰林猿
 * @Description: 归并排序
 **/
public class Merge {
    public Merge() {
    }

    public static <E extends Comparable<E>> void Mergesort(E[] arr, int l, int r) {
        if (l >= r) 
            return;
        int mid = l +(r - l) / 2;
        Mergesort(arr, l, mid);
        Mergesort(arr, mid + 1, r);
        Merge(arr, l, mid, r);
    }

    public static <E extends Comparable<E>> void Merge(E[] arr, int l, int mid, int r) {
        //先把数组复制一个
        E[] copyArr = Arrays.copyOfRange(arr, l, r+1);
        //用两个变量记住第一个下标l和中间的下标mid+1将数组一分为二
        int i = l;
        int j = mid + 1;
        //走一遍数组，每轮都为arr[k]赋值，arr[k]最后是拿来按顺序覆盖传进来的原数组arr的从而形成排序
        for (int k = l; k <= r; k++) {
            //判断一下i是否越界，如果越界了，说明左边数组遍历完毕
            // 就应当将临时数组的j处的值赋给arr[k]（也就是直接将目前右边数组遍历到的值赋给arr[k])
            //但是由于有偏移，比如说l是3，mid是6，r是9，其实存在copyarr里的下标是0，3，6
            //所以我们要用j-l计算偏移过后的真正下标
            if (i > mid) {
                arr[k] = copyArr[j - l];
                j++;                                //为了再下一次循环就可以只遍历我们的另一个数组了
            } else if (j > r) {                      //如果是j下标越界了，说明右边数组遍历完毕，将左边目前遍历到的值返回
                arr[k] = copyArr[i - l];            //同上
                i++;
            } else if (copyArr[i - l].compareTo(copyArr[j - l]) <= 0) {        //说明两边都没有越界，对比i和j并将小的赋给k，然后i++
                arr[k] = copyArr[i - l];                                       //左边小，把左边赋给k
                i++;
            } else {                                                           //右边小，把右边赋给k
                arr[k] = copyArr[j - l];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        Integer[] arr = {3, 2, 1, 4, 5};
        Merge.Mergesort(arr, 0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

优化思路:

很多人其实不知道如何去优化一个算法，在这里总结几个方向给大家看看，这里主要是指排序类的算法。

个人认为优化其实就是去考虑一些边界和极端现象及内存浪费造成的性能损耗

极端有序情况优化：
- 如果给出的序列本身就是一个有序的，如何让算法减少遍历的次数甚至跳过？
- 如果给出的序列很短，造成序列已经有序的数字概率很大，如何让算法不再重新将已经有序的数字重新再排序造成的性能损耗？
这两个其实本质差不多，都是解决序列本身就有序或者接近有序怎么办。

这里考虑两个方案：
1. 用 i f 语句在某处进行判断是否已经有序之类的，如果有序就不再遍历下去。比如说这样：
```
//优化一下，如果左数组和右数组连接的中间那两个数字已经有序，说明没必要再遍历下去了
if (arr[mid].compareTo(arr[mid + 1]) > 0) {        
            Merge(arr, l, mid, r);
}
```
2. 当序列很短时，我们使用对于短数组来说更快的算法。比如说当数组小于15个时使用复杂度为O(n)的插入排序
```
if (r - l <= 15) {
    Insert.InsertSortForMerge(arr, l, r);
    return;
}
```
内存浪费优化
- 考虑一下我们的算法中间有没有反复创建新的空间，导致内存不断占用之类的？
  
  比如说我们在复制数组的时候，其实一直在反复调用，这种情况我们可以把它提到上一层去，然后将其当作一个参数传给下面调用者。这样无需在调用者种反复复制数组，完成内存操作优化。

到这里，其实我们的优化还没有完成，我们只是将一个arr这么大的数组空间重复利用了，但是内容还没有拷贝，我们可以使用这段代码将内容也拷贝进去。同时还顺便解决了偏移量的问题，不再需要老是减一个 L 了

System.arraycopy(arr, l, copyArr, l, r - l + 1);

优化后代码：

package com.sort;
import java.util.Arrays;

/**
 * @Author: 翰林猿
 * @Description: 归并排序
 **/
public class Merge {
    public Merge() {
    }

    public static <E extends Comparable<E>> void Mergesort(E[] arr, int l, int r) {
        //将copy出来的arr提到上一层来，这样不必反复copy数组，节约内存空间。
        E[] copyArr = Arrays.copyOf(arr, arr.length);
        if (r - l <= 15) {
            Insert.InsertSortForMerge(arr, l, r);
            return;
        }
        int mid = l + (r - l) / 2;
        Mergesort(arr, l, mid);
        Mergesort(arr, mid + 1, r);
        if (arr[mid].compareTo(arr[mid + 1]) > 0) {         //优化一下，如果左数组和右数组连接的中间那两个数字已经有序，说明没必要再遍历下去了
            Merge(arr, l, mid, r, copyArr);
        }
    }

    public static <E extends Comparable<E>> void Merge(E[] arr, int l, int mid, int r, E[] copyArr) {
        //先把数组复制一个
        //E[] copyArr = Arrays.copyOfRange(arr, l, r + 1);      优化到上面
        System.arraycopy(arr, l, copyArr, l, r - l + 1);


        //用两个变量记住第一个下标l和中间的下标mid+1将数组一分为二
        int i = l;
        int j = mid + 1;
        //走一遍数组，每轮都为arr[k]赋值，arr[k]最后是拿来按顺序覆盖传进来的原数组arr的从而形成排序
        for (int k = l; k <= r; k++) {
            //判断一下i是否越界，如果越界了，说明左边数组遍历完毕
            // 就应当将临时数组的j处的值赋给arr[k]（也就是直接将目前右边数组遍历到的值赋给arr[k])
            //但是由于有偏移，比如说l是3，mid是6，r是9，其实存在copyarr里的下标是0，3，6
            //所以我们要用j-l计算偏移过后的真正下标
            if (i > mid) {
                arr[k] = copyArr[j];
                j++;                                //为了再下一次循环就可以只遍历我们的另一个数组了
            } else if (j > r) {                      //如果是j下标越界了，说明右边数组遍历完毕，将左边目前遍历到的值返回
                arr[k] = copyArr[i];            //同上
                i++;
            } else if (copyArr[i].compareTo(copyArr[j]) <= 0) {        //说明两边都没有越界，对比i和j并将小的赋给k，然后i++
                arr[k] = copyArr[i];                                       //左边小，把左边赋给k
                i++;
            } else {                                                           //右边小，把右边赋给k
                arr[k] = copyArr[j];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        Integer[] arr = {3, 2, 1, 4, 5, 9, 19, 15, 18};
        Merge.Mergesort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

归并排序

工作原理:

优化前:

优化思路:

极端有序情况优化：

内存浪费优化

优化后代码：