做个营销型网站要多少钱,网络营销是什么等综合因素促成,企业类型,广东建设信息网专业版归并排序归并排序是分而治之的排序算法。划分步骤很简单#xff1a;将当前数组分成两半(如果N是偶数#xff0c;则将其完全平等#xff0c;或者如果N是奇数#xff0c;则一边稍大于一个元素)#xff0c;然后递归地对这两半进行排序。递归写法归并排序递归写法的思想是将当前数组分成两半(如果N是偶数则将其完全平等或者如果N是奇数则一边稍大于一个元素)然后递归地对这两半进行排序。递归写法归并排序递归写法的思想是设定一个函数函数实现的目的是「让int[] arr在L ~ R位置上有序」处理过程是从L ~ R上找一个中间位置M递归调用该函数「让int[] arr的L ~ M上有序M1 ~ R上有序」每一次不能往下递归了便调用归并的方法将左右两边的数组合并成一个数组到最后整个数组便有序了。因此归并排序使用递归方法实现的方法是「整体是递归左边排好序右边排好序merge让整体有序」。伪代码理解这一过程将每个元素拆分成大小为1的部分递归地合并相邻的两个数组分区 i 左侧开始项指数 到 右侧最后项指数 的遍历(两端包括) 如果左侧首值 右侧首值 拷贝左侧首项的值 否则 拷贝右侧部分首值将元素拷贝进原来的数组中代码实现public class MergeSort { public static void main(String[] args) { int[] arr {18, 15, 13, 17, 6, 20, 15, 9}; System.out.println(排序前 Arrays.toString(arr)); mergeSort(arr); System.out.println(排序后 Arrays.toString(arr)); } public static void mergeSort(int[] arr) { if (arr null || arr.length 2) { return; } process(arr, 0, arr.length - 1); } public static void process(int[] arr, int L, int R) { if (L R) { return; } int M L ((R - L) 1); System.out.println(递归调用 L--M--R: L -- M -- R); //左边数组递归 process(arr, L, M); //右边数组递归 process(arr, M 1, R); merge(arr, L, M, R); } public static void merge(int[] arr, int L, int M, int R) { System.out.println(开始归并 arr[ L ~ M ]和arr[ (M 1) ~ R ]两部分数组); //申请一个和arr长度一样的辅助数组 int[] help new int[R - L 1]; //比较两组数组谁小先拷贝谁到辅助数组拷贝之后移动数组指针 //定义数组指针LP表示左部分数组指针RP表示右部分数组指针i表示辅助数组的指针 int LP L; int RP M 1; int i 0; //左右两边数组均不能越界 while (LP M RP R) { help[i] arr[LP] arr[RP] ? arr[LP] : arr[RP]; } //任何一边的数组要越界了就把该部分的数写到help数组 while (LP M) { help[i] arr[LP]; } while (RP R) { help[i] arr[RP]; } //写回到原数组 for (i 0; i arr[L i] help[i]; } }}❝小技巧将一个int类型的数乘以2可以使用位运算左移1位int类型的数除以2位运算右移1位别问为什么问就是位运算就是快❞运行结果排序前[18, 15, 13, 17, 6, 20, 15, 9]递归调用 L--M--R:0--3--7递归调用 L--M--R:0--1--3递归调用 L--M--R:0--0--1开始归并 arr[0~0]和arr[1~1]两部分数组递归调用 L--M--R:2--2--3开始归并 arr[2~2]和arr[3~3]两部分数组开始归并 arr[0~1]和arr[2~3]两部分数组递归调用 L--M--R:4--5--7递归调用 L--M--R:4--4--5开始归并 arr[4~4]和arr[5~5]两部分数组递归调用 L--M--R:6--6--7开始归并 arr[6~6]和arr[7~7]两部分数组开始归并 arr[4~5]和arr[6~7]两部分数组开始归并 arr[0~3]和arr[4~7]两部分数组排序后[6, 9, 13, 15, 15, 17, 18, 20]递归函数调用过程我画了个简图以助理解递归函数调用过程拿代码中的数组分析过程大概就是这样子滴递归归并排序图解非递归写法❝任何递归写法都能转换成非递归写法。❞直接上代码public static void mergeSort2(int[] arr) { if (arr null || arr.length 2) { return; } //数组长度 int N arr.length; //定义每部分参与比较数组的长度初始长度为1 int mergeSize 1; //只要mergeSize小于N while (mergeSize int L 0; while (L int M L mergeSize - 1; if (M N) { break; } int R Math.min(M mergeSize, N - 1); merge(arr, L, M, R); L R 1; } // 为什么需要这个主要是为了防止溢出int的最大值是21亿多(2^31-1) // 假如此时mergeSize是20亿运行下面mergeSize*2的时候就会溢出 if (mergeSize N / 2) { break; } mergeSize 1; }}其中的merge方法还是前面递归方式调用的mergepublic static void merge(int[] arr, int L, int M, int R) { System.out.println(开始归并 arr[ L ~ M ]和arr[ (M 1) ~ R ]两部分数组); //申请一个和arr长度一样的辅助数组 int[] help new int[R - L 1]; //比较两组数组谁小先拷贝谁到辅助数组拷贝之后移动数组指针 //定义数组指针LP表示左部分数组指针RP表示右部分数组指针i表示辅助数组的指针 int LP L; int RP M 1; int i 0; //左右两边数组均不能越界 while (LP M RP R) { help[i] arr[LP] arr[RP] ? arr[LP] : arr[RP]; } //任何一边的数组要越界了就把该部分的数写到help数组 while (LP M) { help[i] arr[LP]; } while (RP R) { help[i] arr[RP]; } //写回到原数组 for (i 0; i arr[L i] help[i]; }}运行结果排序前[18, 15, 13, 17, 6, 20, 15, 9]开始归并 arr[0~0]和arr[1~1]两部分数组开始归并 arr[2~2]和arr[3~3]两部分数组开始归并 arr[4~4]和arr[5~5]两部分数组开始归并 arr[6~6]和arr[7~7]两部分数组开始归并 arr[0~1]和arr[2~3]两部分数组开始归并 arr[4~5]和arr[6~7]两部分数组开始归并 arr[0~3]和arr[4~7]两部分数组排序后[6, 9, 13, 15, 15, 17, 18, 20]这里只是归并排序的非递归写法思想也是分而治之关键还是merge方法。针对代码中的数组int[] arr{18, 15, 13, 17, 6, 20, 15, 9}其排序过程动图演示归并排序动态演示归并排序的时间复杂度归并排序时间复杂度分析Level 02 ^ 0 1次调用merge( ) 和 N / 2 ^ 1个元素时间O(2 ^ 0 x 2 x N / 2 ^ 1) O(N)Level 12 ^ 1 2次调用 merge( ) 与N / 2 ^ 2个元素O(2 ^ 1 x 2 x N / 2 ^ 2) O(N)Level 22 ^ 2 4次调用merge( ) 与N / 2 ^ 3个元素O(2 ^ 2 x 2 x N / 2 ^ 3) O(N)...Level(log N)2 ^(log N-1)(或N / 2)次调用merge( ) )其中N / 2 ^ log N(或1)个元素O(N) 有 log(N) 个层每层都执行O(N)次工作因此总体时间复杂度为 「O(NlogN)」。❝拓展递归计算时间复杂度有一个Master公式形如「T(N) a * T(N/b) O(N^d)」(其中的a、b、d都是常数)的递归函数可以直接通过Master公式来确定时间复杂度。如果 log(b,a) d复杂度为O(N^d)如果 log(b,a) d复杂度为O(N^log(b,a))如果 log(b,a) d复杂度为O(N^d * logN)我们的归并排序可以用下面的公式来计算T(N) 2*T(N/2) O(N^1)根据master可知推导出时间复杂度为「O(N×logN)」❞另外merge过程需要辅助数组所以额外空间复杂度为O(N)归并排序的实质是把比较行为变成了有序信息并传递比O(N^2)的排序快。欢迎阅读我的其他Java基础文章为什么当初不好好学习算法我用线程池ThreadPoolExecutor处理任务和Redis做缓存查询将程序效率提升了5倍从一道面试题进入Java并发新机制---J.U.Csynchronized底层实现知多少synchronized加锁还会升级你知道Object o new Object()在内存中占多少字节吗Java8新特性Stream还有这种操作终于看懂别人的代码了总结Java 8之Lambda表达式的写法套路❝看完点赞养成习惯。举手之劳赞有余香。❞
