逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。
怎么求逆序对呢，我们今天用归并排序来说，资资给我们讲的时候就说归并排序80%会考。我也不知道考没考，我缓考了。
emmm，归并排序大家可能记不太清了，我再给大家提一下。
所谓归并排序就是将一组数进行无数次分割，将它划分成一个个有序的区间，然后再将这一个个有序的区间一个个合并成有序的区间。
怎么划分？
那这就是一个二分的过程了。我们每次将一段数进行分开，我们在这里引入一个mid为中间位置，一直将l到mid进行分，直到mid=l，这说明他已经将一个个连续的区间划分成一个个独立的区间了。这样我们在一个个进行合并的时候由于我们划分成两个区间（即两个两个区间进行合并），并且每一个区间都是有序的。
实际上归并排序的交换次数就是这个数组的逆序对个数
我们可以这样考虑：
归并排序是将数列a[l,r]分成两半a[l,mid]和a[mid+1,r]分别进行归并排序，然后再将这两半合并起来。
在合并的过程中（设l<=i<=mid，mid+1<=j<=h），当a[i]<=a[j]时，并不产生逆序数；当a[i]>a[j]时，在前半部分中比a[i]大的数都比a[j]大，将a[j]放在a[i]前面的话，逆序数要加上mid+1-i。
因此，可以在归并排序中的合并过程中计算逆序数。
归并排序求逆序对其实就是在归并排序的基础上加上了一个统计逆序对的过程。
#include <bits/stdc++.h> using namespace std; int arr[100010]; int temp[100010]; long long merge_sort(int arr[],int l,int r) { if(l >= r) { return 0; } long long cnt = 0; int mid = l + r >> 1; cnt += merge_sort(arr,l,mid); cnt += merge_sort(arr, mid + 1, r); int k = 0; int i = l; int j = mid + 1; while(i <= mid && j <= r) { if(arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { cnt += mid - i + 1; temp[k++] = arr[j++]; } } while(i <= mid) { temp[k++] = arr[i++]; } while(j <= r) { temp[k++] = arr[j++]; } for(i = l,j = 0;i <= r;i++,j++) { arr[i] = temp[j]; } return cnt; } int bubble_sort(int arr[], int len) { int ans = 0; int i, j; for (i = 0; i < len - 1; i++) //外层循环控制趟数，总趟数为len-1 { for (j = 0; j < len - 1 - i; j++)//内层循环为当前i趟数 所需要比较的次数 { if (arr[j] > arr[j + 1]) { ans++; swap(arr[j], arr[j + 1]); } } } return ans; } int main() { int n; cin>>n; for(int i = 0;i < n;i++) { cin>>arr[i]; } cout<<merge_sort(arr,0,n-1)<<endl; // cout<<bubble_sort(arr,n)<<endl; // for(int i = 0;i < n;i++) // { // cout<<arr[i]<<" "; // } return 0; }
