企业官网建设流程全解析

第一次刷到“交易逆序对的总数(6)”这道题时，我愣了几秒钟——交易？逆序对？后来仔细一看题面，其实就是经典数组逆序对统计，题号后面的“(6)”大概只是题库里的序号，跟难度没有直接关系。逆序对的定义很简单：对于数组nums，如果存在i < j且nums[i] > nums[j]，那(i,j)就算一对。统计整个数组有多少对这样的组合，看起来朴素，但它是分治思想最好的入门练习题之一，也是面试里反复出现的考察点。数组规模一旦到十万、百万，O(n²) 的两层循环铁定超时，只有归并排序配合分治，才能把复杂度稳定压到 O(n log n)。这篇文章我会把暴力解、分治原理、完整代码、易错点一次聊透，适合刚学算法的人，也适合准备刷题面试的人参考。

1. 先说清楚逆序对的定义，以及暴力解为什么走不通

1.1 用手数一遍，理解“逆序”到底指什么

我们先拿一个具体数组[7,5,6,4]来数。下标从0开始，所有下标对一共 C(4,2)=6 对，其中满足前面元素大于后面元素的是：7>5、7>6、7>4、5>4、6>4，一共5对。注意5和6这组是5<6，不满足；两个相等的元素比如[1,1]也不算逆序对，必须是严格大于。这里“严格大于”四个字看着不起眼，但在代码里如果写错等号，结果会差很多，后面我会专门讲。

逆序对数量在数学上叫逆序数，它描述的是一个数组相对于升序排列的“错乱程度”。一个完全升序的数组逆序对数为0，一个完全降序的数组逆序对数为n*(n-1)/2，也就是任意两个位置都构成一个逆序对。这个特性很有用，平时验证代码对不对，可以直接构造几个特殊数组：升序数组答案必须是0，降序数组答案必须是n*(n-1)/2，重复数组则要看严格大于条件。

1.2 暴力两层循环：5行代码解决，但只配当玩具

暴力法的思路没有任何弯子：枚举所有i<j，判断nums[i]是否大于nums[j]。Python 写出来就是这样：

def count_inversions_bruteforce(nums): n = len(nums) ans = 0 for i in range(n): for j in range(i + 1, n): if nums[i] > nums[j]: ans += 1 return ans

这段代码的正确性不用怀疑，拿来对拍、验证优化算法非常顺手。但它的问题是复杂度 O(n²)。当n=10^5时，最坏情况需要比较大约5×10^9次，即使 C++ 也未必能在一两秒内跑完，Python 更是直接劝退。所以生产中不可能用暴力，算法竞赛和面试更不可能把 O(n²) 当作最终答案。一旦意识到“每个元素对都被重复比较了很多次”，自然就会想到分治：能不能让每一对元素只被少量几次操作覆盖，而不是全量枚举。

2. 分治为什么能优化逆序对统计

2.1 分治三步骤和逆序对的天然对应

分治算法的经典流程是先分解、再解决、再合并。对数组从中间劈开成左右两半，先分别递归求出左半段内部的逆序对数和右半段内部的逆序对数，然后只需要额外统计“一个元素在左半段、另一个元素在右半段”的跨区间逆序对，三者相加就是答案。正是因为任意逆序对只有三种归属：全在左、全在右、一左一右，所以分治可以把问题自然地拆成互不重叠的三个部分，不会重复也不会遗漏。

这里有一点容易被忽略：左右两半的内部逆序对，在递归求子数组排序时已经统计完了；真正需要动脑筋的是跨区间部分。如果直接暴力统计跨区间，复杂度又会回到 O(n²)，因为每个左半元素都可能和右半元素比较。分治的妙处在于，递归函数在返回之前已经把左右子数组都排成升序，这样合并左半和右半的时候，就能利用“有序”来批量计数，把 O(n²) 的比较压缩成 O(n)。

2.2 合并有序数组时，怎么“顺便”把逆序对算完

过程可以这样看。假设左半有序数组是L，右半有序数组是R，我们用一个归并循环把它们合并成完整的有序数组。维护两个指针i和j，分别指向当前正在比较的L元素和R元素。

• 如果L[i] <= R[j]，说明L[i]不大于右半当前元素；又因为R是有序的，R[j]后面的元素都比R[j]大，所以L[i]不会和R[j]以及它后面的任何元素构成逆序对。此时直接把L[i]放到合并结果里，i后移。
• 如果L[i] > R[j]，说明R[j]小于当前左半元素。更关键的是，因为L是有序的，L[i]后面所有的元素都不会小于L[i]，自然也都大于R[j]。这些左半元素在原始数组中的位置都在R[j]的左侧，值又都比它大，所以每一个都和R[j]构成一个逆序对。也就是说，当遇到这个情况时，可以一次性加上“左半剩余元素个数”个逆序对，然后把R[j]放入合并结果，j后移。

这个技巧就是整道题的核心。举一个小例子，如果左半是[5,7]，右半是[4,6]，合并时第一次比较5和4，5>4，于是5和7这两个左半元素都与4构成逆序对，一次性加2；后面5和6比较，5<=6不计数；7和6比较，7>6，再加1。总计跨区间逆序对3个，加上左右半段内部的逆序对，就得到了完整答案。

2.3 为什么标配是归并排序，而不是快速排序

分治算法一大把，快速排序也是分治，但很少有人用快排统计逆序对。原因在于快排在 partition 之后，pivot 左右两侧虽然满足大小关系，但各自内部并不保证有序。你在 partition 过程中根本不知道某个右侧元素前面到底还剩多少个左侧元素比它大，所以没有办法批量计数。而归并排序的合并阶段面对的是两个有序数组，可以沿着“有序性”这条线一次性扫描完成统计。换句话说，不是所有分治都适合统计逆序对，归并排序的形态天生契合这个需求。

顺带说一句，网上常能看到“分治法求一个n元素数组中最大元素的位置”，这也是分治的入门小例子，做法是把数组分为两半，分别求最大，再比较两个最大值返回位置。它和逆序对统计没有直接关系，但能帮初学者理解“分解-解决-合并”的框架。

3. 完整代码和一步步推演

3.1 C++ 版本：最常用、也最容易写错

先给一份能直接跑的 C++ 代码。为了在递归里不反复申请大数组，我用一个临时vector存放合并结果，合并完再写回原数组对应区间。

#include <vector> #include <cstdio> using namespace std; long long mergeSortCount(vector<int>& nums, int left, int right) { if (left >= right) return 0; int mid = left + (right - left) / 2; long long cnt = mergeSortCount(nums, left, mid) + mergeSortCount(nums, mid + 1, right); vector<int> tmp(right - left + 1); int i = left; int j = mid + 1; int k = 0; while (i <= mid && j <= right) { if (nums[i] <= nums[j]) { tmp[k++] = nums[i++]; } else { cnt += mid - i + 1; tmp[k++] = nums[j++]; } } while (i <= mid) tmp[k++] = nums[i++]; while (j <= right) tmp[k++] = nums[j++]; for (int p = 0; p < (int)tmp.size(); ++p) { nums[left + p] = tmp[p]; } return cnt; } int main() { vector<int> nums = {7,5,6,4}; long long ans = mergeSortCount(nums, 0, (int)nums.size() - 1); printf("%lld\n", ans); return 0; }

这份代码里最关键的一行就是cnt += mid - i + 1。因为当前区间下标是闭区间[left,right]，左半部分是[left,mid]，所以当右指针指向的元素小于nums[i]时，左半从i到mid一共还剩mid-i+1个元素，它们全都在原位置排在当前右元素之前，且值都比它大，所以全部计入答案。用long long承接答案是因为最坏情况逆序对数量接近n²/2，int很容易溢出。

3.2 Python 版本：更容易照葫芦画瓢

很多刷题场景用 Python，代码风格可以更简洁。下面的版本拆成两半分别递归，再把结果合并，最后返回排序后的数组和逆序对数。

def merge_sort_count(nums): if len(nums) <= 1: return nums, 0 mid = len(nums) // 2 left, cnt_l = merge_sort_count(nums[:mid]) right, cnt_r = merge_sort_count(nums[mid:]) merged = [] i = j = 0 cnt = cnt_l + cnt_r m, n = len(left), len(right) while i < m and j < n: if left[i] <= right[j]: merged.append(left[i]) i += 1 else: cnt += m - i merged.append(right[j]) j += 1 merged.extend(left[i:]) merged.extend(right[j:]) return merged, cnt

Python 版本因为没有int溢出问题，数字再大也能撑住，但要注意切片会让空间开销增加。如果在内存极敏感的工程里，更推荐用 C++ 那种传下标的方式。不过面试现场用这种写法的好处是直观，每层递归都返回排好序的数组，计数规则一眼就能看懂。

3.3 手推一遍[7,5,6,4]，看答案怎么凑出来

还是用刚才的例子。第一次分解得到[7,5]和[6,4]；继续分解到单元素[7]、[5]、[6]、[4]。

合并[7]和[5]：7>5，左半还剩1个元素，所以跨区间逆序对 +1，得到有序数组[5,7]。 合并[6]和[4]：6>4，同样 +1，得到[4,6]。 最后合并[5,7]和[4,6]：

5>4，左半元素是5、7，剩余2个，所以 +2，右侧4进入结果，j移到6；5<=6，左侧5进入结果，i移到7；7>6，左半剩余1个，所以 +1，右侧6进入结果； 最后把7放入，合并得到[4,5,6,7]。

整个过程中cnt是1+1+2+1=5，和最开始手数的答案完全一致。注意第二次合并时，7>4和7>6这两个逆序对并不是靠两次独立比较得到的：当5>4时，机器已经通过“批量计数”把7也一起算进去了。这种批量感，就是分治算法效率的来源。

3.4 复杂度小结

归并排序求逆序对的时间复杂度是 O(n log n)，因为每次合并把所有元素扫一遍，递归深度是 log n；空间复杂度是 O(n)，主要来自临时数组，递归栈只占 O(log n)。它不会改变原数组的相对顺序，所以是一种稳定排序。相比暴力 O(n²)，n 越大优势越明显。当n从1万涨到100万，暴力几乎不可用，而归并排序只需要约2000万次操作，任何现代语言都能轻松跑完。

4. 从“交易逆序对”到其他算法：这个问题远不止一种解法

4.1 先别把“字符串逆序”和“逆序对”混为一谈

在相关搜索里看到很多人找“字符串逆序 c语言”“字符串逆序输出”之类的内容，这里必须提醒一下：字符串逆序是把整体字符倒过来，比如"abc"变成"cba"，这属于字符串操作；而逆序对是统计数组中“前面比后面大”的对子数量，属于排列性质。两者只有“逆序”两个字相同，思路完全不同。如果你在网上搜资料，发现自己写的代码怎么都对不上答案，先看看是不是把这两个概念弄混了。字符串逆序通常用双指针或者栈就能解决，逆序对则需要分治或树状数组，复杂度也不在一个量级。

4.2 为什么题目要叫“交易逆序对的总数”

这道题的本质只是数组逆序对统计，但题面偏偏带上了“交易”两个字，让不少人一开始摸不着头脑。类比到实际场景，逆序对确实能描述金融序列里的“无序程度”：把股票每日价格按时间排成数组，如果出现某天价格比之后某天高，那就在时间序列上形成一个“高点在后”的反向关系，逆序对数量越多，说明价格回调越频繁，走势越不稳定。很多量化分析会用类似概念衡量价格序列和某个基准序列的偏离程度。当然，刷题时不用想这么复杂，把“交易”当成包装，直接抽象成数组就行。

4.3 树状数组求逆序对：另一种高频思路

除了归并排序，树状数组（Binary Indexed Tree）也是求逆序对的常见解法，而且在某些动态求逆序对的问题里更灵活。基本步骤是先对数组做离散化，把所有元素映射到1..m的排名；然后从右往左遍历原数组，每遇到一个元素，就查询树状数组中值域在它左侧的所有已出现元素个数，这些元素都位于它右侧但值比它小，因此全部构成逆序对，累加后把当前位置的排名插入树状数组。这样同样是 O(n log n)，但代码更偏向数据结构。

举个例子，数组[7,5,6,4]，离散化后值域排名是4,2,3,1。从右往左遍历到4（排名1），查询比1小的没有，插入1；遍历到6（排名3），查询比3小的已出现元素有排名1，所以 +1，插入3；遍历到5（排名2），查询比2小的有排名1，+1，插入2；遍历到7（排名4），查询比4小的有1、2、3，+3。总计5，结果一致。

4.4 现实中的用途：逆序对不是只有笔试才用

逆序对在实际工程里也有不少影子。第一，它能衡量一个序列离“完全有序”有多远，很多排序算法（比如插入排序）的交换次数就等于逆序对数，所以知道了初始逆序对，就能预估某些排序算法的实际性能。第二，在推荐系统里，把“时间顺序”和“模型打分顺序”两个序列放在一起算逆序对，可以量化推荐结果对时间因素的破坏程度。第三，在数据库维护有序索引时，逆序对数量也常被用来估算索引是否需要重建。虽然不是每个业务都会直接调用求逆序对的函数，但它的思想已经渗透到很多排序和统计场景中。

5. 实际踩坑记录和面试防身术

5.1 等号问题：重复元素最容易翻车

统计逆序对必须满足严格大于，所以相等不能计数。以数组[1,2,2,1]为例，正确答案是两对：两个位置的2分别和最后一个1构成逆序对。合并时如果写成nums[i] < nums[j]，那么当nums[i]=2、nums[j]=2时也会进入 else 分支，错误地把相等的两个2也算成逆序对，答案就会偏大。记住：合并比较时用的是<=，遇到相等时先放左半元素，让右半元素继续跟后面的左半元素比较。这个细节在面试手写代码时非常容易被追问，务必注意。

5.2 边界条件：left、mid、right 一定不能重

递归函数里最容易写错的是mid和mid+1的边界。如果right-left是0或负数，直接返回0；mid用left + (right-left)/2可以避免整数溢出。在 while 循环里，左半段的区间是[left, mid]，右半段是[mid+1, right]，写合并复制回原数组时要保证下标一一对应。很多初学的人会出现“合并到一半数组越界”或者“排序完发现数组少了一块”的诡异现象，基本都是边界考虑不周。建议每次写完都先用一个随机数组做对拍，确认原数组被完整排序。

5.3 返回值记得用长整型

一个很容易被忽略的坑是：当n达到10^5时，完全逆序的数组答案n*(n-1)/2大约是4.99995×10^9，已经超过int上界。如果题目没有特殊说明，用int接收返回结果会在线判定上拿到 Wrong Answer，而且这种 WA 非常难排查，因为直觉上“数一数能有多少对”也不会想到会溢出。C++ 里最好统一使用long long，Java 用long，只有 Python 可以放心使用int。养成习惯，别在这么基础的地方丢分。

5.4 副作用：归并排序会把原数组改掉

很多人的主函数里先定义好nums，然后调用统计函数，完事之后还想继续用nums做别的事，结果发现nums已经被排好序了。因为归并排序本质上是把数组逐渐变成有序，过程中会写入临时结果。如果不想影响原数组，可以在统计函数入口先复制一份，例如 C++ 里：

long long countInversions(vector<int>& nums) { vector<int> work = nums; return mergeSortCount(work, 0, (int)work.size() - 1); }

这个封装看似简单，却能在联调时避免不少“数据被改了”的离谱问题。

5.5 调试速查表

为了方便复习，我把常见的错误状态整理成了一个表：

这张表我每次面试前都会扫一遍，基本能覆盖所有新手常见问题。

5.6 说说我自己的理解方式

最后分享一个个人体会。归并排序求逆序对，网上模板满天飞，但很多人背完以后一星期就忘。我后来发现，真正让它记住的，不是那一行cnt += mid - i + 1，而是一个画面：合并两个有序数组时，右边弹出一个数，左边还剩多少个数没有弹出，这些数全都比它大，而且全都排在它前面，所以每一个都是它制造的逆序对。把“还剩几个、就加几个”这六个字理解透，分治求逆序对就不再是模板题，而是一道随时可以推出来的基础题。