关于逆序对的三种解法
今天学习了逆序对，关于逆序对的三种解法做一个介绍，方便复习。
什么是逆序对？
设 A 为一个有 n 个数字的有序集(n>1)，其中所有数字各不相同。
如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对。
逆序对的解法
第一种：冒泡法（暴力）
直接对原序列进行冒泡排序，统计交换次数，得到的交换次数=逆序对数。
第二种：归并排序
对原序列进行归并排序，在每次合并两数组时可以直接统计逆序对的个数。针对左有序序列中的第i号元素，和右有序序列中的第j号元素，若存在 a[j] < a[i] ，则a[i]后的所有
元素都大于a[j]。这种情况下 逆序对的个数result = mid - i + 1
第三种：离散化 + 树状数组
先利用离散化，一次性读入所有数据，然后记录读入数据的下标和值，按照值的大小对值和下标进行排序。得到新的数据后，建立以新的值（排序的序号）为下标的树状数组，树状数组的值为当前状态下该位值出现的次数。在每次向树状数组插入元素时，都利用树状数组查询比当前插入元素的值更大的元素出现的个数。
优质内容筛选与推荐>>
1、nyoj 929 密码宝盒
2、java移位运算
3、Leetcode 190. Reverse Bits
4、移位操作符
5、SERvet的表单
1、nyoj 929 密码宝盒
2、java移位运算
3、Leetcode 190. Reverse Bits
4、移位操作符
5、SERvet的表单