归并排序
归并排序是分而治之的排序算法。
划分步骤很简单:将当前数组分成两半(如果N是偶数,则将其完全平等,或者如果N是奇数,则一边稍大于一个元素),然后递归地对这两半进行排序。
递归写法
归并排序递归写法的思想是,设定一个函数,函数实现的目的是「让int[] arr在L ~ R位置上有序」,处理过程是从L ~ R上找一个中间位置M,递归调用该函数,「让int[] arr的L ~ M上有序,M+1 ~ R上有序」,每一次不能往下递归了,便调用归并的方法将左右两边的数组合并成一个数组,到最后整个数组便有序了。
因此,归并排序使用递归方法实现的方法是:「整体是递归,左边排好序+右边排好序+merge让整体有序」。
伪代码理解这一过程:
递归地合并相邻的两个数组分区 i=左侧开始项指数到右侧最后项指数的遍历(两端包括) 如果左侧首值<=右侧首值 拷贝左侧首项的值 否则:拷贝右侧部分首值 将元素拷贝进原来的数组中将每个元素拆分成大小为1的部分
代码实现:
publicstaticvoidmain(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)); } publicstaticvoidmergeSort(int[]arr){ if(arr==null||arr.length2){ return; } process(arr,0,arr.length-1); } publicstaticvoidprocess(int[]arr,intL,intR){ if(L==R){ return; } intM=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); } publicstaticvoidmerge(int[]arr,intL,intM,intR){ System.out.println("开始归并arr["+L+"~"+M+"]和arr["+(M+1)+"~"+R+"]两部分数组"); //申请一个和arr长度一样的辅助数组 int[]help=newint[R-L+1]; //比较两组数组,谁小先拷贝谁到辅助数组,拷贝之后移动数组指针 //定义数组指针,LP表示左部分数组指针,RP表示右部分数组指针,i表示辅助数组的指针 intLP=L; intRP=M+1; inti=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;iarr[L+i]=help[i]; } } }publicclassMergeSort{
❝小技巧:
将一个int类型的数乘以2,可以使用位运算
<<
左移1位int类型的数除以2,位运算>>
右移1位别问为什么,问就是
位运算就是快!
❞
运行结果:
递归调用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]排序前:[18, 15, 13, 17, 6, 20, 15, 9]
递归函数调用过程,我画了个简图以助理解:
拿代码中的数组分析,过程大概就是这样子滴:
非递归写法
❝任何递归写法都能转换成非递归写法。
❞
直接上代码:
if(arr==null||arr.length2){ return; } //数组长度 intN=arr.length; //定义每部分参与比较数组的长度,初始长度为1 intmergeSize=1; //只要mergeSize小于N while(mergeSizeintL=0; while(LintM=L+mergeSize-1; if(M>=N){ break; } intR=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; } }publicstaticvoidmergeSort2(int[]arr){
其中的merge方法,还是前面递归方式调用的merge:
System.out.println("开始归并arr["+L+"~"+M+"]和arr["+(M+1)+"~"+R+"]两部分数组"); //申请一个和arr长度一样的辅助数组 int[]help=newint[R-L+1]; //比较两组数组,谁小先拷贝谁到辅助数组,拷贝之后移动数组指针 //定义数组指针,LP表示左部分数组指针,RP表示右部分数组指针,i表示辅助数组的指针 intLP=L; intRP=M+1; inti=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;iarr[L+i]=help[i]; } }publicstaticvoidmerge(int[]arr,intL,intM,intR){
运行结果:
开始归并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]排序前:[18, 15, 13, 17, 6, 20, 15, 9]
这里只是归并排序的非递归写法,思想也是分而治之!关键还是merge方法。
针对代码中的数组int[] arr={18, 15, 13, 17, 6, 20, 15, 9}
,其排序过程动图演示:
归并排序的时间复杂度
Level 0:2 ^ 0 = 1次调用merge( ) 和 N / 2 ^ 1个元素,时间:O(2 ^ 0 x 2 x N / 2 ^ 1)= O(N)
Level 1:2 ^ 1 = 2次调用 merge( ) 与N / 2 ^ 2个元素,O(2 ^ 1 x 2 x N / 2 ^ 2)= O(N)
Level 2:2 ^ 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表达式的写法套路❝看完点赞,养成习惯。
举手之劳,赞有余香。
❞