给定一个整数数组a[n]，若i<j，a[i]>a[j]，则<a[i],a[j]>称为一个逆序对。例如：数组（3， 1，4，5，2）的逆序对有<3,1>，<3,2>，<4,2>，<5,2>，其逆序对的个数称为逆序数，如数组 （3，1，4，5，2）的逆序数为4.

以下是求逆序数的算法：

1. 归并排序

归并排序是一种基于比较的排序算法，其时间复杂度为O(nlogn)，可以用于求逆序数。

具体思路是将数组不断二分，直到剩下单个元素，然后将两个有序的子数组合并，合并时需要统计逆序数。合并时，如果左边数组的当前元素a[i]大于右边数组的当前元素a[j]，则逆序数加上左边数组元素个数i到结尾的个数（因为左边数组是有序的，所以左边数组[i]到结尾都大于右边数组[j]）。

代码如下：

int mergeSort(int a[], int left, int right) {
if (left >= right) return 0; // 递归终止条件
int mid = (left + right) / 2;
int count = mergeSort(a, left, mid) + mergeSort(a, mid+1, right); // 递归求解左右子数组的逆序数
int i = left, j = mid+1, k = 0;
int temp[right-left+1];
while (i <= mid && j <= right) {
if (a[i] > a[j]) { // 左边数组当前元素大于右边数组当前元素
count += mid - i + 1; // 统计逆序数
temp[k++] = a[j++]; // 将右边数组当前元素放入临时数组
} else {
temp[k++] = a[i++]; // 将左边数组当前元素放入临时数组
}
}
while (i <= mid) temp[k++] = a[i++]; // 如果左边数组还有剩余元素，将其放入临时数组
while (j <= right) temp[k++] = a[j++]; // 如果右边数组还有剩余元素，将其放入临时数组
for (int i = left, k = 0; i <= right; i++, k++) a[i] = temp[k]; // 将临时数组中的元素复制回原数组
return count;
}

int countReversePairs(int a[], int n) {
return mergeSort(a, 0, n-1);
}

2. 树状数组

树状数组是一种高效的数据结构，可以用于求一段区间的和，可以用于求逆序数。

具体思路是将数组中的元素插入树状数组中，然后从右往左遍历数组，每遍历一个元素，在树状数组中查询小于该元素的元素个数，将其累加到逆序数中，然后将该元素插入树状数组中。

代码如下：

int lowbit(int x) { // 求x的二进制表示中最后一个1对应的值
return x & (-x);
}

void update(int c[], int n, int i, int val) {
while (i <= n) {
c[i] += val;
i += lowbit(i);
}
}

int query(int c[], int i) {
int sum = 0;
while (i > 0) {
sum += c[i];
i -= lowbit(i);
}
return sum;
}

int countReversePairs(int a[], int n) {
int c[n+1];
memset(c, 0, sizeof(c));
int count = 0;
for (int i = n-1; i >= 0; i--) {
count += query(c, a[i]-1); // 查询小于a[i]的元素个数
update(c, n, a[i], 1); // 将a[i]插入树状数组中
}
return count;
}