侧边栏壁纸
博主头像
Z同学博主等级

工作磨平激情前,坚持技术的热忱。 欢迎光临Z同学的技术小站。 分享最新的互联网知识。

  • 累计撰写 290 篇文章
  • 累计创建 57 个标签
  • 累计收到 98 条评论

名词介绍- 什么是逆序,我们如何计算逆序数

Z同学
2022-01-18 / 0 评论 / 5 点赞 / 4,213 阅读 / 807 字
温馨提示:
本文最后更新于 2022-01-18,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

1. 前言

简单介绍下逆序的概念和示例讲解。

2. 定义

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

一个排列中所有逆序的总数叫做这个排列的逆序数。逆序数为奇数的排列叫做奇排列,逆序数为偶数的排列叫做偶排列。(来自百度百科)

数学最大的魅力就是,把定义用文字描述了,我们也弄不懂它到底是干啥的。

就是说一对数的前后位置与大小顺序相反

我们结合实际场景就能理解了。逆序是线性代数中的概念。

3. 示例

我们通过实例来理解什么是逆序。

我们如果有一个数列: 1,2,3,4,5,6 那么这个是一个从小到大的有序排列。我们定义它为标准顺序的话。

那么如果我们颠倒成: 2,1,3,4,5,6 那么这个排列中就有了一个逆序。(2,1) 而我们的例子中

只有这一种情况,那么这个排列的逆序数就是:1 然后这个排列就可以叫做奇排列。

我们理解了上面的介绍之后,我们可以结合多个实例来自己判断是否理解正确。

示例1:

(1,3,5,2,4,6) 
逆序:(3,2),(5,2),(5,4)
逆序数:3

然后这个数列就是奇排列

示例2:(判断前面是否有比自己还小的数)

(5,4,3,2,1)
逆序:
5之前0个。
4之前1个。
3之前2个。
2之前3个。
1之前4个
逆序数:0+1+2+3+4 = 10

然后这个数列就是偶排列。

示例3:

(1,3,4,2,8,6,5)
逆序情况:
2之前有2个数比它大:2
6之前有1个数比它大:1
5之前有2个数比它大:2
逆序数为:2+1+2 =5 

然后这个数列就是奇排列。

4.总结

逆序是一个很简单的概念。就是线性排列的数组中,没有按照顺序进行排列的我们称为逆序(顺序颠倒了)。

然后一个排列中,全部的颠倒个数就叫做逆序数了。

不要被它的名词给吓退了。就是一个简单的定义概念而已。

而我们如果在算法题中看到逆序的介绍。出题者想表达的意思就是,这个数组或集合中的数值是混乱排序的,并不是按照一个从小到大或从大到小的有序顺序进行排序的。

5

评论区