目录
归并排序（medium）
题目解析
讲解算法原理
编写代码
数组中的逆序对（hard）
题目解析
讲解算法原理
编写代码
归并排序（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个整数数组nums，请你将该数组升序排列。
⽰例1：
输⼊：nums=[5,2,3,1]
输出：[1,2,3,5]
⽰例2：
输⼊：nums=[5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
讲解算法原理
解法（归并排序）：
算法思路：
归并排序的流程充分的体现了「分⽽治之」的思想，⼤体过程分为两步：
◦ 分：将数组⼀分为⼆为两部分，⼀直分解到数组的⻓度为 1 ，使整个数组的排序过程被分为
「左半部分排序」+「右半部分排序」；
◦ 治：将两个较短的「有序数组合并成⼀个⻓的有序数组」，⼀直合并到最初的⻓度。
编写代码
c++算法代码：
class Solution
{
vector<int> tmp;
public:
vector<int> sortArray(vector<int>& nums)
{
tmp.resize(nums.size());
mergeSort(nums, 0, nums.size() - 1);
return nums;
}
void mergeSort(vector<int>& nums, int left, int right)
{
if(left >= right) return;
// 1. 选择中间点划分区间
int mid = (left + right) >> 1;
// [left, mid] [mid + 1, right]
// 2. 把左右区间排序
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// 3. 合并两个有序数组
int cur1 = left, cur2 = mid + 1, i = 0;
while(cur1 <= mid && cur2 <= right)
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] :
nums[cur2++];
// 处理没有遍历完的数组
while(cur1 <= mid) tmp[i++] = nums[cur1++];
while(cur2 <= right) tmp[i++] = nums[cur2++];
// 4. 还原
for(int i = left; i <= right; i++)
nums[i] = tmp[i - left];
}
};class Solution
{
int[] tmp;
public int[] sortArray(int[] nums)
{
tmp = new int[nums.length];
mergeSort(nums, 0, nums.length - 1);
return nums;
}
public void mergeSort(int[] nums, int left, int right)
{
if(left >= right) return;
// 1. 根据中间点划分区间
int mid = (left + right) / 2;
// [left, mid] [mid + 1, right]
// 2. 先把左右区间排个序
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// 3. 合并两个有序数组
int cur1 = left, cur2 = mid + 1, i = 0;
while(cur1 <= mid && cur2 <= right)
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
// 处理没有遍历完的数组
while(cur1 <= mid) tmp[i++] = nums[cur1++];
while(cur2 <= right) tmp[i++] = nums[cur2++];
// 4. 还原
for(int j = left; j <= right; j++)
nums[j] = tmp[j - left];
}
}数组中的逆序对（hard）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
在数组中的两个数字，如果前⾯⼀个数字⼤于后⾯的数字，则这两个数字组成⼀个逆序对。输⼊⼀个数组，求出这个数组中的逆序对的总数。
⽰例1:
输⼊:[7,5,6,4]输出:5
讲解算法原理
解法（利⽤归并排序的过程---分治）：算法思路：
⽤归并排序求逆序数是很经典的⽅法，主要就是在归并排序的合并过程中统计出逆序对的数量，也就是在合并两个有序序列的过程中，能够快速求出逆序对的数量。
我们将这个问题分解成⼏个⼩问题，逐⼀破解这道题。
注意：默认都是升序，如果掌握升序的话，降序的归并过程也是可以解决问题的。• 先解决第⼀个问题，为什么可以利⽤归并排序？
如果我们将数组从中间划分成两个部分，那么我们可以将逆序对产⽣的⽅式划分成三组：• 逆序对中两个元素：全部从左数组中选择
• 逆序对中两个元素：全部从右数组中选择• 逆序对中两个元素：⼀个选左数组另⼀个选右数组根据排列组合的分类相加原理，三种种情况下产⽣的逆序对的总和，正好等于总的逆序对数量。
⽽这个思路正好匹配归并排序的过程：• 先排序左数组；
• 再排序右数组；• 左数组和右数组合⼆为⼀。
因此，我们可以利⽤归并排序的过程，先求出左半数组中逆序对的数量，再求出右半数组中逆序对的数量，最后求出⼀个选择左边，另⼀个选择右边情况下逆序对的数量，三者相加即可。
• 解决第⼆个问题，为什么要这么做？在归并排序合并的过程中，我们得到的是两个有序的数组。我们是可以利⽤数组的有序性，快速统计
出逆序对的数量，⽽不是将所有情况都枚举出来。
• 最核⼼的问题，如何在合并两个有序数组的过程中，统计出逆序对的数量？合并两个有序序列时求逆序对的⽅法有两种：
1. 快速统计出某个数前⾯有多少个数⽐它⼤；2. 快速统计出某个数后⾯有多少个数⽐它⼩；
⽅法⼀：快速统计出某个数前⾯有多少个数⽐它⼤通过⼀个⽰例来演⽰⽅法⼀：
假定已经有两个已经有序的序列以及辅助数组left=[5,7,9]right=[4,5,8]help=[]，通过合并两个有序数组的过程，来求得逆序对的数量：
规定如下定义来叙述过程:
cur1遍历left数组，cur2遍历right数组ret记录逆序对的数量
第⼀轮循环：
left[cur1]>right[cur2]，由于两个数组都是升序的，那么我们可以断定，此刻left数组中[cur1,2]区间内的3个元素均可与right[cur2]的元素构成逆序对，因此可以累加逆序对的数量ret+=3，并且将right[cur2]加⼊到辅助数组中，cur2++遍历下⼀个元素。
第⼀轮循环结束后：left=[5,7,9]right=[x,5,8]help=[4]ret=3cur1=0cur2=1
第⼆轮循环：
left[cur1]==right[cur2]，因为right[cur2]可能与left数组中往后的元素构成逆序对，因此我们需要将left[cur1]加⼊到辅助数组中去，此时没有产⽣逆序对，不更新ret。
第⼆轮循环结束后：left=[x,7,9]right=[x,5,8]help=[4,5]ret=3cur1=1cur2=1
第三轮循环：
left[cur1]>right[cur2]，与第⼀轮循环相同，此刻left数组中[cur1,2]区间内的2个元素均可与right[cur2]的元素构成逆序对，更新ret的值为ret+=2，并且将right[cur2]加⼊到辅助数组中去，cur2++遍历下⼀个元素。
第三轮循环结束后：left=[x,7,9]right=[x,x,8]help=[4,5,5]ret=5cur1=1cur2=2
第四轮循环：
left[cur1]<right[cur2]，由于两个数组都是升序的，因此我们可以确定left[cur1]⽐right数组中的所有元素都要⼩。left[cur1]这个元素是不可能与right数组中的元素构成逆序对。因此，⼤胆
的将left[cur1]这个元素加⼊到辅助数组中去，不更细ret的值。第四轮循环结束后：left=[x,x,9]right=[x,x,8]help=[4,5,5,7]ret=5cur1=2cur2=2
第五轮循环：
left[cur1]>right[cur2]，与第⼀、第三轮循环相同。此时left数组内的1个元素能与right[cur2]构成逆序对，更新ret的值，并且将right[cur2]加⼊到辅助数组中去。
第五轮循环结束后：left=[x,x,9]right=[x,x,x]help=[4,5,5,7,8]ret=6cur1=2cur2=2
处理剩余元素：• 如果是左边出现剩余，说明左边剩下的所有元素都是⽐右边元素⼤的，但是它们都是已经被计算过
的（我们以右边的元素为基准的），因此不会产⽣逆序对，仅需归并排序即可。• 如果是右边出现剩余，说明右边剩下的元素都是⽐左边⼤的，不符合逆序对的定义，因此也不需要
处理，仅需归并排序即可。
整个过程只需将两个数组遍历⼀遍即可，时间复杂度为O(N)。由上述过程我们可以得出⽅法⼀统计逆序对的关键点：
在合并有序数组的时候，遇到左数组当前元素>右数组当前元素时，我们可以通过计算左数组中剩余元素的⻓度，就可快速求出右数组当前元素前⾯有多少个数⽐它⼤，对⽐解法⼀中⼀个⼀个枚举逆序对效率快了许多。
⽅法⼆：快速统计出某个数后⾯有多少个数⽐它⼩依旧通过⼀个⽰例来演⽰⽅法⼆：
假定已经有两个已经有序的序列以及辅助数组left=[5,7,9]right=[4,5,8]help=[]，通过合并两个有序数组的过程，来求得逆序对的数量：
规定如下定义来叙述过程:
cur1遍历left数组，cur2遍历right数组ret记录逆序对的数量
第⼀轮循环：
left[cur1]>right[cur2]，先不要着急统计，因为我们要找的是当前元素后⾯有多少⽐它⼩的，这⾥虽然出现了⼀个，但是right数组中依旧还可能有其余⽐它⼩的。因此此时仅将right[cur2]加⼊到辅助数组中去，并且将cur2++。
第⼀轮循环结束后：left=[5,7,9]right=[x,5,8]help=[4]ret=0cur1=0cur2=1
第⼆轮循环：
left[cur1]==right[cur2]，由于两个数组都是升序，这个时候对于元素left[cur1]来说，我们已经可以断定right数组中[0,cur2)左闭右开区间上的元素都是⽐它⼩的。因此此时可以统计逆序对的数量ret+=cur2-0，并且将left[cur1]放⼊到辅助数组中去，cur1++遍历下⼀个元素。
第⼆轮循环结束后：left=[x,7,9]right=[x,5,8]help=[4,5]ret=1cur1=1cur2=1
第三轮循环：
left[cur1]>right[cur2]，与第⼀轮循环相同，直接将right[cur2]加⼊到辅助数组中去，cur2++遍历下⼀个元素。
第三轮循环结束后：left=[x,7,9]right=[x,x,8]help=[4,5,5]ret=1cur1=1cur2=2
第四轮循环：
left[cur1]<right[cur2]，由于两个数组都是升序的，这个时候对于元素left[cur1]来说，我们依旧已经可以断定right数组中[0,cur2)左闭右开区间上的元素都是⽐它⼩的。因此此时可以统计逆序对的数量ret+=cur2-0，并且将left[cur1]放⼊到辅助数组中去，cur1++遍历下⼀个元素。
第四轮循环结束后：left=[9]right=[8]help=[4,5,5,7]ret=3cur1=2cur2=2
第五轮循环：
left[cur1]>right[cur2]，与第⼀、第三轮循环相同。直接将right[cur2]加⼊到辅助数组中去，cur2++遍历下⼀个元素。
第五轮循环结束后：left=[x,x,9]right=[x,x,x]help=[4,5,5,7,8]ret=3cur1=2cur2=2
处理剩余元素：• 如果是左边出现剩余，说明左边剩下的所有元素都是⽐右边元素⼤的，但是相⽐较于⽅法⼀，逆序
对的数量是没有统计过的。因此，我们需要统计ret的值：
◦ 设左边数组剩余元素的个数为leave◦ ret+=leave*（cur2-0）
对于本题来说，处理剩余元素的时候，left数组剩余1个元素，cur2-0=3，因此ret需要类加上3，结果为6。与⽅法⼀求得的结果相同。
• 如果是右边出现剩余，说明右边剩下的元素都是⽐左边⼤的，不符合逆序对的定义，因此也不需要处理，仅需归并排序即可。
整个过程只需将两个数组遍历⼀遍即可，时间复杂度依旧为O(N)。
由上述过程我们可以得出⽅法⼆统计逆序对的关键点：
在合并有序数组的时候，遇到左数组当前元素<=右数组当前元素时，我们可以通过计算右数组已经遍历过的元素的⻓度，快速求出左数组当前元素后⾯有多少个数⽐它⼤。
但是需要注意的是，在处理剩余元素的时候，⽅法⼆还需要统计逆序对的数量。
编写代码
升序的版本
c++算法代码：
class Solution
{
int tmp[50010];
public:
int reversePairs(vector<int>& nums)
{
return mergeSort(nums, 0, nums.size() - 1);
}
int mergeSort(vector<int>& nums, int left, int right)
{
if(left >= right) return 0;
int ret = 0;
// 1. 找中间点，将数组分成两部分
int mid = (left + right) >> 1;
// [left, mid][mid + 1, right]
// 2. 左边的个数 + 排序 + 右边的个数 + 排序
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
// 3. ⼀左⼀右的个数
int cur1 = left, cur2 = mid + 1, i = 0;
while(cur1 <= mid && cur2 <= right) // 升序的时候 {
if(nums[cur1] <= nums[cur2])
{
tmp[i++] = nums[cur1++];
}
else
{
ret += mid - cur1 + 1;
tmp[i++] = nums[cur2++];
}
}
// 4. 处理⼀下排序
while(cur1 <= mid) tmp[i++] = nums[cur1++];
while(cur2 <= right) tmp[i++] = nums[cur2++];
for(int j = left; j <= right; j++)
nums[j] = tmp[j - left];
return ret;
}
};class Solution
{
int[] tmp;
public int reversePairs(int[] nums)
{
int n = nums.length;
tmp = new int[n];
return mergeSort(nums, 0, n - 1);
}
public int mergeSort(int[] nums, int left, int right)
{
if(left >= right) return 0;
int ret = 0;
// 1. 选择⼀个中间点，将数组划分成两部分
int mid = (left + right) / 2;
// [left, mid] [mid + 1, right]
// 2. 左半部分的个数 + 排序 + 右半部分的个数 + 排序 ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
// 3. ⼀左⼀右的个数
int cur1 = left, cur2 = mid + 1, i = 0;
while(cur1 <= mid && cur2 <= right) // 升序版本 {
if(nums[cur1] <= nums[cur2])
{
tmp[i++] = nums[cur1++];
}
else
{
ret += mid - cur1 + 1;
tmp[i++] = nums[cur2++];
}
}
// 4. 处理⼀下排序
while(cur1 <= mid) tmp[i++] = nums[cur1++];
while(cur2 <= right) tmp[i++] = nums[cur2++];
for(int j = left; j <= right; j++)
nums[j] = tmp[j - left];
return ret;
}
}降序的版本
c++算法代码：
class Solution
{
int tmp[50010];
public:
int reversePairs(vector<int>& nums)
{
return mergeSort(nums, 0, nums.size() - 1);
}
int mergeSort(vector<int>& nums, int left, int right)
{
if(left >= right) return 0;
int ret = 0;
// 1. 找中间点，将数组分成两部分
int mid = (left + right) >> 1;
// [left, mid][mid + 1, right]
// 2. 左边的个数 + 排序 + 右边的个数 + 排序
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
// 3. ⼀左⼀右的个数
int cur1 = left, cur2 = mid + 1, i = 0;
while(cur1 <= mid && cur2 <= right) // 降序的版本 {
if(nums[cur1] <= nums[cur2])
{
tmp[i++] = nums[cur2++];
}
else
{
ret += right - cur2 + 1;
tmp[i++] = nums[cur1++];
}
}
// 4. 处理⼀下排序
while(cur1 <= mid) tmp[i++] = nums[cur1++];
while(cur2 <= right) tmp[i++] = nums[cur2++];
for(int j = left; j <= right; j++)
nums[j] = tmp[j - left];
return ret;
}
};class Solution
{
int[] tmp;
public int reversePairs(int[] nums)
{
int n = nums.length;
tmp = new int[n];
return mergeSort(nums, 0, n - 1);
}
public int mergeSort(int[] nums, int left, int right)
{
if(left >= right) return 0;
int ret = 0;
// 1. 选择⼀个中间点，将数组划分成两部分
int mid = (left + right) / 2;
// [left, mid] [mid + 1, right]
// 2. 左半部分的个数 + 排序 + 右半部分的个数 + 排序 ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
// 3. ⼀左⼀右的个数
int cur1 = left, cur2 = mid + 1, i = 0;
while(cur1 <= mid && cur2 <= right) // 降序的版本 {
if(nums[cur1] <= nums[cur2])
{
tmp[i++] = nums[cur2++];
}
else
{
ret += right - cur2 + 1;
tmp[i++] = nums[cur1++];
}
}
// 4. 处理⼀下排序
while(cur1 <= mid) tmp[i++] = nums[cur1++];
while(cur2 <= right) tmp[i++] = nums[cur2++];
for(int j = left; j <= right; j++)
nums[j] = tmp[j - left];
return ret;
}
}
