七大排序之归并排序

文章目录

七大排序之归并排序
前言
一、算法思路
二、代码实现
三、算法稳定性
四、拓展
- 4.1 海量数据处理：用到外部存储器
- 4.2 归并排序的衍生问题
总结

前言

博主个人社区：开发与算法学习社区

博主个人主页：Killing Vibe的博客

欢迎大家加入，一起交流学习~~

一、算法思路

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

动图如下：

其实就是分为归和并两个过程：

归：不断将原数组拆分为子数组（一分为二），直到每个子数组只剩下一个元素 = 》归过程结束

并：不断合并相邻的两个子数组为一个大的子数组，合并的过程就是将两个已经有序的子数组合并为一

举个栗子：

如下图所示的待排序序列，经过不断的归过程变成了一个个的小数组：

当每个子数组都只剩下一个元素时，每个子数组都是一个有序数组，然后开始两两合并。

如下是并过程：

时间复杂度：稳定O（nlogn）空间复杂度：O（n）

二、代码实现

代码如下：

    private static void mergeSortInternal(int[] arr, int l, int r) {
        // 2.小数组直接使用插入排序
        if (r - l <= 15) {
            insertionSort(arr,l,r);
            return;
        }
        // int mid = (l + r) / 2;
        // l = 2,r = 4  mid = 3 = 2 + (4 - 2) / 2 = 3
        int mid = l + ((r - l) / 2);
        mergeSortInternal(arr,l,mid);
        mergeSortInternal(arr,mid + 1,r);
        // arr[l..mid] 和 arr[mid + 1...r]有序 只需要合并这两个子数组即可
        // 1.到底什么时候才需要合并 arr[mid] < arr[mid + 1] 说明？arr[mid] 数组1的最大值 arr[mid + 1]数组2的最小值
        // 整个数组已经有序了，那你还合并个der
        if (arr[mid] > arr[mid + 1]) {
            // 前后两个子数组还存在乱序，才需要合并
            merge(arr,l,mid,r);
        }
    }


    /**
     * 将有序子数组arr[l..mid] 和 有序arr[mid + 1...r] 合并为一个大的有序数组arr[l..r]
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private static void merge(int[] arr, int l, int mid, int r) {
        // 先创建一个新的数组aux,将子数组的值复制给新数组
        int[] aux = new int[r - l + 1];
        // l = 2,r = 4
        // arr[2..4]
        // aux[0..2] 索引下标差了个l偏移量
        for (int i = 0; i < aux.length; i++) {
            // aux的索引下标0...arr.length - 1
            // arr的下标l...r
            aux[i] = arr[i + l];
        }
        // 数组1的开始下标
        int i = l;
        // 数组2的开始下标
        int j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 第一个数组已经遍历完毕
                arr[k] = aux[j - l];
                j ++;
            }else if (j > r) {
                // 第二个子数组遍历完毕
                arr[k] = aux[i - l];
                i ++;
            }else if (aux[i - l] <= aux[j - l]) {
                // 将aux[i - l]写回arr[k]
                arr[k] = aux[i - l];
                i ++;
            }else {
                // aux[i - l] > aux[j - l] 写回aux[j - l]
                arr[k] = aux[j - l];
                j ++;
            }
        }
    }


    /**
     * 在arr[l..r]上进行插入排序
     * @param arr
     * @param l
     * @param r
     */
    private static void insertionSort(int[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            for (int j = i; j >= l + 1 && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j - 1);
            }
        }
    }