目录
1. 归并排序
给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
示例 1：
输入：nums = [5,2,3,1] 输出：[1,2,3,5] 解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。
示例 2：
输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5] 解释：请注意，nums 的值不一定唯一。
提示：
1 <= nums.length <= 5 * 104-5 * 104 <= nums[i] <= 5 * 104
1.1 题目解析
题目本质
把整数数组 nums 升序排列。目标是在不调用内置排序的前提下，做到 O(n log n) 的时间复杂度，且额外空间尽量小。
常规解法
直接用冒泡 / 插入 / 选择：实现简单，但时间复杂度 O(n^2)，在 n=5*10^4 时会超时。
快排（手写）：平均 O(n log n)，最坏 O(n^2)，实现要注意枢轴与不变式，否则容易退化。
问题分析
题目希望稳定达成 O(n log n)。稳定、可控且好实现的选择是归并排序：
分而治之（递归二分）保证 log n 层；
每层合并代价 O(n)；
总体 O(n log n)；
代价是需要一段临时数组 tmp（O(n) 额外空间）。
思路转折
要想时间稳定在 O(n log n) 且实现稳健 → 走归并排序路线：
先把左右两段分别排好；
合并时双指针线性扫一遍，把更小的元素依次写入 tmp；
最后把 tmp 回写到 nums[left..right]。
预测：时间 O(n log n)；空间 O(n)（单份 tmp 复用，已经是归并常见的最小开销版）。
1.2 解法
算法思想
分治 + 合并 对区间 [left, right]：
划分中点 mid = (right + left) / 2；
递归排好 [left, mid] 与 [mid+1, right]；
用双指针 cur1、cur2 合并到 tmp[0..]；
把 tmp 覆盖回 nums[left..right]。
此实现是稳定排序：当相等时 nums[cur1] <= nums[cur2] 先取左边，保持相对次序。
i）在 sortArray 中创建一份长度为 nums.length 的 tmp，供所有递归复用；
ii）mergeSort(nums, left, right)：
递归终止：left >= right；
分治：mergeSort(nums, left, mid) 与 mergeSort(nums, mid+1, right)；
合并：
cur1 = left, cur2 = mid+1, i = 0；
当 cur1<=mid && cur2<=right：把较小的放入 tmp[i++]；
扫尾：把剩余的另一侧元素依次放入 tmp；
回写：for (int j = left; j <= right; j++) nums[j] = tmp[j-left];
易错点
合并时比较的是元素值：nums[cur1] <= nums[cur2]，不是下标范围。
递增 i 指针 tmp[i++] 。
回写时的偏移要用 j - left，因为 tmp 从 0 写起。
1.3 代码实现
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;
}
int mid = (right + left) / 2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
int i = 0, cur1 = left, cur2 = mid + 1;
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++];
for (int j = left; j <= right; j++) {
nums[j] = tmp[j - left];
}
}
}
复杂度分析
时间复杂度：O(n log n)
空间复杂度：O(n)
2. 交易逆序对的总数
LCR 170. 交易逆序对的总数 - 力扣（LeetCode）
在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。
示例 1：
输入：record = [9, 7, 5, 4, 6] 输出：8 解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。
提示：
0 <= record.length <= 50000
2.1 题目解析
题目本质
这是典型的逆序对计数：给定数组 record，统计满足 i < j 且 record[i] > record[j] 的有序对数量。
核心抽象：用分治 + 合并（归并排序），在合并两段有序区间时批量统计跨段逆序对。
常规解法
双重循环枚举所有 (i, j)，判断 record[i] > record[j]。
问题分析
暴力是 O(n^2)，n=5e4 时约 12.5 亿次比较，不可接受。
思路转折
要高效 → 需要在有序结构里批量计数 → 归并合并时一次比较可累计一段：
升序合并：若 nums[i] > nums[j]（i∈[left,mid], j∈[mid+1,right]），则左侧 [i..mid] 全部大于 nums[j]，一次性加 mid - i + 1。
降序合并：若 nums[i] > nums[j]，则右侧 [j..right] 全部小于 nums[i]，一次性加 right - j + 1。
预测：整体 O(n log n)，可过最大规模。
2.2 解法
算法思想
分治 + 合并计数 对 [left, right]：
递归统计左区间 [left, mid] 总数、右区间 [mid+1, right] 总数；
合并时统计跨跨区间总数
总数 ret = 左区间 + 右区间 + 跨区间。
升序合并公式
nums[i] > nums[j] ⇒ ret += (mid - i + 1)。
降序合并公式
nums[i] > nums[j] ⇒ ret += (right - j + 1)。
两种写法都对；差别只在“谁先入 tmp ”以及“加哪一侧的剩余长度”。
i）递归把 [left, right] 拆到长度为 1；
ii）分别统计左右段的逆序对；
iii）合并两段有序数组，同时批量统计跨段逆序对；
iiii）回写 tmp 到 nums[left..right]；
iiiii）返回计数。
易错点
递归区间错误
合并时比较的是“值”，不是下标范围：if (nums[i] <= nums[j])。
递增临时数组指针：tmp[k++]
计数的“参照物”要和合并方向匹配：
升序合并：右更小时加左侧剩余 mid - i + 1。
降序合并：左更大时加右侧剩余 right - j + 1。
回写用偏移：nums[j] = tmp[j-left]，不要用已移动过的 left 做下标。j 遍历原区间 [left..right]，j-left 就是对应的 tmp 下标。
2.3 代码实现
方法一：升序合并计数
class Solution {
int dest; // 不用也保留你的字段名
int[] tmp;
public int reversePairs(int[] record) {
if (record == null || record.length < 2) return 0;
dest = 0; // 按你的风格保留
tmp = new int[record.length];
int result = mergeSort(record, 0, record.length - 1);
return result;
}
public int mergeSort(int[] nums, int left, int right) {
if (left >= right) return 0;
int mid = left + (right - left) / 2;
int ret = 0;
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
int cur1 = left, cur2 = mid + 1, i = 0;
while (cur1 <= mid && cur2 <= right) { // 升序合并
if (nums[cur1] <= nums[cur2]) {
tmp[i++] = nums[cur1++];
} else {
// 右更小 → 左侧 [cur1..mid] 都 > nums[cur2]
ret += (mid - cur1 + 1);
tmp[i++] = nums[cur2++];
}
}
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 dest; // 同上，保留
int[] tmp;
public int reversePairs(int[] record) {
if (record == null || record.length < 2) return 0;
dest = 0;
tmp = new int[record.length];
int result = mergeSort(record, 0, record.length - 1);
return result;
}
public int mergeSort(int[] nums, int left, int right) {
if (left >= right) return 0;
int mid = left + (right - left) / 2;
int ret = 0;
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
int cur1 = left, cur2 = mid + 1, i = 0;
while (cur1 <= mid && cur2 <= right) { // 降序合并
if (nums[cur1] > nums[cur2]) {
// 左更大 → 右侧 [cur2..right] 都 < nums[cur1]
ret += (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++];
for (int j = left; j <= right; j++) {
nums[j] = tmp[j - left];
}
return ret;
}
}
复杂度分析
时间复杂度：O(n log n)
空间复杂度：O(n)