归并排序及小和问题

大家好，欢迎来到IT知识分享网。

归并排序mergeSort

先让左侧部分排好序

变成了1，2，3

再让右侧部分排好序

变成了2，5，6

怎么样让它整体都有序呢

merge在一起就行了

准备一个辅助空间 谁小拷贝谁

左侧下标指向1

右侧下标指向2

左侧如果小于等于右侧

先拷贝左侧的

如果右侧小于左侧

则先拷贝右侧

如图 1小拷贝1 指针往下动

相等的时候 默认拷贝左边的 指针再往右动

3>2 右侧小拷贝右边的 指针往右动

3<5 拷贝3 指针越界 将剩下的拷贝过来

小结

左侧部分排好序

右侧部分排好序

利用merge的过程 使得整体都有序

在辅助空间有序了 再拷贝回原数组

代码

1、L=R 就一个数 return

2、先左侧排序

3、再右侧排序

4、此时整体还无序

所以有一个merge的过程

整个范围是L~R

左侧范围是L~M

右侧范围是M+1 ~ R

所有用L、M、R表示2个区域的意思

左侧和右侧各自都有序了

再来看下merge的过程

a、先准备一个辅助空间help

L-R上一共有多少个数 就开多大的空间

i 这个 变量专门给help使用的

变量p1是左侧部分的下标指向L位置

变量p2是右侧部分的下标指向M+1位置

b、p1 没有超过M并且p2没有超过R 表示都没有越界

在都没有越界的情况下 谁小拷贝到help中去

p1位置的值 如果小于等于p2位置上的值

谁小则拷贝到help的i位置上去

假设p1位置上的值是1

p2位置上的值是3

1<3 则将1放到help的i位置上去

c、p1++ 就说明p1移动到了下一个位置

i++ 也来到了下一个位置

比如p1指向了4

4 >3 将3放到help i位置

d、i往下移动，p2也往下移动 比如指向了7

4<7 将4拷贝

e、如果p1没有越界 p2越界了

就把p1剩下的拷贝到help中去

或者 如果p2没有越界 p1越界了 就把p2剩下的拷贝到help中去

这2个while循环只会执行一个

要么p1越界要么p2越界

f、把help中的内容拷贝到原数组中

看这个过程是否可以用master公式

整个过程的数据量是N的规模

第一个子问题是N/2规模

第二个子问题也是N/2规模

即调用子问题调用了2次

除了子问题之外 剩下的过程是什么时间复杂度?

这个蓝色区域是O(1)时间复杂度

关键要看merge的时间复杂度是多少？

左侧指针只往右走不回退

右侧指针也是只往右走不回退

每一次只有一个指针动

左侧或右侧越界了之后 另一侧就把剩下的走完

所以整个过程是O(N)的时间复杂度

把help拷贝到数组中的过程也是O(N)的

所以整体的时间复杂度是

T(N)=2 * T(N/2) + O(N)

是符合master公式的 a=2,b=2,d=1

所以 = d

对应的时间复杂度是O(N * )

mergesort实质

选择排序、冒泡排序和插入排序 都是N^2的算法

为什么它们比mergesort差呢

因为它浪费了大量的比较行为

比如选择排序

0~N-1范围 比较了差不多N次 才知道哪个数放到0位置上

1～N-1次比较了N-1次 搞定一个数 放到1位置上

每一轮的比较都是独立的

比较这么多次 才搞定了一个数

归并排序没有浪费比较行为

归并排序是左侧的指针和右侧的指针

依次从左到右 左侧跟右侧的比

比较行为信息没有浪费 被留下来了

变成了整体有序的部分

正是因为这样的原因 它变成了O(N * )

外排序就是两个指针比较的东西拷贝到一个外部的数组中去，然后再拷贝回来

额外空间复杂度是O(N)表示最多只用准备N的空间就够了

每次merge的时候准备一个空间 用完就释放了

最多准备长度为N的空间 每一次复用该空间

题目

小和问题

[1,3,4,2,5]

1左边比1小的数 没有 所以1的小和是0

3左边比它小的数只有一个1 所以3的小和是1

4左边比它小的是1，3 累加为4 即4的小和是4

2左边比它小的只有一个1 ，2的小和是1

5左边都比它小 所以5的小和是1+3+4+2=10

整个数组的小和是所有小和累加起来

0+1+4+1+10=16

暴力解的方式

来到i位置的时候 左边遍历一下

所有比它小的都求出来

每到一个位置i 左边都遍历一下

等差数列

这样的方式时间复杂度是O(N^2)

求小和的过程能不能做到N*LogN

在mergesort的过程中就可以依次求出整个数组所有的小和来

比如 [1,3,4,2,5]

对1来说 右边有多少个数比1大呢

4个数 所以就产生4个1的小和

对3来说 右边有2个数比3大 所以产生2个3的小和

对于4来说 右边有1个数比4大 所以产生1个4的小和

对于2来说 右边有1个数比2大 生成1个2的小和

对于5来说 右边没有数 产生0个5的小和

一共还是16个小和

按照这样的思路求和原始问题是等效的

原来是求一个数左边有多少个数比它小都算作这个数的小和

反过来 求一个数 右边有多少个数比它大 依次求出它的小和

两者是等效的

一个数右边有多少个数比它大 可以用归并排序求解

对于[1,3,4,2,5]来说 1，3，4是左侧，2，5是右侧

对于1，3，4来说1，3是左侧，4是右侧

对于1，3来说1是左侧，3是右侧

对于2，5来说2是左侧，5是右侧

对于1和3来说 左侧指针指向1，右侧指针指向3

当左侧比右侧小的时候 1小于3 1的右侧有1个数比1大 所以产生1个1的小和

拷贝到外排序数组中

然后左侧就越界了

右侧的3也拷贝进来

将外排序数组中的1，3修改回原数组还是1，3

即在1～3范围上merge的时候 产生了1个1的小和

此时左侧的1，3和右侧的4分别已经排好序了 然后在一起merge

左侧指针指向1 右侧指针指向4

右侧是4 只有4这一个数比1大 所以此时产生1个1小和 拷贝到外排数组

移动左侧下标 指向3 右侧只有一个数大于3 产生1个3的小和

拷贝到数组

左侧再移动 就越界了 右侧的4拷贝下来

外排数组拷贝回原数组

2和5同理

2的右侧只有一个5大于2 所以产生了1个2的小和

将2放入排序数组

左侧指针再移动 越界

将5拷贝到外排数组

再将外排数组中的2，5拷贝进原数组

此时1,3,4和2，5要merge

左侧指针指向1

右侧指针指向2

右侧有2个数比1大 所以产生2个1的小和

将1拷贝到外排数组中

左侧置针移动到3

右侧的2小于3不产生小和 所以将2拷贝到外排数组

右侧下标移动到5

3小于5 右侧有一个数比3大 产生1个3的小和

把3拷贝到外排数组中

此时左侧下标指向4 右侧下标指向5

所以右侧还有一个5

对于4来说 右侧只有一个数5比4大 所以产生1个4的小和

将4拷贝进来

左侧指针再右移 下标越界 将右侧剩下的5拷贝进来

再拷贝进原数组

所以最终的排序是1，2，3，4，5

每次的小和分别是1，1，3，2，2，3，4 一共也是16

在merge的过程中 每一个数求有多少个数比这个数大的过程

是分批的 不遗漏的 也不重算 依次找到的

这里需要注意的地方是如果左侧和右侧相等的时候 一定要拷贝右侧且不产生小和

因为如果拷贝左侧 就不知道右侧有几个数比左侧大了

拷贝哪一侧 那一侧的指针就会往右移动

比如拷贝右侧 右侧指标p2往右移动 r-p2+1 就是右侧比左侧当前指针所指向的数大的个数

代码

当l=r的时候 小和就是0 也不需要排序

找中点位置

左侧排序并且求小和数量 加上 右侧排序并且求小和的数量

加上 左侧和右侧merge的过程产生小和的数量

就是整个小和的数量

1、

在两侧指针都不越界的情况下

只有左侧比右侧小

才产生小和数量增加的行为

增加多少呢

r-p2+1

表示当前右侧比当前左侧p1所指的数大的个数

个数乘以当前左侧所指的那个数就是小和增加的量

如果左侧不比右侧的小 小和增加的数量是0

2、接下来的拷贝：在当左侧比右侧小的时候 才拷贝左侧

当左侧大于等于右侧的时候 先拷贝右侧

3、越界或拷贝回原数组 过程不产生小和