前言介绍

归并排序是Merge sort）是一种有效、稳定的排序算法，它采用了分治法（Divide and Conquer）的典型应用,何为分治 ? 即把多个事件分为两个或者多个子问题来解决(其实是一种递归寻找子问题的思路)

归并分支的思想

• 原理 : 在思考一个问题在大范围上的答案, 是否等于, 左部分的答案 + 右部分的答案 + 跨越左右的答案
• 在计算跨越左右的答案的时候, 我们要思考如果加上左右都有序的这个条件, 会不会获得计算的便利性
• 如果满足上述的两点, 那我们的这个题大概率是通过归并分治的思路去解决
• 只需要改编我们的merge函数即可, 在求解问题的同时, 加上归并排序的过程即可

1 . 简单的归并排序

首先先讲一下我们的归并排序,归并排序是一种高效的排序算法

代码的实现细节如下

class Solution {public int[] sortArray(int[] nums) {if (nums == null || nums.length < 2) {return nums;}//下面是排序的主体mergeSort(nums, 0, nums.length - 1);return nums;}private void mergeSort(int[] nums, int left, int right) {if (left >= right) {return;}int mid = left + ((right - left) >> 1);mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);//其实质是每次通过merge函数之后,之前比较的结果就会被保留进行加速merge(nums, left, mid, right);}private void merge(int[] nums, int left, int mid, int right) {int[] temp = new int[right - left + 1];int pl = left;int pr = mid + 1;int index = 0;while (pl <= mid && pr <= right) {if (nums[pl] <= nums[pr]) {temp[index++] = nums[pl++];} else {temp[index++] = nums[pr++];}}while (pl <= mid) {temp[index++] = nums[pl++];}while (pr <= right) {temp[index++] = nums[pr++];}for (int i = 0; i < index; ++i) {nums[left + i] = temp[i];}}
}

有了上面的归并分治的基础,我们回头看我们的归并排序,其实就是分治法的一种标准应用, 总体有序 = 左半边有序 + 右半边有序 + 跨越左右有序

2 . 数组的最小和问题

用暴力方法,这道题是很好想的,时间复杂度是O(N^2)
我们先来尝试分析一下这道题

首先 :
逆向思维转换,求数组的小和,其实就是求一个数在小和里面贡献了多少
即为,对于任意一个数来说,该数右边有几个数比该数大,那就贡献了几份这个数字的大小
其次 :
进行分治法分析 , 总小和数 = 左小和数 + 右小和数 + 左跨右的小和数
请一定要记住 , 计算某一半边的小和数的时候 , 一定不能与另一半边关联(分)
最后 :
有了分治的思想 , 当左半边跟右半边有序的时候 , 题目会不会更简便 , 答案是肯定的 , 有序了之后 , 每次滑动的时候 , 指针是不会进行回退的(滑动窗口的思想) , 所以时间复杂度可以达到 O(N) (统计的时候)

下面是代码实现

 /*** 求一个数组的小和 :* 基本思路是首先用逆向思维法, 想要计算小和, 可以统计某一个数字在小和中的出现的次数来累加求和计算* 整个数组的小和 == 左侧数组的小和 + 右侧数组的小和 + 跨越左右的小和* 这道题, 如果不进行排序的话, 时间复杂度还是O(N^2)...* 在进行排序了之后,我们的统计的时间复杂度其实是O(N)...* 所以这道题可以采用归并分治的策略来解决** @param nums* @param left* @param right* @return*/public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int sz = in.nextInt();int[] nums = new int[sz];for (int i = 0; i < nums.length; ++i) {nums[i] = in.nextInt();}long res = getMinSum(nums,0,nums.length - 1);System.out.println(res);}public static long getMinSum(int[] nums, int left, int right) {if (left == right) {return 0;}int mid = left + ((right - left) >> 1);return getMinSum(nums, left, mid) + getMinSum(nums, mid + 1,right) + mergeMinSum(nums, left, mid, right);}private static long mergeMinSum(int[] nums, int left, int mid, int right) {int pl = left;int pr = mid + 1;long ans = 0;long tempSum = 0;//下面是进行统计的过程//下面这个循环的时间复杂度其实是O(N),因为我们的左指针是不发生回退的while (pr <= right) {while (pl <= mid && nums[pl] <= nums[pr]) {tempSum += nums[pl++];}ans += tempSum;pr++;}//下面我们进行排序的过程pl = left;pr = mid + 1;int index = 0;int[] temp = new int[right - left + 1];while (pl <= mid && pr <= right) {temp[index++] = nums[pl] <= nums[pr] ? nums[pl++] : nums[pr++];}while (pl <= mid) {temp[index++] = nums[pl++];}while (pr <= right) {temp[index++] = nums[pr++];}for (int i = 0; i < temp.length; ++i) {nums[left + i] = temp[i];}return ans;}}

3 . 逆序数对问题

归并分治的分析
总交易逆序对数目 = 左边数目 + 右边数目 + 左跨右的数目
然后如果在每次统计完进行归并排序之后,我们又会加速这过程
其实就是归并排序(滑动窗口)
代码实现如下

class Solution {public int reversePairs(int[] record) {if (record == null || record.length <= 1) {return 0;}return process(record, 0, record.length - 1);}// 下面就是归并的思路了private int process(int[] nums, int left, int right) {// 递归终止条件if (left == right) {return 0;}int mid = left + ((right - left) >> 1);return process(nums, left, mid) + process(nums, mid + 1, right) + mergeOfrevers(nums, left, mid, right);}private int mergeOfrevers(int[] nums, int left, int mid, int right) {// 先统计,后进行排序int pl = left;int pr = mid + 1;int ans = 0;while (pl <= mid) {while (pr <= right && nums[pl] > nums[pr]) {pr++;}ans += pr - mid - 1;pl++;}// 下面就没什么可说的了,就是简单的归并排序的过程pl = left;pr = mid + 1;int index = 0;int[] temp = new int[right - left + 1];while (pl <= mid && pr <= right) {temp[index++] = nums[pl] <= nums[pr] ? nums[pl++] : nums[pr++];}while (pl <= mid) {temp[index++] = nums[pl++];}while (pr <= right) {temp[index++] = nums[pr++];}for (int i = 0; i < temp.length; ++i) {nums[left + i] = temp[i];}return ans;}
}

4 . 翻转对数量的计算

这道题也没什么可以说的点, 跟上一道题的思路, 完完全全一致
直接上代码实现 ,改动的时候, 记得把 nums[pl] <= nums[pr]* 2
换成 nums[pl] / 2.0 <= nums[pr]
因为要防止数字越界

class Solution {public int reversePairs(int[] record) {if (record == null || record.length <= 1) {return 0;}return process(record, 0, record.length - 1);}// 下面就是归并分治的思路了private int process(int[] nums, int left, int right) {// 递归终止条件if (left == right) {return 0;}int mid = left + ((right - left) >> 1);return process(nums, left, mid) + process(nums, mid + 1, right) + mergeOfrevers(nums, left, mid, right);}private int mergeOfrevers(int[] nums, int left, int mid, int right) {// 先统计,后进行排序int pl = left;int pr = mid + 1;int ans = 0;while (pl <= mid) {while (pr <= right && nums[pl]  / 2.0 >  (double)nums[pr]) {pr++;}ans += pr - mid - 1;pl++;}// 下面就没什么可说的了,就是简单的归并排序的过程pl = left;pr = mid + 1;int index = 0;int[] temp = new int[right - left + 1];while (pl <= mid && pr <= right) {temp[index++] = nums[pl] <= nums[pr] ? nums[pl++] : nums[pr++];}while (pl <= mid) {temp[index++] = nums[pl++];}while (pr <= right) {temp[index++] = nums[pr++];}for (int i = 0; i < temp.length; ++i) {nums[left + i] = temp[i];}return ans;}
}