逆序对

逆序对

在序列 $S[0,n)$ 中，若 $0<i<j<n,S[i]>S[j]$，称 $(i,j)$ 为一个逆序对。

统计

• 暴力算法：$O(n^2)$
• 可在归并排序过程中统计 归并排序时，两侧的逆序对数可递归统计，只需统计跨越分界的逆序对。 对于跨越分界的逆序对，可以在二路归并的同时完成。假设对于左侧归并到 $i$，右侧归并到 $j$，分界为 $mi$，则逆序对增加 $mi-i$ 对