##### 逆序对 - 逆序对 - **逆序对**指的是[[全序集排列]]中两个元素的位置顺序与元素顺序相反, 即对于排列 $P = (p_1, p_2, \dots, p_n)$, 如果存在 $i < j$ 且 $p_i > p_j$, 则称 $(p_i, p_j)$ 是一个逆序对. 逆序数 $\text{inv}(P)$ 是逆序对的总数, 衡量了排列的无序程度, 如果一个排列的逆序数是偶数, 则称这个排列为偶排列, 否则称为奇排列, 也是[[奇偶置换]]. 排列中奇排列和偶排列个数相等. 排列符号 $\text{sgn}(P)$ 由逆序数奇偶决定, 偶正奇负, 是一种交错性质 - $P = (p_1, p_2, \dots, p_n)$ - $\displaystyle\text{inv}(P) = \sum_{i < j} \mathbf{1}(p_i > p_j)$ - $\text{sgn}(P)=(-1)^{\text{inv}(P)}$