什么是逆序数，可不可以举个例子

如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。也就是说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个 不同的自然数，可规定从小到大为标准次序）。

归并排序

直接计数法虽然简单直观，但是其时间复杂度是 O(n^2)。一个更快（但稍复杂）的计算方法是在归并排序的同时计算逆序数。

下面这个 C++ 编写的例子演示了计算方法。函数 mergeSort() 返回序列的逆序数。

int is1[n],is2[n];// is1为原数组，is2为临时数组，n为个人定义的长度。