造算法与数据结构基础到高级全家桶教程直击BTAJ等一线大厂必问算法面试题真题详解马士兵】https://www.bilibili.com/video/BV13g41157hK?p4vd_source04ee94ad3f2168d7d5252c857a2bf358

2.2

在新数组newArr[]开辟存储空间大小为R-L1也就是原始数组的元素个数。

左数组的范围arr[L]到arr[M]右数组的范围arr[M1]到arr[R]两个指针的范围小于等于各自组的右边界p1Mp2R。

当p1p2将p1指向的数拷贝到newArr[i]中然后指针和i都当p2p1则对p2进行相同操作当p1p2先拷贝p1再拷贝p2然后p1、p2、ii2

当p1先到达右边界则将p2往后的内容都拷贝到newArr[]中newArr[i]

arr[p1];

newArr[i]arr[p1]}else{newArr[i]arr[p2]}}//处理其中一个指针到达边界的情况while

){newArr[i]

arr[p2]}//如果要将排序后的新结果newArr替换掉旧数组arr则可以用for循环逐个替换for(

i0;

如果用master公式计算这个归并排序代码的时间复杂度T(N)

2*T(N/2)

解释左数组和右数组的数据量都是N/2且都是先组内排序再利用双指针遍历后放入数组遍历操作的时间复杂度是O(N)。

归并排序的时间复杂度O(NlogN)优于选择排序、插入排序等O(N…^2)的原因

在选择排序、插入排序中遍历一遍含n个元素的数组只能确定下来一个元素的位置其余的比较被浪费了。

而在归并排序中两个子数组的元素都是有序的因此每一次比较都能确定一个元素的位置并使指针后移继续比较后续的元素。

2.2.3

小和问题一个数组中遍历每个元素然后把左侧比当前数小的数累加起来得到这个数组的小和。

遍历开始前小和sum0

方法1O(N^2)。

使用最纯粹的遍历方法。

遍历数组然后将当前元素和左侧元素诸葛比较、加和得到小和。

方法2O(logN)。

使用了归并排序对于每个元素如果它的右侧有m个元素比它大则再加上m*当前元素的值。