排序第四节——归并排序（附有自己的视频讲解）

2.4 归并排序

***视频讲解

模板

    /** * 时间复杂度：O(n*logn) * 空间复杂度：O(n) * 稳定性：稳定排序 * 直接插入 冒泡 归并 * @param array */
    public static void mergerSort1(int[] array) {
    
        mergeSortFunc(array,0,array.length-1);
    }
    private static void mergeSortFunc(int[] array,int left,int right) {
    

        if(left >= right) {
    
            return;
        }

        int mid = (left+right) / 2;
        //1、分解左边
        mergeSortFunc(array,left,mid);
        //2、分解右边
        mergeSortFunc(array,mid+1,right);
        //3、进行合并
        merge(array,left,right,mid);
    }
    
    private static void merge(int[] array,int start,int end,
                              int midIndex) {
    

        int[] tmpArr = new int[end-start+1];
        int k = 0;//tmpArr数组的下标

        int s1 = start;
        int s2 = midIndex+1;

        //两个归并段 都有数据
        while (s1 <= midIndex && s2 <= end) {
    
            if(array[s1] <= array[s2]) {
    
                tmpArr[k++] = array[s1++];
            }else {
    
                tmpArr[k++] = array[s2++];
            }
        }

        //当走到这里的时候 说明 有个归并段 当中 没有了数据 ，拷贝另一半的全部 到tmpArr数组当中
        while (s1 <= midIndex) {
    
            tmpArr[k++] = array[s1++];
        }

        while (s2 <= end) {
    
            tmpArr[k++] = array[s2++];
        }
        //把排好序的数字 拷贝回 原数组
        for (int i = 0; i < k; i++) {
    
            array[i+start] = tmpArr[i];
        }
    }

2.4.1 基本思想

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

非递归模板

    public static void mergerSort(int[] array) {
    

        int gap = 1;//每组的数据

        while (gap < array.length) {
    

            for (int i = 0; i < array.length; i += gap*2 ) {
    
                //进入这个循环 i一定合法
                int s1 = i;
                int e1 = s1+gap-1;
                if(e1 >= array.length) {
    
                    e1 = array.length-1;
                }
                int s2 = e1+1;
                if(s2 >= array.length) {
    
                    s2 = array.length-1;
                }/**/
                int e2 = s2+gap-1;
                //int e2 = e1+gap;
                if(e2 >= array.length) {
    
                    e2 = array.length-1;
                }
                merge(array,s1,e2,e1);
            }
            gap *= 2;
        }
    }

2.4.2 归并排序总结

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

2.4.3 海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序

1. 先把文件切分成 200 份，每个 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了