概述
归并排序算法，想必诸位都十分熟悉。其基本思想也就是 分治。整个排序过程分成两部分–分治法将问题 分(divide)成一些小的问题然后递归求解，而 治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之。
思路
拆分阶段
分的过程很容易看懂，即将一个大的数组拆分成若干个小的数组，减少问题规模。
合并阶段
实现
public static void mergeSort(int [] arr) {
int [] temp = new int [arr.length];
//通过辅助数组可以有效的利用空间，减少空间复杂度。防止sort时递归创建多个数组，增加空间开销
sort(arr, 0, arr.length - 1, temp);
}
/**对arr数组的[left...right]进行归并排序
**/
private static void sort(int [] arr, int left, int right, int [] temp) {
//保证排序边界的有效性
if(left < right) {
int mid = (right + left) / 2;
sort(arr, left, mid, temp);
sort(arr, mid + 1, right, temp);
merge(arr, left, mid, right, temp);
}
}
//将[left...mid]和[mid+1...right]进行合并
private static void merge(int [] arr, int left, int mid,int right, int [] temp) {
int i = left; //指向左侧索引
int j = mid +1; //指向右侧索引
int t = 0; //指向temp数组的指针
while(i
扩展与应用
那么求逆序对和归并排序又有什么关系呢？关键就在于「归并」当中「并」的过程。我们通过一个实例来看看。
首先原始数组为 [2,3,5,7,1,4,6,8]。在合并时比较i所指向的元素2以及j所指向的元素1发现 1
然后j后移，发现 2
i后移，发现 3
然后i继续后移，发现4
分析到这里我们就可以发现一个规律，就是在合并时，当后一个数组索引j所指向的元素大于前一个数组索引i所指向的元素时，会构成逆序对，且逆序对的个数为前一个数组未被排序的元素个数即mid – i +1个。
重复做以上操作便可以得到下边的结果：
代码实现
/**
使用归并排序思想来解决逆序对问题
**/
class Solution {
public int reversePairs(int[] nums) {
int [] temp = new int [nums.length];
return split(nums, 0, nums.length - 1, temp);
}
/**
计算num数组[left .. right]逆序对的个数
**/
private int split(int [] nums, int left, int right, int [] temp) {
if(nums.length < 2) return 0;
if(left < right) {
int mid = (right - left) / 2 + left;
int leftNum = split(nums, left, mid, temp);
int rightNum = split(nums, mid + 1, right, temp);
int mergeNum = merge(nums, left, mid, right, temp);
return leftNum + rightNum + mergeNum;
}
return 0;
}
/**
计算合并nums数组[left...mid]以及[mid+1 .. right]过程中产生的逆序对个数
**/
private int merge(int [] nums, int left, int mid, int right, int [] temp) {
int res = 0;
int i = left;
int j = mid + 1;
int t = 0; //指向临时数组的索引
while(i
总结
归并排序本质上一个分治思想的一种体现，通过将大问题进行拆分，分成若干小问题分别求解。然后将求解结果进行合并，得到一个最终解，进而解决该问题。
引用
- https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/shu-zu-zhong-de-ni-xu-dui-by-leetcode-solution/
- https://www.cnblogs.com/chengxiao/p/6194356.html
Original: https://www.cnblogs.com/goWithHappy/p/merge_sort.html
Author: vcjmhg
Title: 使用归并排序思想解决逆序对数量问题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/599542/
转载文章受原作者版权保护。转载请注明原作者出处！