✨hello，愿意点进来的小伙伴们，你们好呐！
✨ 🐻🐻系列专栏：【数据结构】
🐲🐲本篇内容： 【详解归并排序】
🐯🐯作者简介:一名现大二的三非编程小白

我们今天来看看七大比较排序算法的最后一种 ----- 归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and
Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使
子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序(递归版)

思路：

1.我们应该要先把一组数据拆成一个个数据。找到数据的中间的数mid，通过中间数划分。

2.先将该数组全部分解出来.

3.分解后，我们就要·对每一个数据进行合并排序。下面我用简图来演示一遍。

4，结合后成为有序的数组。

Java代码如下（递归版）：

public class TestMergeSort {
    public static void main(String[] args) {
        int[] array = {5,4,3,2,1};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void mergeSort(int[] array){
        mergeSortChild(array,0, array.length - 1);
    }

    public static void mergeSortChild(int[] array,int left,int right){
        if(left >= right){
            return;
        }

        int mid = (left + right) / 2;
        mergeSortChild(array,left,mid);
        mergeSortChild(array,mid + 1,right);

        merge(array,left,right,mid);
    }

    public static void merge(int[] array,int left,int right,int mid){

        //定义变量来合并成有序数组用到
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;

        int[] tmpArr = new int[right - left + 1];
        int k = 0;
        //循环判断存入新数组中
        while(s1 <= e1 && s2 <= e2){
            if(array[s1] < array[s2]){
                tmpArr[k++] = array[s1++];
            }else{
                tmpArr[k++] = array[s2++];
            }
        }
        //将剩余的数据存入数组中
        while(s1 <= e1){
            tmpArr[k++] = array[s1++];
        }
        while(s2 <= e2){
            tmpArr[k++] = array[s2++];
        }
        for(int i = 0;i < tmpArr.length;i++){
            array[i + left] = tmpArr[i];
        }
    }
}

归并排序(非递归版)

思路：

1.我们可以将一个数组以2为一组分开，并进行排序

2.然后再以4为一组进行分组排序

3。最后再分成8个元素一组进行排序，也就是整个数组进行排序

这种思路也是需要用left，mid，right来实现的，那么重点就是怎么找到这三个位置啦，接下来我们来看一下代码的实现

Java代码实现（非递归版）

public class TestMergeSort {
    public static void main(String[] args) {
        int[] array = {5,4,3,2,1};
        mergeNotRecursionSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void mergeNotRecursionSort(int[] array){
        int gap = 1;
        while(gap < array.length){
            for(int i = 0;i < array.length;i += gap * 2){
                int left = i;
                int mid = left + gap - 1;
                int right = mid  + gap;
                //计算left right mid
                //将其进行排序
                if(mid >= array.length){
                    mid = array.length - 1;
                }
                if(right >= array.length ){
                    right = array.length - 1;
                }
                merge(array,left,right,mid);
            }
            gap *= 2;
        }
    }
    ublic static void merge(int[] array,int left,int right,int mid){

        //定义变量来合并成有序数组用到
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;

        int[] tmpArr = new int[right - left + 1];
        int k = 0;
        //循环判断存入新数组中
        while(s1 <= e1 && s2 <= e2){
            if(array[s1] < array[s2]){
                tmpArr[k++] = array[s1++];
            }else{
                tmpArr[k++] = array[s2++];
            }
        }
        //将剩余的数据存入数组中
        while(s1 <= e1){
            tmpArr[k++] = array[s1++];
        }
        while(s2 <= e2){
            tmpArr[k++] = array[s2++];
        }

        for(int i = 0;i < tmpArr.length;i++){
            array[i + left] = tmpArr[i];
        }

    }

}

归并排序总结：

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

下面我们来看看磁盘问题究竟是什么

海量数据的排序问题：

场景：

我们有100G的文件需要对它进行排序，但是电脑内存只有1G。

解决方法：

因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
1. 先把文件切分成 200 份，每个 512 M.
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了。