Merge Sort - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

入门链接

归并排序算法讲解 归并排序 马士兵说:代码分析归并排序算法的时间复杂度

图解

详解

图解排序算法(四)之归并排序 [图解] 归并排序 【算法】排序算法之归并排序 归并排序详解(MergeSort)递归和非递归实现 归并排序时间复杂度过程分析 [数据结构与算法] 排序(三) 平均时间复杂度O(nlogn) 归并排序的空间复杂度为什么是O(n)?快速排序的空间复杂度为什么是O(log2n)? 归并排序的空间复杂度优化——手摇算法(内存反转算法) 空间复杂度为O(1),时间复杂度为O(nlogn)的归并排序

标准写法(递归版本 自上而下)

步骤1: 归并排序的核心,把一个前半部分和后半部分都有序的数组切分成两半

public static void merge(int[] arr, int left, int middle, int right) {
    // 例:2, 24, 44, 45, 56, 37, 44, 50, 61, 66
    // leftArr = [2, 24, 44, 45, 56], rightArr = [37, 44, 50, 61, 66]
    // 例:2, 24, 44, 45, 56, 71, 37, 44, 50, 61, 66
    // leftSize = [2, 24, 44, 45, 56, 71], rightSize = [37, 44, 50, 61, 66]
    // fullSize = leftSize + rightSize 
    // = middle - left + 1 + right - middle = right - left + 1
    // 别忘了 + 1
    int leftSize = middle - left + 1;
    int rightSize = right - middle;
    int[] leftArr = new int[leftSize];
    int[] rightArr = new int[rightSize];

    for (int i = 0; i < leftSize; i++) {
        leftArr[i] = arr[i];
    }

    for (int j = 0; i < rightSize; j++) {
        rightArr[j] = arr[leftSize + j];
    }
}

步骤2: 细节处理

public static void merge(int[] arr, int left, int middle, int right) {
    // 例:2, 24, 44, 45, 56, 37, 44, 50, 61, 66
    // leftArr = [2, 24, 44, 45, 56], rightArr = [37, 44, 50, 61, 66]
    // 例:2, 24, 44, 45, 56, 71, 37, 44, 50, 61, 66
    // leftSize = [2, 24, 44, 45, 56, 71], rightSize = [37, 44, 50, 61, 66]
    // fullSize = leftSize + rightSize
    // = middle - left + 1 + right - middle = right - left + 1
    // 别忘了 + 1
    int leftSize = middle - left + 1;
    int rightSize = right - middle;
    int[] leftArr = new int[leftSize];
    int[] rightArr = new int[rightSize];

    // 注意用i = left,而不是i = 0;用j = middle + 1,而不是j = 0
    // 是因为我们始终都只是在操作arr这个数组
    // 用left,middle,right这三个变量来控制arr数组中某一个片段
    for (int i = left; i <= middle; i++) {
        leftArr[i - left] = arr[i];
    }

    for (int j = middle + 1; j <= right; j++) {
        rightArr[j - middle - 1] = arr[j];
    }
}

步骤3: 归并排序的核心,把两个有序的数组合并成一个有序的数组

public static void merge(int[] arr, int left, int middle, int right) {
    // 例:2, 24, 44, 45, 56, 37, 44, 50, 61, 66
    // leftArr = [2, 24, 44, 45, 56], rightArr = [37, 44, 50, 61, 66]
    // 例:2, 24, 44, 45, 56, 71, 37, 44, 50, 61, 66
    // leftSize = [2, 24, 44, 45, 56, 71], rightSize = [37, 44, 50, 61, 66]
    // fullSize = leftSize + rightSize
    // = middle - left + 1 + right - middle = right - left + 1
    // 别忘了 + 1
    int leftSize = middle - left + 1;
    int rightSize = right - middle;
    int[] leftArr = new int[leftSize];
    int[] rightArr = new int[rightSize];

    // 注意用i = left,而不是i = 0;用j = middle + 1,而不是j = 0
    // 是因为我们始终都只是在操作arr这个数组
    // 用left,middle,right这三个变量来控制arr数组中某一个片段
    for (int i = left; i <= middle; i++) {
        leftArr[i - left] = arr[i];
    }

    for (int j = middle + 1; j <= right; j++) {
        rightArr[j - middle - 1] = arr[j];
    }

    // 把两个数组排序,合并成一个数组,并更新原数组
    // 比较方法:从两个数组的头部开始,哪个元素小就先把哪个元素放进去新的数组
    // 注意这里k不是从0开始,正如前面所说,我们始终都只是在操作arr这个数组中的片段
    // 未必是从0开始
    int i = 0, j = 0, k = left;
    while (i < leftSize && j < rightSize) {
        if (leftArr[i] < rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    // 两个数组其中一个剩下的元素直接放进去新的数组
    while (i < leftSize) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }
    while (j < rightSize) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

步骤4: 归并排序的核心,递归思想,通过递归不断切割数组

public static void mergeSort(int[] arr, int left, int right) {
    // 例:2, 24, 44, 45, 56, 37, 44, 50, 61, 66
    // arr[left] = 2
    // arr[middle] = 56
    // arr[middle + 1] = 37
    // arr[right] = 66
    int middle = left + (right - left) / 2;
    //把arr进行分割
    mergeSort(arr, left, middle);
    mergeSort(arr, middle + 1, right);
    // 分割完后合并
    merge(arr, left, middle, right);
}

步骤5: 增加递归终止条件,完成递归

public static void mergeSort(int[] arr, int left, int right) {
    // 剩下一个元素时停止
    if (left == right) {
        return;
    }
    // 例:2, 24, 44, 45, 56, 37, 44, 50, 61, 66
    // arr[left] = 2
    // arr[middle] = 56
    // arr[middle + 1] = 37
    // arr[right] = 66
    int middle = left + (right - left) / 2;
    //把arr进行分割
    mergeSort(arr, left, middle);
    mergeSort(arr, middle + 1, right);
    // 分割完后合并
    merge(arr, left, middle, right);
}

标准写法(迭代版本 自下而上)

就像金字塔一样从下往上排序,合并数组

43, 56, 98, 31, 33, 13, 65, 13, 1, 87, 65 43, 56, 98, 31, 33, 13, 65, 13 | 1, 87, 65 43, 56, 98, 31 | 33, 13, 65, 13 | 1, 87, 65 43, 56 | 98, 31 | 33, 13 | 65, 13 | 1, 87 | 65 43 | 56 | 98 | 31 | 33 | 13 | 65 | 13 | 1 | 87 | 65

public static void mergeSort(int[] arr) {
    // len表示归并子数组的长度,1表示,一个一个的归并;
    // 归并后的长度为2,2表示两个两个的归并,归并后的长度为4,以此类推
    // 例:43, 56, 98, 31, 33, 13, 65, 13, 1, 87, 65
    // len = 1:43 | 56 | 98 | 31 | 33 | 13 | 65 | 13 | 1 | 87 | 65
    // len = 2:43, 56 | 98, 31 | 33, 13 | 65, 13 | 1, 87 | 65
    // ...
    int len, start;
    // len = 2 * len代表两倍增长
    for (len = 1; len < arr.length; len = 2 * len) {
        // 按照len的长度归并回arr数组,归并后长度翻倍
        // start = start + 2 * len代表两倍增长
        // 例如上面的例子,len = 1时,每归并一次(完成43, 56),
        // 就往右边移动两格(继续完成98, 31),以此类推
        for (start = 0; start < arr.length; start = start + 2 * len) {
            if (start + len - 1 > arr.length - 1) {
                // 注意一下情况:43, 56, 98, 31 | 33, 13, 65, 13 | 1, 87, 65
                // 对于最后一组 1, 87, 65
                // 此时start是8,len是4,超过了长度,所以middle的值和right的值就不能直接 + len
                merge(arr, start, start + (arr.length - 1 - start) / 2, arr.length - 1);
            } else {
                // 此时start + 2 * len - 1已经超过数组长度,right的取值就应该只能去arr.length - 1
                merge(arr, start, start + len - 1, Math.min(start + 2 * len - 1, arr.length - 1));
            }
        }
    }
}

时间复杂度分析

空间复杂度分析

写法1:空间复杂度 S(n) = 2S(n/2) + n = O(nlogn)

public static int[] mergeSort(int[] arr, int left, int right) {
    if (n = 1) then return;
    else:
        int middle = left + (right - left) / 2;
        int[] leftArr = mergeSort(arr, left, middle);
        int[] rightArr = mergeSort(arr, middle + 1, right);
        // 返回leftArr和rightArr合并后的结果
        // 这种写法会导致合并时分配的空间无法释放
        return merge(leftArr, rightArr, middle); 
}

写法2:空间复杂度 S(n) = 2S(n/2) + O(1) = O(n),与上面的标准写法类似,需要一个辅助数组

public static void mergeSort(int[] arr, int left, int right, int[] tempArray) {
    if (left = right) then return;
    else:
        int middle = left + (right - left) / 2;
        mergeSort(arr, left, middle, tempArray);
        mergeSort(arr, middle + 1, right, tempArray);
        // 数组arr中从begin到mid是排好序的,从mid+1到end也是排好序的
        // 现在需要把这两个部分合并,并把合并结果储存在tempArray中
        merge(arr, left, middle, right, tempArray);
        // 把tempArray的合并结果复制到arr中
        copy(tempArray, arr, begin, end);
}

写法2优化:通过交换arr1和arr2,节省copy步骤

public static void mergeSort(int[] arr1, int[] arr2, int left, int right) {
    if (left = right) then return;
    else:
        int middle = left + (right - left) / 2;
        mergeSort(arr2, arr1, left, middle);
        mergeSort(arr2, arr1, middle + 1, right);
        // 每次mergeSort结束,数组arr1中从begin到mid是排好序的,从mid+1到end也是排好序的
        // 现在需要把这两个部分合并,并把合并结果储存在arr2中
        merge(arr1, arr2, left, middle, right);
}

递归步骤分析

要点

  • N个节点完全二叉树的高度:log2N + 1
  • 既可以升序排序,也可以降序排序,把merge方法中的if中的 leftArr[i] < rightArr[j] 改为 leftArr[i] > rightArr[j] 即可
  • 最好时间复杂度是O(nlogn);平均时间复杂度是O(nlogn);最坏时间复杂度是O(nlogn)
  • 空间复杂度O(n),每次合并都需要一个额外的辅助数组,合并完后该数组就会被销毁
  • 什么时候使用插入排序而不是归并排序?
    • 空间有限
    • 有大的内存缓存
    • 数组中几乎是有序