逆序数是指在一个排列中，一对数的前后顺序与大小顺序相反的对数，求逆序数最常用的方法包括暴力枚举法、归并排序法和树状数组法，其中归并排序法在时间复杂度上最优，适用于大规模数据。 例如，对于序列 [3,1,2]，逆序对有 (3,1) 和 (3,2)，因此逆序数为2。
暴力枚举法是最直观的方式：遍历所有数对 (i, j) 且 i < j，若 a[i] > a[j] 则计数加1。时间复杂度 O(n²)，适合小规模数据。归并排序法则在合并过程中统计逆序数：当左半部分元素大于右半部分元素时，逆序数增加左半部分剩余元素个数。时间复杂度 O(n log n)，稳定且高效。树状数组法通过离散化将数值映射为索引，然后依次插入并查询比当前元素大的已插入数，时间复杂度 O(n log n)，但需要额外空间。实际应用中，对于大型数组（如10万以上），推荐使用归并排序法；对于编程竞赛或面试，常要求手写归并排序实现。
此外，逆序数的概念在算法分析（如排序算法的稳定性）、线性代数（行列式定义）以及数据库索引优化中都有重要应用。掌握多种求法有助于根据场景选择最优方案。
【常见问题】
问题1：逆序数怎么求最快？
回答1：逆序数最快求法通常采用归并排序法，时间复杂度为O(n log n)，在数据量较大时性能最优。树状数组法同样能达到O(n log n)，但需要额外离散化处理。
问题2：逆序数怎么求如果数组中有重复元素？
回答2：求逆序数时，重复元素通常不被视为逆序对（因为前后顺序与大小顺序相等，不满足“大于”条件）。在归并排序和树状数组实现中，需要严格判断a[i] > a[j]才计数，相等时不计数。
问题3：逆序数怎么求在编程中实现？
回答3：以Python为例，归并排序求逆序数：定义merge_sort函数，在合并时若左半部分当前元素大于右半部分当前元素，则逆序数增加左半部分剩余元素个数，递归返回逆序数之和。代码可参考经典算法模板。
问题4：逆序数怎么求与排列奇偶性有什么关系？
回答4：逆序数的奇偶性决定排列的奇偶性。若逆序数为偶数，排列为偶排列；若为奇数，则为奇排列。这在行列式计算中用于确定符号——逆序数为奇时该项取负号。