Question

求排列21543的逆序数并指出该排列的奇偶性？谢谢大家了！！

Answer 1

是：n-1，n-2，??，2，1，n，是吧。如果是，那么： n-1的逆序数=0 n-2的逆序数=1 ???? 2的逆序数=n-3 1的逆序数=n-2 n的逆序数。

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

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

扩展资料：

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

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

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

long merge(int low,int mid,int high)。

int i=low,j=mid+1,k=low。

long count=0。

while(i<=mid&&j<=high。

if(is1[i]<=is1[j])// 此处为稳定排序的关键，不能用小于。

is2[k++]=is1[i++]。

参考资料来源：百度百科-逆序数