为什么将前后2个数对调一下,逆序数就会加1或者减1
发布网友
发布时间:2022-05-16 02:18
我来回答
共1个回答
热心网友
时间:2023-10-09 04:04
交换相邻的两个数
设原排列为 a1a2...aiai+1...an
交换 ai与ai+1, 排列为 a1a2...ai+1ai...an
易知, ai,ai+1 与其他数构成的逆序不变
若 ai<ai+1, 则多了一个逆序 ai+1ai
若 ai>ai+1, 则少了一个逆序 aiai+1
所以, 交换相邻的两个数, 排列的逆序数加1或减1
即改变了排列的逆序数的奇偶性