Question

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

Answer 1

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

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

归并排序

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

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

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

Answer 2

你好!
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。——这是北大《高等代数》上的定义。