归并排序及小和问题(下)

简介: 归并排序及小和问题(下)

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

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

拷贝到外排序数组中

然后左侧就越界了

右侧的3也拷贝进来


image.png

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

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

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

image.png

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

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

image.png

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

拷贝到数组

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

image.png

外排数组拷贝回原数组

image.png

2和5同理

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

将2放入排序数组

左侧指针再移动 越界

将5拷贝到外排数组

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

image.png

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

左侧指针指向1

右侧指针指向2


image.png

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

image.png

将1拷贝到外排数组中

左侧置针移动到3

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


image.png

右侧下标移动到5

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

把3拷贝到外排数组中


image.png

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

所以右侧还有一个5

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

将4拷贝进来

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


image.png

再拷贝进原数组

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

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

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

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

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

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

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

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

代码


image.png

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

找中点位置

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

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

就是整个小和的数量

image.png

1、

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

只有左侧比右侧小

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

增加多少呢

r-p2+1

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

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

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

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

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

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

相关文章
|
6月前
归并排序详解
归并排序详解
56 1
|
人工智能 BI
归并排序
归并排序。
44 0
|
5月前
|
算法 搜索推荐 Java
归并排序就是这么容易
归并排序就是这么容易
40 2
|
6月前
|
存储 算法 搜索推荐
C++归并排序的实现
C++归并排序的实现
|
6月前
|
搜索推荐
归并排序是什么
归并排序是什么
20 归并排序
20 归并排序
42 0
|
存储 算法 搜索推荐
归并排序(看了就会)
归并排序(看了就会)
|
搜索推荐 算法 C#
C#——归并排序
C#——归并排序
152 0
|
算法
【2. 归并排序】
归并与快排不同: >快速排序: >- 分界点是随机数组里面的一个`数`来分,使得左边都是<= 这个数,右边 >= 这个数 (`数值`) >- 先分完,在分别递归俩边 > >归并排序: >- 先递归俩边,在进行合并操作 >- 分界点是`整个数组中间的位置`(`下标值`)
95 0
【2. 归并排序】