与归并排序相关的一些问题

与归并排序相关的一些问题

作者:Grey

原文地址:

博客园:与归并排序相关的一些问题

CSDN:与归并排序相关的一些问题

归并排序的递归解法

插入,选择,冒泡排序时间复杂度是O(N^2),归并排序可以做到时间复杂度O(N*logN)

归并排序的整体思路是利用递归,先让左边排好序,再让右边排好序,然后通过merge操作让整体有序。

merge操作类似合并两个及以上有序链表问题中提到的算法。

但是merge过程需要辅助数组,所以额外空间复杂度为O(N)

完整代码和注释见:

public class Code_MergeSort {

    // 递归方法实现
    public static void mergeSort1(int[] arr) {
        if (arr == null || arr.length > 1);
        // 左边部分有序
        process(arr, l, mid);
        // 右边部分有序
        process(arr, mid + 1, r);
        // 整体变有序
        merge(arr, l, mid, r);
    }
    // arr[l...mid]已经有序
    // arr[mid+1...r]也已经有序
    // 将arr[l...r]整体变有序
    public static void merge(int[] arr, int l, int mid, int r) {
        // 辅助数组
        int[] help = new int[r - l + 1];
        int ls = l;
        int rs = mid + 1;
        int i = 0;
        while (ls 

这个递归过程时间复杂度可以利用 master 公式来计算。

T(N) = 2*T(N/2) + O(N^1)

故上述算法时间复杂度为O(N*logN)

归并排序的迭代版本实现

因为任何递归函数都可以用非递归函数来实现,所以,归并排序有对应的迭代方法,思路如下

  1. 设置一个步长,从 1 开始,1,2,4,8,16....2^n 方式递增
  2. 每次处理对应步长的数组区间范围内的排序。
  3. 步长超过或者等于数组长度,则整个数组排序完成。

比如[1,3,4,2,5,6,4,6,8]

先设置步长为 1,数组分成如下区间

[0...1],[2...3],[4...5],[6...7],[8...8]

注:最后一组不够分,则单独作为一组处理。

将如上区间内部排好序,得到的数组为

[1,3,2,4,5,6,4,6,8]

然后设置步长为 2,数组分成如下区间

[0...3],[4...7],[8...8]

然后将上述区间内部先排好序,得到数组为

[1,2,3,4,4,5,6,6,8]

然后设置步长为 4,数组分成如下区间

[0...7],[8...8]

然后将上述区间内部先排好序,得到数组为

[1,2,3,4,4,5,6,6,8]

最后设置步长为 8,数组只有一个区间,直接排序,得到最后结果

[1,2,3,4,4,5,6,6,8]

完整代码见


public class Code_MergeSort {

    // 归并排序的迭代版
    public static void mergeSort2(int[] arr) {
        if (arr == null || arr.length = len) {
                    // 没有右组
                    break;
                }
                int mid = lStart + step - 1;
                // rEnd不能越界
                int rEnd = mid + Math.min(step, len - mid - 1);
                // 右组中第一个位置
                // 中点位置
                merge(arr, lStart, mid, rEnd);
                lStart = rEnd + 1;
            }
            // 防止溢出
            if (step > (len / 2)) {
                break;
            }
            step 

合并有序数组

题目描述见LeetCode 88. Merge Sorted Array

本题思路就是归并排序的merge过程,不赘述,代码如下

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int len = m + n;
        while (m > 0 && n > 0) {
            if (nums1[m - 1] > nums2[n - 1]) {
                nums1[--len] = nums1[--m];
            } else {
                nums1[--len] = nums2[--n];
            }
        }
        while (n > 0) {
            nums1[--len] = nums2[--n];
        }
    }
}

注:本题在 LintCode 中也有,见LintCode 6 · Merge Two Sorted Arrays

在 LintCode 中,对本题有个扩展要求:

如果一个数组很大,另一个数组很小,你将如何优化算法?

对于扩展要求,我们可以用如下方式来优化

即直接查小数组中的元素在大数组中的位置(可以用二分),然后依次填入具体位置

完整代码见

public class Solution {

    public static int[] mergeSortedArray(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        int[] bigger = m >= n ? A : B;
        int[] smaller = bigger == A ? B : A;
        int[] helper = new int[m + n];
        int from = 0;
        int to;
        int index = 0;
        for (int i = 0; i > 1);
            if (bigger[mid] > value) {
                R = mid - 1;
            } else if (bigger[mid] 

计算右侧小于当前元素的个数问题

题目描述见:LeetCode 315. Count of Smaller Numbers After Self

本题也是利用了归并排序的merge过程,由于归并排序是从小到大排序,而我们需要得到某个元素右侧有多少比它小,所以我们还需要将归并排序改成从大到小排序。

以某一次merge过程为例,比如

左侧区间(已排好序): [5,3,2,1]

右侧区间(已排好序):[6,4,3,3]

示例图如下

与归并排序相关的一些问题插图

当左侧指针来到s1的时候,右侧指针移动到s2的时候,开始比左侧的值要小,此时可以结算s1位置右侧有几个比它小的元素。

左侧组中比 s1 更小的元素个数 + (r - s2 + 1)

完整代码见:

class Solution {
   public static class Node {
        public int value;
        public int index;

        public Node(int index, int value) {
            this.value = value;
            this.index = index;
        }
    }

    // 思路转换为:一个数的右边有多少个数比它小!
    // 改归并排序(从大到小)
    public static List countSmaller(int[] nums) {
        List result = new ArrayList(nums.length);
        Node[] nodes = new Node[nums.length];
        for (int i = 0; i  result) {
        if (l == r) {
            return;
        }
        int m = l + ((r - l) >> 1);
        process(nodes, l, m, result);
        process(nodes, m + 1, r, result);
        merge(nodes, l, m, r, result);
    }

    private static void merge(Node[] nodes, int l, int m, int r, List result) {
        Node[] help = new Node[r - l + 1];
        int s1 = l;
        int s2 = m + 1;
        int index = 0;
        while (s1  nodes[s2].value) {
                result.set(nodes[s1].index, result.get(nodes[s1].index) + r - s2 + 1);
                help[index++] = nodes[s1++];
            } else if (nodes[s1].value 

LintCode上有一个类似的题目,题目描述见:LintCode 532 · Reverse Pairs

本题的思路和上一题一致,都是先将归并排序改成从大到小排序,然后在merge过程中,求一个数右侧有几个数比它小,不赘述,代码见:

public class Solution {
   public static long reversePairs(int[] A) {
        if (null == A || A.length > 1);
        return process(a, l, m) + process(a, m + 1, r) + merge(a, l, m, r);
    }

    private static long merge(int[] a, int l, int m, int r) {
        int[] help = new int[r - l + 1];
        int index = 0;
        int s1 = l;
        int s2 = m + 1;
        long ans = 0L;
        while (s1  a[s2]) {
                ans += (r - s2 + 1);
                help[index++] = a[s1++];
            } else {
                help[index++] = a[s2++];
            }
        }
        while (s1 

翻转对问题

题目描述见:LeetCode 493. Reverse Pairs

本题也是利用merge过程,不同于上述两个问题,本题在merge两个区间之前,就要先统计一下num[i] > 2 * num[j]的数量。

完整代码见:

class Solution {
   public static int reversePairs(int[] A) {
        if (null == A || A.length > 1);
        return process(a, l, m) + process(a, m + 1, r) + merge(a, l, m, r);
    }

    public static int merge(int[] a, int l, int m, int r) {
        // 先执行统计
        int ans = 0;
        int s1 = l;
        int s2 = m + 1;
        while (s1  (long) a[s2]) {
                ans += (r - s2 + 1);
                s1++;
            } else {
                s2++;
            }
        }
        // 以下是经典mergesort排序
        int[] help = new int[r - l + 1];
        s1 = l;
        s2 = m + 1;
        int index = 0;

        while (s1  a[s2]) {
                help[index++] = a[s1++];
            } else {
                help[index++] = a[s2++];
            }
        }
        while (s1 

区间和的个数问题

题目描述见:LeetCode 327. Count of Range Sum

本题有几个优化点:

  1. 由于需要快速得到区间和,所以,可以通过前缀和数组来加速区间和的求法。
  2. merge过程中,由于存在单调性,所以可以通过滑动窗口的方式,定位到区间和的上下界,整个过程不回退,所以不会增加归并排序的整体时间复杂度。

完整代码和注释见

class Solution {
    public static int countRangeSum(int[] nums, int lower, int upper) {
        int size = nums.length;
        // 前缀和数组加速求区间的和!!
        long[] preSum = new long[size];
        preSum[0] = nums[0];
        for (int i = 1; i = lower && preSum[j] > 1);
        return p(preSum, i, mid, lower, upper) + p(preSum, mid + 1, j, lower, upper) + merge(preSum, i, mid, j, lower, upper);
    }

    private static int merge(long[] preSum, int i, int mid, int j, int lower, int upper) {
        // 单调性->滑动窗口
        int pair = 0;
        int L = i;
        int R = i;
        int S = mid + 1;
        // 区间和存在单调性,使用滑动窗口定位上下界,不回退,所以O(logN)
        while (S  preSum[r]) {
                helper[index++] = preSum[r++];
            } else {
                helper[index++] = preSum[l++];
            }
        }
        while (l 

更多

算法和数据结构笔记

参考资料

算法和数据结构体系班-左程云

文章来源于互联网:与归并排序相关的一些问题

THE END
分享
二维码