单页营销型网站模板下载,什么是新零售,photoshop电脑版怎么安装,网站域名备案密码【一周刷爆LeetCode#xff0c;算法大神左神#xff08;左程云#xff09;耗时100天打造算法与数据结构基础到高级全家桶教程#xff0c;直击BTAJ等一线大厂必问算法面试题真题详解#xff08;马士兵#xff09;】https://www.bilibili.com/video/BV13g41157hK?p4v…【一周刷爆LeetCode算法大神左神左程云耗时100天打造算法与数据结构基础到高级全家桶教程直击BTAJ等一线大厂必问算法面试题真题详解马士兵】https://www.bilibili.com/video/BV13g41157hK?p4vd_source04ee94ad3f2168d7d5252c857a2bf358
目录
2、认识O(NlogN)的排序
2.2 归并排序
2.2.1 思路代码实现
2.2.2 时间复杂度
2.2.3 应用小和问题 笔记
2、认识O(NlogN)的排序
2.2 归并排序
2.2.1 思路代码实现
在新数组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[p2];当p2先达右边界newArr[i] arr[p1];
整体代码
public static void mergeSort(int[] arr, int L, int M, int R){int[] newArr new int[R-L1];int i0;int p1L, p2M1;while( p1M p2 R ){newArr[i] arr[p1] arr[p2] ? arr[p1] : arr[p2]; //这部分等效于if( arr[p1] arr[p2] ){ newArr[i]arr[p1]}else{newArr[i]arr[p2]}}//处理其中一个指针到达边界的情况while ( p1 M ){newArr[i] arr[p1]}while ( p2 R ){newArr[i] arr[p2]}//如果要将排序后的新结果newArr替换掉旧数组arr则可以用for循环逐个替换for( i0; iarr.length; i){arr[Li] newArr[i];}}
2.2.2 时间复杂度
如果用master公式计算这个归并排序代码的时间复杂度T(N) 2*T(N/2) O(N)
解释左数组和右数组的数据量都是N/2且都是先组内排序再利用双指针遍历后放入数组遍历操作的时间复杂度是O(N)。
归并排序的时间复杂度O(NlogN)优于选择排序、插入排序等O(N…^2)的原因
在选择排序、插入排序中遍历一遍含n个元素的数组只能确定下来一个元素的位置其余的比较被浪费了。
而在归并排序中两个子数组的元素都是有序的因此每一次比较都能确定一个元素的位置并使指针后移继续比较后续的元素。
2.2.3 应用小和问题
小和问题一个数组中遍历每个元素然后把左侧比当前数小的数累加起来得到这个数组的小和。
举例数组元素为1、3、4、2、5的例子。
遍历开始前小和sum0
遍历到1左侧无更小值sum0
遍历到3左侧有1比3小sumsum1
遍历到4左侧有1、3比4小sumsum13
遍历到2左侧有1比2小sumsum1
遍历到5左侧有1、3、4、2比5小sumsum1342
此情景中的最终小和为16。 计算小和有2种时间复杂度不同的方法。
方法1O(N^2)。使用最纯粹的遍历方法。遍历数组然后将当前元素和左侧元素诸葛比较、加和得到小和。
方法2O(logN)。使用了归并排序对于每个元素如果它的右侧有m个元素比它大则再加上m*当前元素的值。
