归并排序(优化与案例)_vlambda技术博客

vlambda
2022-03-09

归并排序(优化与案例)

算法描述

使用归并排序进行升序排列。

示例：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

算法设计

基本思路：借助额外空间，合并两个有序数组，得到更长的有序数组。例如：「力扣」第 88 题：合并两个有序数组。

核心函数：mergeSort函数（分治思想）和merge函数（合并有序数组），分治过程一定情况下可以实现并行化。

算法优化

优化1：小区间采用插入排序

Java 源码里面也有类似这种操作，「小区间」的长度是个超参数，需要测试决定，我这里参考了 JDK 源码；

优化2：两个数组本身有序，无需合并

左边界大于右边界或者要归并的两个数组已经有序，无需进行merge过程。

优化3：全程使用一份临时数组进行两个数组的合并操作

避免创建临时数组和销毁的消耗，避免计算下标偏移量。即使用

System.arraycopy(nums, left, tmp, left, right - left + 1)拷贝到tmp临时数组。

优化4：位运算求解中间值

对Java语言，left + right >>> 1 在可能存在溢出的情况下，结论也是正确的。

代码实现

class Solution {

    // 列表大小大于或等于该值，将优先使用归并排序，否则使用插入排序
    private static final int INSERTION_SORT_THRESHOLD = 7;

    public int[] sortArray(int[] nums) {
        int n = nums.length;
        int[] tmp = new int[n];

        mergeSort(nums, 0, n - 1, tmp);
        return nums;
    }

    private void mergeSort(int[] nums, int left, int right, int[] tmp) {
        if (right - left <= INSERTION_SORT_THRESHOLD) {
            insertionSort(nums, left, right);
            return;
        }

        // int mid = left + (right - left) / 2;
        int mid = left + right >>> 1;
        mergeSort(nums, left, mid, tmp);
        mergeSort(nums, mid + 1, right, tmp);
        // 如果子区间本身有序，则无需合并
        if (nums[mid] <= nums[mid + 1]) {
            return;
        }

        merge(nums, left, mid, right, tmp);
    }

    private void insertionSort(int[] nums, int left, int right) {
        for (int i = left + 1; i <= right; ++i) {
            int tmp = nums[i];
            int j = i;
            while (j > left && nums[j - 1] > tmp) {
                nums[j] = nums[j - 1];
                j--;
            }
            nums[j] = tmp;
        }
    }

    private void merge(int[] nums, int left, int mid, int right, int[] tmp) {
        System.arraycopy(nums, left, tmp, left, right - left + 1);

        int i = left;
        int j = mid + 1;

        for (int k = left; k <= right; k++) {
            if (i == mid + 1) {
                nums[k] = tmp[j];
                j++;
            } else if (j == right + 1) {
                nums[k] = tmp[i];
                i++;
            } else if (tmp[i] <= tmp[j]) {
                // 注意写成 < 就丢失了稳定性（相同元素原来靠前的排序以后依然靠前）
                nums[k] = tmp[i];
                i++;
            } else {
                // tmp[i] > tmp[j]:先放较小的元素
                nums[k] = tmp[j];
                j++;
            }
        }
    }
}

注意点(补充)：

实现归并排序的时候，要特别注意，不要把这个算法实现成非稳定排序，区别就在 <= 和 < ，已在代码中注明。
「归并排序」比「快速排序」好的一点是，它借助了额外空间，可以实现「稳定排序」，Java 里对于「对象数组」的排序任务，就是使用归并排序（的升级版 TimSort，在这里就不多做介绍）。
时间复杂度：O(N log N)，这里 N 是数组的长度；空间复杂度：O(N)，辅助数组与输入数组规模相当。
「归并排序」也有「原地归并排序」和「不使用递归」的归并排序，但是我个人觉得不常用，编码、调试都有一定难度。
经典问题：

《剑指 Offer》第 51 题：数组中的逆序对，照着归并排序的思路就能写出来。
「力扣」第 315 题：计算右侧小于当前元素的个数，它们是一个问题。

应用拓展

示例1：「力扣」第 88 题合并两个有序数组

注意：归并排序的merge过程，但是考虑不使用额外空间，技巧：倒序遍历两个数组（先添加较大的）

代码实现：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int merge = m + n - 1;

        while (i > -1 || j > -1) {
            if (j < 0) {
                nums1[merge--] = nums1[i--];
            } else if (i < 0) {
                nums1[merge--] = nums2[j--];
            } else if (nums1[i] > nums2[j]) {
                nums1[merge--] = nums1[i--];
            } else {
                nums1[merge--] = nums2[j--];
            }
        }
    }
}

示例2：《剑指 Offer》第 51 题：数组中的逆序对

注意：暴力解超时！必然进行时间优化，这里利用归并排序分治思想（降低时间复杂度）+合并两个数组的有序性（统计逆序对的个数）

排序的过程是必要的，正是因为排序才加速下一轮的统计逆序对的速度。
分治先统计左右区间的逆序对，再计算跨区间的逆序对（这里我们采用在第2个区间归并时，即j指向元素归并回去的时候，统计逆序数 == 前面还没有归并回去的元素个数：mid - i + 1）即以左边的元素比当前大的元素个数，统计逆序对。

ps：这里不要求排序所以需要拷贝一份nums数组。

ps2：以右侧小于当前元素个数的方式统计逆序数的个数，类似下面的315题，只需要改成归并i，统计逆序数 == j - mid + 1，如果只是统计逆序数，左右无区别，如本题。

代码实现：

class Solution {
    public int reversePairs(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return 0;
        }
        int[] copy = new int[n];
        System.arraycopy(nums, 0, copy, 0, n);

        int[] tmp = new int[n];
        return reversePairs(copy, 0, n - 1, tmp);
    }

    private int reversePairs(int[] copy, int left, int right, int[] tmp) {
        if (left >= right) {
            return 0;
        }
        int mid = left + ((right - left) >> 1);
        int leftPairs = reversePairs(copy, left, mid, tmp);
        int rightPairs = reversePairs(copy, mid + 1, right, tmp);

        if (copy[mid] <= copy[mid + 1]) {
            return leftPairs + rightPairs;
        }
        int crossPairs = mergeAndCount(copy, left, mid, right, tmp);
        return leftPairs + rightPairs + crossPairs;
    }

    private int mergeAndCount(int[] copy, int left, int mid, int right, int[] tmp) {
        System.arraycopy(copy, left, tmp, left, right - left + 1);

        int i = left;
        int j = mid + 1;
        int count = 0;

        for (int k = left; k <= right; k++) {
            if (i == mid + 1) {
                copy[k] = tmp[j];
                j++;
            } else if (j == right + 1) {
                copy[k] = tmp[i];
                i++;
            } else if (tmp[i] <= tmp[j]) {
                copy[k] = tmp[i];
                i++;
            } else {
                copy[k] = tmp[j];
                j++;
                // 当j指向元素归并进去，计算逆序数
                count += (mid - i + 1); 
            }
        }
        return count;
    }
}

示例3：「力扣」第 315 题：计算右侧小于当前元素的个数

注意：数据量很大，暴力必然超时！与上题相同，即每个位置逆序数的个数。

需要在「前有序数组」的元素归并的时候，数一数「后有序数组」已经归并回去的元素的个数，因为这些已经出列的元素都比当前出列的元素要（严格）小；
一个元素在算法的执行过程中位置发生变化，我们还想定位它，可以使用「索引数组」（记录元素下标），技巧在于：「原始数组」不变，用于比较两个元素的大小，真正位置变化的是「索引数组」的位置；归并回去时，方便知道哪个下标的元素。
ps: res[indexes[k]] += (j - mid - 1); 理解：indexes[k] 表示当前 k 下标对应的原始数组的下标是多少，外面再套一层 res[indexes[k]] 记录了原始数组的对应下标右侧小于当前元素的个数，在排序的过程中，每一次计算一部分，所以是 += 。整个算法完成以后，indexes 映射成输入数组的元素的值以后，是有序的。

代码实现：核心：比较数值，操作下标

class Solution {
    public List<Integer> countSmaller(int[] nums) {

        List<Integer> result = new ArrayList<>();
        int n = nums.length;
        if (n < 1) {
            return result;
        }

        int[] ans = new int[n];
        int[] tmp = new int[n];
        int[] indexs = new int[n];

        for (int i = 0; i < n; i++) {
            indexs[i] = i;
        }

        countSmaller(nums, 0, n - 1, tmp, indexs, ans);
        for (int num : ans) {
            result.add(num);
        }
        return result;
    }

    private void countSmaller(int[] nums, int left, int right, int[] tmp, int[] indexs, int[] ans) {
        if (left == right) {
            return;
        }
        int mid = left + (right - left) / 2;
        countSmaller(nums, left, mid, tmp, indexs, ans);
        countSmaller(nums, mid + 1, right, tmp, indexs, ans);

        // 已经有序，不存在逆序对，不需要进行合并
        if (nums[indexs[mid]] <= nums[indexs[mid + 1]]) {
            return;
        }
        mergeAndCount(nums, left, mid, right, tmp, indexs, ans);
    }

    private void mergeAndCount(int[] nums, int left, int mid, int right, int[] tmp, int[] indexs, int[] ans) {
        System.arraycopy(indexs, left, tmp, left, right - left + 1);

        int i = left;
        int j = mid + 1;

        for (int k = left; k <= right; k++) {
            if (i == mid + 1) {
                indexs[k] = tmp[j];
                j++;
            } else if (j == right + 1) {
                indexs[k] = tmp[i];
                i++;
                // 后有序数组已经归并完成，一定比当前要归并的元素小
                ans[indexs[k]] += (right - mid);
            } else if (nums[tmp[i]] <= nums[tmp[j]]) {
                indexs[k] = tmp[i];
                i++;
                // 当前元素要归并，后有序数组已经归并的元素一定比当前元素小
                ans[indexs[k]] += (j - mid - 1);
            } else {
                indexs[k] = tmp[j];
                j++;
            }
        }
    }
}

示例4：计算数组的小和（计算左侧大于当前元素总和）要求时间复杂度O(NlogN)，空间复杂度O(N)

1左边比1小的数，没有；

3左边比3小的数，1；

4左边比4小的数，1、3；

2左边比2小的数，1；

5左边比5小的数，1、3、4、2；

所以小和为1+1+3+1+1+3+4+2=16

代码实现：

import java.util.Scanner;

public class Main {

    // 运行超时
    public static long solution1(int[] nums) {
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] <= nums[i]) {
                    sum += nums[j];
                }
            }
        }
        return sum;
    }

    public static long solution(int[] nums) {
        int n = nums.length;
        if (n < 1) {
            return 0;
        }

        int[] tmp = new int[n];
        return mergeSort(nums, 0, n - 1, tmp);
    }

    private static long mergeSort(int[] nums, int left, int right, int[] tmp) {
        if (left == right) {
            return 0;
        }
        int mid = left + (right - left) / 2;

        return mergeSort(nums, left, mid, tmp) +
               mergeSort(nums, mid + 1, right, tmp) + 
               mergeAndSum(nums, left, mid, right, tmp);
    }

    private static long mergeAndSum(int[] nums, int left, int mid, int right, int[] tmp) {
        System.arraycopy(nums, left, tmp, left, right - left + 1);

        int i = left;
        int j = mid + 1;
        long smallSum = 0;

        for (int k = left; k <= right; k++) {
            if (i == mid + 1) {
                nums[k] = tmp[j];
                j++;
            } else if (j == right + 1) {
                nums[k] = tmp[i];
                i++;
            } else if (tmp[i] <= tmp[j]) {
                // i进行归并时，左边小于右边产生小和（当前加入的一定比右边还未加入的元素小）
                smallSum += tmp[i] * (right - j + 1);
                nums[k] = tmp[i];
                i++;
            } else {
                nums[k] = tmp[j];
                j++;
            }
        }
        return smallSum;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        int i = 0;
        while (n-- > 0) {
            nums[i++] = sc.nextInt();
        }
        System.out.println(solution(nums));
//         System.out.println(solution1(nums));
    }
}

巨人的肩膀：

https://leetcode-cn.com/problems/min-stack/solution/shi-yong-fu-zhu-zhan-tong-bu-he-bu-tong-bu-python-/

vlambda博客
学习文章列表