承接上文归并排序及小和问题
归并排序扩展-逆序对问题
在一个数组中，左边的数如果比右边的数大，则两个数构成一个逆序对，找到逆序对的数量
比如 3,2,4,5,0
所有的逆序对是 3,2; 3,0; 2,0; 4,0; 5,0
上文的小和问题是 求右边有多少个数比左边的数大
这个题目是求右边有多少个数比左边的数小
所以逆序对的问题和小和问题是等效的
归并排序为什么不会重算和漏算或归并排序的实质
一个数组[a,b,c,d,e,f,g,h,i]
就看数字c 看它经历什么样的心路历程
一开始数组是这么被分的
当a和b整体产生小和变成有序之后 跟c合并的过程
c不产生小和
因为右组所有的数都不会产生小和
然后a,b,c就变成了一个有序的部分
c在哪里不重要
接下来 a,b,c这个整体和d，e所在的组合并
这样合并的时候c产生的小和数量它的范围被扩到右侧的d,e范围上
d，e这个范围上有可能有比c大的（有0个比c大的，有1个比c大的，有2个比c大的）
具体哪种情况不重要，重要的是c已经把自己求有多少个数比自己大的范围扩到d，e上
然后a,b,c,d,e共同构成一个有序的部分，c在哪里不重要
重要的是下面会和f,g,h,i所在的数组
去求这个范围上有多少个数比c大
c先去求de范围有多少个数比c大
再去求f,g,h,i范围有多少个数比c大
a,b,c,d,e,f,g,h,i 这些数成为一个整体
c在哪个位置不重要
如果右侧还有一个范围 则c所在的这个整体会继续求那个右侧的范围有多少个数比c大
c在求有多少个数比它大的范围是右侧依次往外扩的
所以说它不会漏算
为什么说不会重算？
因为c一旦跟某一个右组合并了之后
它们就会变成一个组
而一个组内部是不会产生小和的
只有左组和右组之间才会产生小和
c只是一个普通的一员而已 对于所有的数来说都是这个过程
所以求每一个数的小和都不会漏算 都不会重算
荷兰国旗问题
怎么把一组数做划分 左边都小于它 右边都大于它 中间都等于它
1、问题1
左边都小于等于number，右边都大于number
不要求有序 只要求对数组进行划分
比如 一个数组是 3,5,6,7,4,3,5,8
number是5
所有小于等于5的放左边，大于5的放右边
准备一个变量表示小于等于区域的右边界
一开始在数组的最左侧
当前来到的位置是i位置
当来到i位置就会有两种情况
第一种是小于等于number的
第二种是大于number
1)i所在当前位置的数<=number
把当前数[i]和<=区的下一个数做交换
然后<=区往右扩一个位置
当前数也跳下一个i++
如图第一个数是3
3<5
3和<=区的下一个数也是3 即自己和自己交换
交换完之后 <=区往后扩
当前数跳下一个
当前数是5 也满足 <=number
5和5 自己和自己交换 <=区向右扩
当前数下移
此时当前数6大于5 命中第二种情况
i直接跳下一个
当前数是4 ,<=number的
把它跟<=区的下个数做交换
4和6做交换
<=区往右扩
当前数也跳下一个
有中了情况1
把当前数和下个数做交换
<=区往右扩
当前数跳下一个
当前数是8 ，i++ 越界了
此时已经做到了 <=区都是<=5的 ，右侧都是>5的
i是当前来到的位置
右侧是还未看过的位置 待定区域
<=区域里面都是<=已经做到的位置
<=区域和i中间的位置大于区域
荷兰国旗问题🇳🇱
小于区域放左边 中间都是等于number的 右边都是大于number的
小于和大于区域都不要求有序
当然可以没有小于区域或等于区域或大于区域 如果有的话 严格分开
时间复杂度是O(N) 用有限几个变量
定义两个变量 一个是小于区域的左边界
一个是大于区域的右边界
