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++]。

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

Answer 2

第一个n
的逆序数是0
第二个n-1的逆序数是1
第三个n-2的逆序数是2
.....................................
第n个1
的逆序数是
n-1
∴逆序数是0+1+2+3+........n-1
(n-1+0)*n/2
=n(n-1)/2
因为n(n-1)是连续的两个自然数。
∴当n或(n-1)是4的倍数时，是偶排列
当n或(n-1)是只能是2的倍数时,是奇排列

Answer 3

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。
T=1+0+2+1=4，偶排列
21
54，53
43

Answer 4

2-5
2-4
2-3
1-5
1-4
1-3
5-4
5-3
4-3
逆序数为9，为奇数，排列的奇偶性：奇排列