C++算法
归并排序与数组中的逆序对算法解析
归并排序利用分治思想将数组递归二分至单个元素，再通过有序合并完成排序，时间复杂度为 O(nlogn)。在归并合并两个有序子数组的过程中，可利用有序性快速统计跨越两部分的逆序对数量。文章详解了归并排序的标准实现，以及基于该过程计算数组中逆序对总数的优化算法，包含核心思路分析与 C++ 代码示例。
归并排序利用分治思想将数组递归二分至单个元素，再通过有序合并完成排序，时间复杂度为 O(nlogn)。在归并合并两个有序子数组的过程中，可利用有序性快速统计跨越两部分的逆序对数量。文章详解了归并排序的标准实现，以及基于该过程计算数组中逆序对总数的优化算法，包含核心思路分析与 C++ 代码示例。
归并排序的流程充分体现了「分而治之」的思想，大体过程分为两步：
分：将数组一分为二为两部分，一直分解到数组的长度为 1，使整个数组的排序过程被分为「左半部分排序」+「右半部分排序」;
治：将两个较短的「有序数组合并成一个长的有序数组」，一直合并到最初的长度。
class Solution {
public:
// 归并排序的算法
vector<int> tmp; // 用于存放两个有序数组合并后的结果
void mergesort(vector<int>& nums, int left, int right) {
if (left == right) {
return;
}
// 1、选择中间点划分区间
int mid = (right - left) / 2 + left;
// 将数组分成两块：[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++];
}
// 只会进其中一个循环
// 将两个数组有序合并到 tmp 中后，再还原给原数组 nums 对应部分位置
for (int i = left; i <= right; i++) {
nums[i] = tmp[i - left]; // tmp 数组每次都是以开头下标 0 的位置合并两个数组
}
}
vector<int> sortArray(vector<int>& nums) {
// 归并实现：
tmp.resize(nums.size());
mergesort(nums, 0, nums.size() - 1);
return nums;
}
};
用归并排序求逆序数是很经典的方法，主要就是在归并排序的合并过程中统计出逆序对的数量，也就是在合并两个有序序列的过程中，能够快速求出逆序对的数量。
我们将这个问题分解成几个小问题，逐一破解这道题。 (注意：默认都是升序，如果掌握升序的话，降序的归并过程也是可以解决问题的。)
先解决第一个问题，为什么可以利用归并排序？
如果我们将数组从中间划分成两个部分，那么我们可以将逆序对产生的方式划分成三组：
逆序对中两个元素：全部从左数组中选择
逆序对中两个元素：全部从右数组中选择
逆序对中两个元素：一个选左数组另一个选右数组
根据排列组合的分类相加原理，三种情况下产生的逆序对的总和，正好等于总的逆序对数量。
而这个思路正好匹配归并排序的过程：
先排序左数组；
再排序右数组；
左数组和右数组合二为一。
因此，我们可以利用归并排序的过程，先求出左半数组中逆序对的数量，再求出右半数组中逆序对的数量，最后求出一个选择左边，另一个选择右边情况下逆序对的数量，三者相加即可。
解决第二个问题，为什么要这么做？
在归并排序合并的过程中，我们得到的是两个有序的数组。我们是利用数组的有序性，快速统计出逆序对的数量，而不是将所有情况都枚举出来。
最核心的问题，如何在合并两个有序数组的过程中，统计出逆序对的数量？合并两个有序序列时求逆序对的方法有两种：
class Solution {
public:
int count = 0;
vector<int> tmp; // 用于存放两个有序数组合并后的结果
int reversePairs(vector<int>& record) {
tmp.resize(record.size());
mergesort(record, 0, record.size() - 1);
return count;
}
void mergesort(vector<int>& nums, int left, int right) {
if (left >= right) // 正常归并排序递归的结束条件不用包含 left>right
// 因为归并是分两块，最小的情况就是两个数分成各一个，不存在越界的情况
// 但是此题有空数组的案例，所以一开始 left=0，right=-1，要考虑在内
{
return;
}
// 1、选择中间点划分区间
int mid = (right - left) / 2 + left;
// 将数组分成两块：[left, mid] [mid + 1, right]
// 2、把左右区间排序
mergesort(nums, left, mid);
mergesort(nums, mid + 1, right);
// 3、判断两个有序数组一左一右的逆序对个数，并且将两个数组合并成一个有序数组
int cur1 = left, cur2 = mid + 1, i = 0;
//(1) 将数组排成升序的思路：
while (cur1 <= mid && cur2 <= right) {
if (nums[cur1] <= nums[cur2]) {
tmp[i++] = nums[cur1++];
} else {
// 当第一次遇见 nums[cur1] > nums[cur2],说明 [cur1, mid] 区间所有值都大于 nums[cur2]
// 计算当前 nums[cur2] 的逆序对个数
count += mid - cur1 + 1;
tmp[i++] = nums[cur2++];
}
}
//(2) 将数组排成降序的思路：
// while(cur1 <= mid && cur2 <= right)
// {
// if(nums[cur1] > nums[cur2])
// {
// count += right - cur2 + 1;
// tmp[i++] = nums[cur1++];
// }
// else
// {
// tmp[i++] = nums[cur2++];
// }
// }
// 处理还没有排序的剩余部分
while (cur1 <= mid) {
tmp[i++] = nums[cur1++];
}
while (cur2 <= right) {
tmp[i++] = nums[cur2++];
}
// 将两个数组有序合并到 tmp 中后，再还原给原数组 nums 对应部分位置
for (int i = left; i <= right; i++) {
nums[i] = tmp[i - left]; // tmp 数组每次都是以开头下标 0 的位置合并两个数组
}
}
};
到此，47.归并排序，48.数组中的逆序对这两道算法题就讲解完了。归并排序采用分治思想，先将数组不断二分至单个元素，再通过有序合并操作完成排序，时间复杂度为 O(nlogn)。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online