逆序数是n(n-1)/2。
假设n是偶数，则n＝2m，m是奇数或偶数，所以n(n-1)/2=m(2m-1)。这里的2m-1肯定是奇数，但是m可奇可偶，所以当m是奇数2k+1（此时n＝2m=4k+2）时，n(n-1)/2是奇数。当m是偶数2k（此时n＝2m=4k）时，n(n-1)/2是偶数。
假设n是奇数，则n＝2m+1，m是奇数或偶数，所以n(n-1)/2=m(2m+1)。同样的讨论，得到结论：当m是奇数2k+1（此时n＝2m+1=4k+3）时，n(n-1)/2是奇数。当m是偶数2k（此时n＝2m+1=4k+1）时，n(n-1)/2是偶数。
综上，当n=4k或4k+1是偶排列，当n=4k+2或4k+3时，是奇排列。
